Memoria para optar al título de Ingeniero Civil en Computación / La triangulación de Delaunay es una entidad geométrica con muchas aplicaciones en computación gráfica e ingeniería. Por lo general, su construcción es un problema difícil que a menudo viene acompañado con restricciones geométricas y de calidad. Para facilitar la experimentación de algoritmos relativos al problema de Delaunay, se presenta una herramienta con mejoras en simplicidad, desempeño y robustez frente a otras opciones existentes. En primer lugar, se ofrece una implementación sólida del algoritmo de Delaunay incremental con intercambio de aristas, el cual es un método conocido que aborda el problema agregando cada punto de la triangulación secuencialmente. Esta implementación maneja las estructuras de datos de forma sencilla (triángulos con punteros a sus vecinos), por lo que es fácil de extender. Además, asegura que las triangulaciones siempre quedan bien definidas, anulando cualquier operación que invalide la triangulación de acuerdo con un criterio de robustez sobre los triángulos. En segundo lugar, se implementa un algoritmo que adapta las triangulaciones para satisfacer restricciones en las aristas, el cual funciona por medio de una idea sencilla que reusa conceptos del algoritmo de Delaunay incremental. En cada iteración se localizan los triángulos que intersectan la arista que se quiere respetar y se intercambian las diagonales secuencialmente hasta que sea respetada. Finalmente, el algoritmo Lepp-Centroide desarrollado por la profesora Rivara y coautores permite obtener una triangulación de buena calidad (ángulo mínimo acotado) por medio de la inserción de nuevos puntos. La implementación de esta memoria se comporta como ha sido establecido en estudios teóricos y prácticos previos, lo que significa que se consigue mejorar la calidad de las triangulaciones insertando pocos puntos y con restricciones geométricas menos fuertes.

Este trabalho apresenta o desenvolvimento de um gerador de malha de elementos finitos baseado no Algoritmo de Refinamento de Delaunay. O pacote é versátil e pode ser aplicado às malhas seriais e adaptativas ou à decomposição de uma malha inicial grossa ou pré-refinada usando processamento paralelo. O algoritmo desenvolvido trabalha com uma entrada de dados na forma de um gráfico de linhas retas planas. A construção do algoritmo de Delaunay foi baseada na técnica de Watson para a triangulação fronteiriça e nos métodos seqüenciais de Ruppert e Shewchuk para o refinamento com paralelismo. A técnica elaborada produz malhas que mantêm as propriedades de uma triangulação de Delaunay. A metodologia apresentada foi implementada utilizando os conceitos de Programação Orientada a Objetos com o auxílio de bibliotecas de código livre. Aproveitando a flexibilidade de algumas dessas bibliotecas acopladas foi possível parametrizar a dimensão do problema, permitindo gerar malhas seqüenciais bidimensionais e tridimensionais. Os resultados das aplicações em malhas seriais, adaptativas e com programação paralela mostram a eficácia desta ferramenta. Uma versão acadêmica do algoritmo de refinamento de Delaunay bidimensional para o Ambiente Mathematica também foi desenvolvido. / This work presents the development of a finite elements mesh generation based on Delaunay Triangulation Algorithm. The package is versatile and applicable to the serial and adaptable meshes or to either the coarse or pre-refined initial mesh decomposition using parallel computing. The developed algorithm works with data input in the form of Planar Straight Line Graphics. The building of the Delaunay Algorithm was based on the Watson\'s technique for the boundary triangulation and in both Ruppert and Shewchuk sequential methods for the parallel refinement. The proposed technique produces meshes maintaining the properties of the Delaunay triangulation. The presented methodology was implemented using the Programming Object-Oriented concepts, which is supported by open source libraries. Taking advantage of the flexibility of some of those coupled libraries the parametrization of the problem dimension was possible, allowing to generate both two and three-dimensional sequential meshes. The results obtained with the applications in serial, adaptive and in parallel meshes have shown the effectiveness of this tool. An academic version of the twodimensional Delaunay refinement algorithm for the Mathematica Environment was also developed.

Este trabalho apresenta o desenvolvimento de um gerador de malha de elementos finitos baseado no Algoritmo de Refinamento de Delaunay. O pacote é versátil e pode ser aplicado às malhas seriais e adaptativas ou à decomposição de uma malha inicial grossa ou pré-refinada usando processamento paralelo. O algoritmo desenvolvido trabalha com uma entrada de dados na forma de um gráfico de linhas retas planas. A construção do algoritmo de Delaunay foi baseada na técnica de Watson para a triangulação fronteiriça e nos métodos seqüenciais de Ruppert e Shewchuk para o refinamento com paralelismo. A técnica elaborada produz malhas que mantêm as propriedades de uma triangulação de Delaunay. A metodologia apresentada foi implementada utilizando os conceitos de Programação Orientada a Objetos com o auxílio de bibliotecas de código livre. Aproveitando a flexibilidade de algumas dessas bibliotecas acopladas foi possível parametrizar a dimensão do problema, permitindo gerar malhas seqüenciais bidimensionais e tridimensionais. Os resultados das aplicações em malhas seriais, adaptativas e com programação paralela mostram a eficácia desta ferramenta. Uma versão acadêmica do algoritmo de refinamento de Delaunay bidimensional para o Ambiente Mathematica também foi desenvolvido. / This work presents the development of a finite elements mesh generation based on Delaunay Triangulation Algorithm. The package is versatile and applicable to the serial and adaptable meshes or to either the coarse or pre-refined initial mesh decomposition using parallel computing. The developed algorithm works with data input in the form of Planar Straight Line Graphics. The building of the Delaunay Algorithm was based on the Watson\'s technique for the boundary triangulation and in both Ruppert and Shewchuk sequential methods for the parallel refinement. The proposed technique produces meshes maintaining the properties of the Delaunay triangulation. The presented methodology was implemented using the Programming Object-Oriented concepts, which is supported by open source libraries. Taking advantage of the flexibility of some of those coupled libraries the parametrization of the problem dimension was possible, allowing to generate both two and three-dimensional sequential meshes. The results obtained with the applications in serial, adaptive and in parallel meshes have shown the effectiveness of this tool. An academic version of the twodimensional Delaunay refinement algorithm for the Mathematica Environment was also developed.