Spelling suggestions: "subject:"voronoi diagrams"" "subject:"voronoi iagrams""
11 |
K-set Polygons and Centroid TriangulationsEl Oraiby, Wael 09 October 2009 (has links) (PDF)
This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.
|
12 |
Fluid distribution optimization in porous media using leaf venation patterns / Otimização da distribuição de fluidos em meios porosos usando padrões de venações de folhasOliveira, Caio Martins Ramos de 22 March 2017 (has links)
Several examples of nearly optimal transport networks can be found in nature. These networks effectively distribute and drain fluids throughout a medium. Evidence suggests that blood vessels of the circulatory system, airways in the lungs and veins of leaf venations are examples of networks that have evolved to become effective in their tasks while simultaneously being energy efficient. Hence, it does not come as a surprise that recent performance improvements of modern power generating devices occur due to the use of nature-inspired channel architectures. Guided by this observations, in this work, we investigate the application of visually realistic computer-generated leaf venation patterns to a type of photovoltaic device. We solve the flow through the device problem using Computational Fluid Dynamics (CFD) tools. Moreover, we attempt to develop experimentals models. Ultimately, we seek to single out the network properties that affect their performance. / Diversos exemplos de redes de transporte quase ótimas podem ser encontradas na natureza. Essas redes distribuem e coletam fluidos através de um meio. Evidências sugerem que os vasos sanguíneos do sistema circulatório, as vias respiratórias nos pulmões e as veias das venações em folhas são exemplares de redes que evoluiram para se tornarem efetivas em suas tarefas sendo, ao mesmo tempo, eficientes energeticamente. Dessa forma, não chega a ser surpreendente que recentes melhorias de performance em dispositivos de geração de energia modernos ocorrem devido ao uso de arquiteturas de canais inspiradas na natureza. Guiados por estas observações, nesse trabalho, investigamos a aplicação de padrões de venações verossímeis geradas por computador em um tipo de dispositivo fotovoltaico. Resolvemos o problema de escoamento através do dispositivo usando ferramentas de Dinâmica de Fluidos Computacional (CFD). Além disso, procuramos desenvolver modelos experimentais. Em última instância, estamos em busca das propriedades da rede que afetam sua performance.
|
13 |
Análise dos erros na estimação de gradientes em malhas de Voronoi / Analysis errors in the estimation of gradient in Voronoi meshesJailson França dos Santos 18 March 2013 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho apresenta um estudo teórico e numérico sobre os erros que ocorrem nos
cálculos de gradientes em malhas não estruturadas constituídas pelo diagrama de Voronoi,
malhas estas, formadas também pela triangulação de Delaunay. As malhas adotadas, no
trabalho, foram as malhas cartesianas e as malhas triangulares, esta última é gerada pela
divisão de um quadrado em dois ou quatro triângulos iguais. Para tal análise, adotamos a
escolha de três metodologias distintas para o cálculo dos gradientes: método de Green Gauss,
método do Mínimo Resíduo Quadrático e método da Média do Gradiente Projetado
Corrigido. O texto se baseia em dois enfoques principais: mostrar que as equações de erros
dadas pelos gradientes podem ser semelhantes, porém com sinais opostos, para pontos de
cálculos em volumes vizinhos e que a ordem do erro das equações analíticas pode ser
melhorada em malhas uniformes quando comparada as não uniformes, nos casos
unidimensionais, e quando analisada na face de tais volumes vizinhos nos casos
bidimensionais. / This work presents a theoretical and numerical study on the errors that occur in the
calculation of gradients on unstructured meshes Voronoi type, these meshes, also formed by
Delaunay triangulation. The meshes adopted in the work were cartesian and triangular
meshes, the latter is formed by dividing a square in two or four equal triangles. For this
analysis, we adopt the choice of three different methodologies for the calculation of gradients:
Green Gauss method, weighted least-squares method and mean value of the projected
gradients method. The text is based on two main approaches: to show that the equations of
errors given by the gradients may be similar, but with opposite signs, for calculation point in
opposite volumes. And show that the order of the error of the analytical equations can be
improved in uniform mesh when compared to not uniform, the one-dimensional case, and
when viewed from the opposite face of such volumes for the two-dimensional case.
|
14 |
[en] MULTIRESOLUTION ADAPTIVE MESH EXTRACTION FROM VOLUMES, USING SIMPLIFICATION AND REFINEMENT / [pt] EXTRAÇÃO DE MALHAS ADAPTATIVAS EM MULTI-RESOLUÇÃO A PARTIR DE VOLUMES, USANDO SIMPLIFICAÇÃO E REFINAMENTOADELAILSON PEIXOTO DA SILVA 13 June 2003 (has links)
[pt] Este trabalho apresenta um método para extração de malhas
poligonais adaptativas em multi-resolução, a partir de
objetos volumétricos. As principais aplicações da
extração
de malhas estão ligadas à área médica, dinâmica de
fluidos,
geociências, meteorologia, dentre outras. Nestas áreas os
dados podem ser representados como objetos volumétricos.
Nos dados volumétricos as informações estão representadas
implicitamente, o que dificulta o processamento direto
dos
objetos que se encontram representados dentro do volume.
A
extração da malha visa obter uma representação explícita
dos objetos, de modo a viabilizar o processamento dos
mesmos. O método apresentado na tese procura extrair a
malha a partir de processos de Simplicação e Refinamento.
Durante a simplificação é extraída uma representação
super
amostrada do objeto (na mesma resolução do volume
inicial),
a qual é simplificada de modo a se obter uma malha base
ou
malha grossa, em baixa resolução, porém contendo a
topologia correta do objeto.
A etapa de refinamento utiliza a transformada de distâ
ncia
para obter uma representação da malha em multi-resolução,
ou seja, a cada instante é obtida uma malha de maior
resolução que vai se adaptando progressivamente à
geometria
do objeto. A malha final apresenta uma série de
propriedades
importantes, como boa razão de aspecto dos triângulos,
converge para a superfície do objeto, pode ser aplicada
tanto a objetos com borda quanto a objetos sem borda,
pode
ser aplicada tanto a superfície conexas quanto a não
conexas, dentre outras. / [en] This work presents a method for extracting multiresolution
adaptive polygonal meshes, from volumetric objects. Main
aplications of this work are related to medical area, fluid
dynamics, geosciences, metheorology and others. In these
areas data may be represented as volumetric objects.
Volumetric datasets are implicit representations of
objects, so it s very dificult to apply directly any
process to these objects. Mesh extraction obtains an
explicit representation of the objetc, such that it s
easier to process directly the objects.
The presented method extracts the mesh from two main
processes: Simplification and Refinement. The
simplification step extracts a supersampled representation
of the object (in the same volume resolution), and
simplifies it in such a way to obtain a base mesh (or
coarse mesh), in a low resolution, but containing the
correct topology of the object. Refinement step uses the
distance transform to obtain a multiresolution
representation of the mesh, it means that at each instant
it s obtained an adaptive higher resolution mesh. The final
mesh presents a set of important properties, like good
triangle aspect ratio, convergency to the object surface,
may be applied as to objects with boundary and as to
objects with multiple connected components, among others
properties.
|
15 |
Optimal steering for kinematic vehicles with applications to spatially distributed agentsBakolas, Efstathios 10 November 2011 (has links)
The recent technological advances in the field of autonomous vehicles have resulted in a growing impetus for researchers to improve the current framework of mission planning and execution within both the military and civilian contexts. Many recent efforts towards this direction emphasize the importance of replacing the so-called monolithic paradigm, where a mission is planned, monitored, and controlled by a unique global decision maker, with a network centric paradigm, where the same mission related tasks are performed by networks of interacting decision makers (autonomous vehicles). The interest in applications involving teams of autonomous vehicles is expected to significantly grow in the near future as new paradigms for their use are constantly being proposed for a diverse spectrum of real world applications.
One promising approach to extend available techniques for addressing problems involving a single autonomous vehicle to those involving teams of autonomous vehicles is to use the concept of Voronoi diagram as a means for reducing the complexity of the multi-vehicle problem. In particular, the Voronoi diagram provides a spatial partition of the environment the team of vehicles operate in, where each element of this partition is associated with a unique vehicle from the team. The partition induces, in turn, a graph abstraction of the operating space that is in a one-to-one correspondence with the network abstraction of the team of autonomous vehicles; a fact that can provide both conceptual and analytical advantages during mission planning and execution. In this dissertation, we propose the use of a new class of Voronoi-like partitioning schemes with respect to state-dependent proximity (pseudo-) metrics rather than the Euclidean distance or other generalized distance functions, which are typically used in the literature. An important nuance here is that, in contrast to the Euclidean distance, state-dependent metrics can succinctly capture system theoretic features of each vehicle from the team (e.g., vehicle kinematics), as well as the environment-vehicle interactions, which are induced, for example, by local winds/currents. We subsequently illustrate how the proposed concept of state-dependent Voronoi-like partition can induce local control schemes for problems involving networks of spatially distributed autonomous vehicles by examining different application scenarios.
|
16 |
Mimetic finite differences for porous media applicationsAl-Hinai, Omar A. 07 July 2014 (has links)
We connect the Mimetic Finite Difference method (MFD) with the finite-volume two-point flux scheme (TPFA) for Voronoi meshes. The main effect is reducing the saddle-point system to a much smaller symmetric-positive definite matrix. In addition, the generalization allows MFD to seamlessly integrate with existing porous media modeling technology. The generalization also imparts the monotonicity property of the TPFA method on MFD. The connection is achieved by altering the consistency condition of the velocity bilinear operator. First-order convergence theory is presented as well as numerical results that support the claims. We demonstrate a methodology for using MFD in modeling fluid flow in fractures coupled with a reservoir. The method can be used for nonplanar fractures. We use the method to demonstrate the effects of fracture curvature on single-phase and multi-phase flows. Standard benchmarks are used to demonstrate the accuracy of the method. The approach is coupled with existing reservoir simulation technology. / text
|
17 |
Análise dos erros na estimação de gradientes em malhas de Voronoi / Analysis errors in the estimation of gradient in Voronoi meshesJailson França dos Santos 18 March 2013 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho apresenta um estudo teórico e numérico sobre os erros que ocorrem nos
cálculos de gradientes em malhas não estruturadas constituídas pelo diagrama de Voronoi,
malhas estas, formadas também pela triangulação de Delaunay. As malhas adotadas, no
trabalho, foram as malhas cartesianas e as malhas triangulares, esta última é gerada pela
divisão de um quadrado em dois ou quatro triângulos iguais. Para tal análise, adotamos a
escolha de três metodologias distintas para o cálculo dos gradientes: método de Green Gauss,
método do Mínimo Resíduo Quadrático e método da Média do Gradiente Projetado
Corrigido. O texto se baseia em dois enfoques principais: mostrar que as equações de erros
dadas pelos gradientes podem ser semelhantes, porém com sinais opostos, para pontos de
cálculos em volumes vizinhos e que a ordem do erro das equações analíticas pode ser
melhorada em malhas uniformes quando comparada as não uniformes, nos casos
unidimensionais, e quando analisada na face de tais volumes vizinhos nos casos
bidimensionais. / This work presents a theoretical and numerical study on the errors that occur in the
calculation of gradients on unstructured meshes Voronoi type, these meshes, also formed by
Delaunay triangulation. The meshes adopted in the work were cartesian and triangular
meshes, the latter is formed by dividing a square in two or four equal triangles. For this
analysis, we adopt the choice of three different methodologies for the calculation of gradients:
Green Gauss method, weighted least-squares method and mean value of the projected
gradients method. The text is based on two main approaches: to show that the equations of
errors given by the gradients may be similar, but with opposite signs, for calculation point in
opposite volumes. And show that the order of the error of the analytical equations can be
improved in uniform mesh when compared to not uniform, the one-dimensional case, and
when viewed from the opposite face of such volumes for the two-dimensional case.
|
18 |
Fluid distribution optimization in porous media using leaf venation patterns / Otimização da distribuição de fluidos em meios porosos usando padrões de venações de folhasCaio Martins Ramos de Oliveira 22 March 2017 (has links)
Several examples of nearly optimal transport networks can be found in nature. These networks effectively distribute and drain fluids throughout a medium. Evidence suggests that blood vessels of the circulatory system, airways in the lungs and veins of leaf venations are examples of networks that have evolved to become effective in their tasks while simultaneously being energy efficient. Hence, it does not come as a surprise that recent performance improvements of modern power generating devices occur due to the use of nature-inspired channel architectures. Guided by this observations, in this work, we investigate the application of visually realistic computer-generated leaf venation patterns to a type of photovoltaic device. We solve the flow through the device problem using Computational Fluid Dynamics (CFD) tools. Moreover, we attempt to develop experimentals models. Ultimately, we seek to single out the network properties that affect their performance. / Diversos exemplos de redes de transporte quase ótimas podem ser encontradas na natureza. Essas redes distribuem e coletam fluidos através de um meio. Evidências sugerem que os vasos sanguíneos do sistema circulatório, as vias respiratórias nos pulmões e as veias das venações em folhas são exemplares de redes que evoluiram para se tornarem efetivas em suas tarefas sendo, ao mesmo tempo, eficientes energeticamente. Dessa forma, não chega a ser surpreendente que recentes melhorias de performance em dispositivos de geração de energia modernos ocorrem devido ao uso de arquiteturas de canais inspiradas na natureza. Guiados por estas observações, nesse trabalho, investigamos a aplicação de padrões de venações verossímeis geradas por computador em um tipo de dispositivo fotovoltaico. Resolvemos o problema de escoamento através do dispositivo usando ferramentas de Dinâmica de Fluidos Computacional (CFD). Além disso, procuramos desenvolver modelos experimentais. Em última instância, estamos em busca das propriedades da rede que afetam sua performance.
|
19 |
[pt] OTIMIZAÇÃO TOPOLÓGICA COM REFINAMENTO ADAPTATIVO DE MALHAS POLIGONAIS / [en] TOPOLOGY OPTIMIZATION WITH ADAPTIVE POLYGONAL MESH REFINEMENTTHOMÁS YOITI SASAKI HOSHINA 03 November 2016 (has links)
[pt] A otimização topológica tem como objetivo encontrar a distribuição mais
eficiente de material (ótima topologia) em uma determinada região, satisfazendo
as restrições de projeto estabelecidas pelo usuário. Na abordagem
tradicional atribui-se uma variável de projeto, constante, denominada densidade,
para cada elemento finito da malha. Dessa forma, a qualidade da representação
dos novos contornos da estrutura depende do nível de discretização
da malha: quanto maior a quantidade de elementos, mais bem definida
será a topologia da estrutura otimizada. No entanto, a utilização de malhas
super-refinadas implica em um elevado custo computacional, principalmente
na etapa de solução numérica das equações de equilíbrio pelo método dos elementos
finitos. Este trabalho propõe uma nova estratégia computacional para
o refinamento adaptativo local de malhas utilizando elementos finitos poligonais
em domínios bidimensionais arbitrários. A ideia consiste em realizar um
refinamento da malha nas regiões de concentração de material, sobretudo nos
contornos internos e externos, e um desrefinamento nas regiões de baixa concentração
de material, como por exemplo, nos furos internos. Desta forma, é
possível obter topologias ótimas, com alta resolução e relativamente baixo custo
computacional. Exemplos representativos são apresentados para demonstrar a
robustez e a eficiência da metodologia proposta por meio de comparações com
resultados obtidos com malhas super-refinadas e mantidas constantes durante
todo o processo de otimização topológica. / [en] Topology optimization aims to find the most efficient distribution of
material (optimal topology) in a given domain, subjected to design constraints
defined by the user. The quality of the new boundary representation depends
on the level of mesh refinement: the greater the number of elements in the mesh,
the better will be the representation of the optimized structure. However, the
use of super refined meshes implies in a high computational cost, especially
regarding the numerical solution of the linear systems of equations that arise
from the finite element method. This work proposes a new computational
strategy for adaptive local mesh refinement using polygonal finite elements in
arbitrary two-dimensional domains. The idea is to perform a mesh refinement
in regions of material concentration, mostly in inner and outer boundaries,
and a mesh derefinement in regions of low material concentration such as
the internal holes. Thus, it is possible to obtain optimal topologies with high
resolution and relatively low computational cost. Representative examples
are presented to demonstrate the robustness and efficiency of the proposed
methodology by comparing the results obtained herein with the ones from the
literature where super refined meshes are held constant throughout all topology
optimization process.
|
20 |
Um método para análise e visualização de dados georreferenciados relacionados ao trânsito de veículosMachado, Jonathan 30 March 2017 (has links)
Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2017-06-13T15:57:01Z
No. of bitstreams: 1
Jonathan Machado_.pdf: 1018280 bytes, checksum: ac428b5c72c1ef24649cb96a3a778512 (MD5) / Made available in DSpace on 2017-06-13T15:57:01Z (GMT). No. of bitstreams: 1
Jonathan Machado_.pdf: 1018280 bytes, checksum: ac428b5c72c1ef24649cb96a3a778512 (MD5)
Previous issue date: 2017-03-30 / Nenhuma / Os acidentes de trânsito de veículos são uma das maiores causas de mortes na população jovem mundial, e existe uma tendência ao crescimento no número de casos dos mesmos nos próximos anos. A ocorrência dos acidentes é influenciada por diversos fatores, tais como condições das vias, condições climáticas, fiscalização de leis por órgãos governamentais, dentre outros. Seria interessante conhecer de maneira mais detalhada quais destes fatores detém maior influência. Na internet, existe uma quantidade imensa de dados gerados pelos mais diversos órgãos e empresas, porém grande parte desta informação não é analisada por ninguém, seja por falta de acesso, ou porque os dados não estão estruturados de uma maneira que permita seu entendimento. A disponibilização de dados vem aumentando, seja por conta de políticas de dados abertos implantadas pelo governo ou através de ferramentas colaborativas da web, que possibilitam o registro de informações por parte da população, e que posteriormente disponibilizam seus dados. Este trabalho propõe um método de agrupamento de dados georreferenciados oriundos de diversas fontes, para realização de uma análise estatística utilizando a técnica de Análise de Componentes Principais, que poderá identificar de forma georreferenciada quais características influenciam mais na ocorrência de acidentes de trânsito de veículos. Após a análise, é explorada uma nova metodologia de visualização dos resultados, plotados sobre mapas, que podem servir de auxílio para órgãos do governo e tomadores de decisão que realizam ações para diminuir os acidentes de trânsito. / Traffic accidents of vehicles are one of the biggest causes of deaths in the world's young population, and there is a tendency to increase this number in the next years. The occurrence of accidents is influenced by several factors, such as road conditions, climatic conditions, law enforcement by government agencies, among others. It would be interesting to know in more detail which of these factors has the greatest influence. On the internet, there is an immense amount of data generated by diverse agencies and companies, but much of this information is not analyzed, either because of lack of access, or because the data is not structured in a way that allows its understanding. The availability of data is increasing, either through open data policies implemented by the government, or through collaborative web tools, which make it possible record information by population, and subsequently make their data available. This work proposes a method of grouping georeferenced data from several sources, to perform a statistical analysis using the technique of Principal Components Analysis, which can identify in a georeferenced way which characteristics influence more in the occurrence of traffic acidentes of vehicles. After the analysis, a new methodology for visualizing results, plotted on maps, is explored, which can serve as an aid to government agencies and decision makers who take actions to reduce traffic accidents.
|
Page generated in 0.0712 seconds