A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

Submitted by Maicon Juliano Schmidt (maicons) on 2015-07-06T16:35:49Z No. of bitstreams: 1 Luana Carine Schünke.pdf: 7508388 bytes, checksum: a12396bedf39ca3d110912e0a25ef468 (MD5) / Made available in DSpace on 2015-07-06T16:35:49Z (GMT). No. of bitstreams: 1 Luana Carine Schünke.pdf: 7508388 bytes, checksum: a12396bedf39ca3d110912e0a25ef468 (MD5) Previous issue date: 2013-01-31 / Nenhuma / Cidades participativas são aquelas em que os seus cidadãos participam na construção e melhora do cotidiano da sua cidade. Neste sentido, a ideia é de que através de uma página virtual as pessoas possam registrar eventos relacionados a sua cidade. Exemplos de eventos são crimes, acidentes, manutenções, entre outros. Através da mesma página virtual, os cidadãos também podem visualizar informações sobre a sua cidade, essas visualizações são resultantes da integralização dos dados registrados pelos próprios cidadãos. O objetivo deste trabalho é gerar a visualização e a interação de diferentes classes de ocorrências em cidades participativas. Para isso, são estudados vários conceitos como: visualização de informações, diagramas de Voronoi, árvore quaternária, envoltória convexa e API do Google Maps. A partir desses estudos, é criado um modelo de visualização de ocorrências. As visualizações resultantes geram regiões de acordo com a densidade das ocorrências. A interação entre duas classes de ocorrências acontece com base nas densidades das ocorrências e também de acordo com uma distribuição de contexto. As classes de ocorrências escolhidas para as interações são ocorrências criminais e ocorrências policiais. A distribuição de contexto riqueza é aplicada com o intuito de ser um atrativo para as ocorrências criminais. O comportamento do sistema oriundo das interações é analisado e representado graficamente. / Participatory cities are those that citizens participate in the construction and improvement of their common daily life. In this direction, the idea of this work is that through a website people can record issues/occurrences related to their city. Examples of occurrences are crimes, accidents, maintenance issues, among others. Through the same site, citizens can get global information about the city, resulted from the integration of the supplied data by the use of a visualization scheme. The goal of this work is to create views and interactions about the occurrences registered in a participatory city. For this, many concepts are studied like: data visualizing, Voronoi diagrams, quaternary tree, convex hull and Google Maps API. Starting from this studies, there is created a model visualization of occurrences. The resulting visualizations generate regions according occurrences densities. Based on occurrences densities and also in agreement with a context distribution the interaction between two classes of events befall. Criminal occurrences and police occurrences are the classes of events selected to interact. The wealth context distribution is apllied with the aim to be attractive for the criminal occurrences. The system behavior arising from interactions is analyzed and graphically represented.

A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

En aquesta tesi es solucionen problemes de visibilitat i proximitat sobre superfícies triangulades considerant elements generalitzats. Com a elements generalitzats considerem:punts, segments, poligonals i polígons. Les estrategies que proposem utilitzen algoritmesde geometria computacional i hardware gràfic. Comencem tractant els problemes de visibilitat sobre models de terrenys triangulats considerant un conjunt d'elements de visió generalitzats. Es presenten dos mètodes per obtenir, de forma aproximada, mapes de multi-visibilitat. Un mapa de multi-visibilitat és la subdivisió del domini del terreny que codifica la visibilitat d'acord amb diferents criteris. El primer mètode, de difícil implementació, utilitza informació de visibilitat exacte per reconstruir de forma aproximada el mapa de multi-visibilitat. El segon, que va acompanyat de resultats d'implementació, obté informació de visibilitat aproximada percalcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Coma aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntessobre la multi-visibilitat d'un punt o d'una regió. A continuació tractem els problemes de proximitat sobre superfícies polièdriques triangulades considerant seus generalitzades. Es presenten dos mètodes, amb resultats d'implementació, per calcular distàncies des de seus generalitzades sobre superfícies polièdriques on hi poden haver obstacles generalitzats. El primer mètode calcula, de forma exacte, les distàncies definides pels camins més curts des de les seus als punts del poliedre. El segon mètode calcula, de forma aproximada, distàncies considerant els camins més curts sobre superfícies polièdriques amb pesos. Com a aplicacions, es calculen diagrames de Voronoi d'ordre k, i es resolen, de forma aproximada, alguns problemes de localització de serveis. També es proporciona un estudi teòric sobre la complexitat dels diagrames de Voronoi d'ordre k d'un conjunt de seus generalitzades en un poliedre sense pesos. / In this thesis, we solve visibility and proximity problems on triangulated surfaces concerning generalized elements. As generalized elements, we consider: points, segments, polygonal chains and polygonal regions. The proposed strategies use algorithms of Computational Geometry and Graphics Hardware. We start by studying multi-visibility problems on triangulated terrain models concerning a set of generalized view elements. We present two methods to obtain approximate multi-visibility maps. A multi-visibility map is a subdivision of the terrain domain encoding visibility according to different criteria. The first method, of complex implementation, uses exactly computed visibility information to approximately reconstruct the unknown multi-visibility map. The second, from which implementation results are provided, uses approximate visibility information to compute and visualize discrete multi-visibility maps by exploiting graphics hardware capabilities. As applications, we compute multi-visibility maps, solve inter-region multi-visibility problems and approximately answer point and polygonal region multi-visibility queries. Next, we tackle proximity problems on triangulated polyhedral surfaces, where generalized obstacles are allowed, considering generalized sources. We present two methods, with implementation results, to compute distances on polyhedral surfaces from a generalized source. The first method computes exact shortest path distances from generalized sources. The second provides approximate weighted shortest path distances from generalized sites on weighted polyhedral surfaces. Both methods are posteriorly extended to handle the multiple-site problem where the corresponding distance field is obtained. As applications, we compute discrete order-k Voronoi diagrams and approximately solve some facility location problems. We also provide a theoretical study on the order-k Voronoi diagram complexity of a set of generalized sources for the non-weighted case.

