Um gerador incremental de diagramas de Voronoi com domínio limitado por contorno convexo /

Abstract

Esta dissertação apresenta um algoritmo incremental para geração do Diagrama de Voronoi interno a um contorno arbitrário convexo.O algoritmo proposto utiliza conceitos básicos da geometria computacional, uma estrutura de dados adequada para este tipo de problema e trata os todos pontos geradores uniformemente. Em linhas gerais o processo da adição de um novo ponto gerador consiste em: encontrar no diagrama o ponto gerador mais próximo e dividir sua região com o novo ponto; Identificar prováveis vizinhos deste novo ponto gerador e também para cada um dividir sua região, e finalmente eliminar vértices desnecessários. Este algoritmo foi Implementado em MatLab, devido as suas facilidades computacionais e desta forma evitou-se o envolvimento em problemas como, estruturas de armazenamento de dados, visualização dos resultados, etc. O presente algoritmo foi testado para até 1000 pontos geradores aleatórios e também pontos geradores de malhas hexagonais, triangulares e retangulares. O algoritmo proposto apresentou os resultados esperados sem reportar erros numéricos ou topológicos.

This dissertation presents an incremental algorithm to generate Voronoi Diagrams internal with respect to an arbitrary convex boundary. The proposed algorithm uses basic concepts from computational geometry, a data structure suitable for this type of problem and treats uniformly each source point. In summary, the process of adding a new source point consists of the following steps: find the closest source point in the diagram and split its region with the new point, identify possible neighboors of the new source point and split the regions of each, and finally, eliminate unnecessary vertices. This algorithm was implemented in MatLab in order to take advantage of its computational facilities and to avoid dealing with problems like strutures for data storage, visualization of results, etc. The present algorithm was tested with up to 1000 randomically generated source points and also with source points for hexagonal, triangular and rectangular meshes. The proposed algorithm produced the expected results, without reporting numerical or topological errors.