In this dissertation, we study the triangular mesh simplification process, describing its main characteristics. We discuss an adaptation for triangular meshes of a mesh simplification process based on Voronoi coverage proposed by Peixoto [2002]. Moreover, we use Fast Marching Method as a distance function over the mesh and some different strategies for simplified mesh vertices selection, like curvature based selection. The simplification process is done by constructing an intrinsic Voronoi diagram over the original mesh. We discuss some necessary conditions to obtain a mesh, as Voronoi dual, without any singularities and topologically equivalent to the original mesh. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nesta dissertação, estudaremos o processo de simplificaçãoo de malhas triangulares, caracterizando-o com suas particularidades. Discutiremos uma adaptação para superfícies triangulares do método de simplificação baseado em uma cobertura de Voronoi proposto por Peixoto [2002]. Além disso, utilizaremos o método Fast Marching como uma nova métrica e diferentes estratégias para seleção de vértices da malha simplificada, como a seleção por curvatura. A simplificação ocorre a partir de um diagrama de Voronoi intrínseco à malha. Discutiremos algumas condições necessárias para que a partir do dual desse diagrama, obtenha-se uma malha sem singularidades que seja equivalente a malha original.

Made available in DSpace on 2017-06-01T18:20:35Z (GMT). No. of bitstreams: 1 dissertacao_alex_sandro.pdf: 1913546 bytes, checksum: 4b66064e90d6f91355a93dc670dd6261 (MD5) Previous issue date: 2011-11-30 / Atmospheric pollutants has become a major world concern for environmental and public health. Several studies have already addressed in this context about theme in order to verify the association between increased incidences of diseases with increased air pollution, mainly in cities where vehicle traffic has increased significantly. The pollution control is usually done by monitoring air quality through the sensor network. This monitoring network, besides being used as a tool for measuring public health safety, allow analyze the benefits gained by efforts to control the levels of air pollution and justify possible actions in case of breach of the thresholds established by legislation. The high costs involved and the difficulty inherent in the logistics of deployment and maintenance of the collection points can lead to an inappropriate placement or unrepresentative, if not carefully studied. Therefore, a good choice of site of insertion point is essential to provide greater efficiency in these costs. In this sense, the use of the weighted diagram Vononoi was used as a tool to determine the coverage area of each pollutant atmospheric sensor. After being realized the simulations, the coverage area of each sensor related with their own weight, were presented in a satisfactory way / A poluição atmosférica tornou-se uma das maiores preocupações mundiais para a saúde pública e ambiental. Vários estudos já abordaram o contexto desse tema, no intuito de verificar a associação entre o aumento da incidência de doenças com o aumento da poluição atmosférica, principalmente em cidades onde o tráfego de veículos tem aumentado de forma significante. O controle dessa poluição, normalmente, é realizado através da monitoração da qualidade do ar, por meio de rede de sensores. Esta rede de monitoramento, além de ser utilizada como instrumento de medida de segurança de saúde pública, permite analisar os benefícios propiciados pelas ações de controle dos níveis de poluição do ar e justifica possíveis intervenções em caso de violação dos limiares estabelecidos pela legislação. Os altos custos envolvidos e a dificuldade inerente à logística de implantação e manutenção dos pontos de coleta podem levar a um posicionamento inadequado ou pouco representativo, quando não estudado cuidadosamente. Portanto, uma boa escolha do local de inserção do ponto é indispensável para propiciar uma maior eficiência nesses custos. Os Diagramas de Voronoi Valorados foram utilizados como uma ferramenta para determinar a área de abrangência de cada sensor de poluição atmosférica. Após a realização das simulações, as áreas de abrangência de cada sensor relacionada com seu peso, foram apresentadas de maneira satisfatória

The thesis deals with computational modelling of ceramic foams and analysis of influence of structural manufacturing defects (like broken struts, closed pores and material clumps) have on foam strength. Model of foam geometry was discretized using beam elements in order to decrease computational cost. In place where several struct join, rigid beam element was used so that the increased stiffness is better modelled. Closed walls of pores were modelled and discretised by shell elements. Influence of loading direction was analysed on foams containing no defects and then influence of amount of defects in foam on strength was further analysed. Highest strength show foams created by cells whose structs are oriented in direction of loading. These were losing strength most rapidly. Foam with structure of rhombic dodecahedral cell was least influenced by presence of closed pore defects but it also showed lowest strength even without defects. Cells with struts oriented in direction of loading experienced biggest drop in strength. Kelvin cell is a compromise. It was shown that difference in strength of strut with constant and varying cross-section is tenths of percent.

This thesis deals with procedural generation techniques and its use in the creation of voxel models. The techniques that have been used are Perlin Noise, Voronoi diagram, L-systems etc. This knowledge is then used to create a world generator for computer game with open world. This game provides players with the ability to modify this world and use its creativity, for example, in building construction. The game, however, will not give to the player all options for free, but for example for build, he or she will first have to find and mine the material. The game has been written in programming language C++ with the use of libraries Boost, SDL and OpenGL.

[pt] Uma boa representação de malhas tridimensionais é fundamental para a renderização de objetos e para simulações numéricas. Ocorre, entretanto, que, quando objetos são capturados através de sensores, é comum existir super amostragem em algumas regiões e/ou sub amostragem em outras. Para resolver esse problema existem diversas técnicas na literatura de reamostragem da malha. Recentemente uma abordagem mais generalizada para uma representação utilizando malhas de triângulos e com boas garantias matemáticas gerando malhas com triângulos muito próximos aos triângulos de Delaunay vem ganhando destaque. O grande problema desta técnica para a aplicação de objetos com bordas (buracos ou malha aberta) é que ela faz um efeito de erosão nas bordas. Para uma aplicação em que as bordas e buracos devem representar aproximadamente a mesma região isso é um grande problema. Neste trabalho apresentamos uma abordagem geométrica para a reamostragem da representação do objeto que resolve este problema aplicado em dados de horizonte sísmico. / [en] A good mesh representation of tridimensional objects is necessary not only to render algorithms but also to support numerical simulations. Objects captured via sensors, e.g., seismic acquisition and laser scanning, have an intrinsic error in its representation of objects. Furthermore, this unprocessed data does not generate a good description of the objects, portraying it inadequately or incorrectly. The existing literature on resampling representations contains various techniques to resolve this problem. In particular, a general approach using triangle mesh has recently gained attention. One benefit of this technique is its mathematical guarantees generating triangles meshes that closely approximate Delaunay triangles. The main drawback to this technique occurs in its application to objects with borders, such as holes or mesh intersections. In this work, we present a new method to re-mesh the object representation taking into account the simplification of the curves that represent the holes. We apply this technique to seismic horizon data.

In real world applications such as rescue robots, service robots, mobile mining robots, and mine searching robots, an autonomous mobile robot needs to reach multiple goals with the shortest path while avoiding obstacles. In this thesis, we propose Artificial Immune System (AIS) based algorithms and two hybrids based on AIS associated with the Simulated Annealing (SA) algorithm and Voronoi Diagram (VD) for real-time map building and path planning for multi-goal applications. A global route is initially planned by the Immune System Algorithm (ISA). Then the created path is used to guide the robot to multiple waypoints following the foraging trail. An AIS-based point-to-point navigator is also proposed and tested here, which is used to navigate the robot along a collision-free global route. The proposed hybrid ISA model integrated with SA or VD algorithm aims to generate paths while a mobile robot explores terrain with map building in an unknown environment. We explore the ISA algorithm with simulation and comparison studies to demonstrate the capability of the proposed hybrid model of AIS and SA or AIS and VD algorithms in achieving a global route with minimized overall distance. Simulation and comparison studies validate the efficiency and effectiveness of the proposed hybrid models. They also confirm that concurrent multi-waypoint navigation with obstacle avoidance and mapping of an autonomous robot is successfully performed under unknown environments.