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.

El objetivo general de esta memoria es extender y mejorar una herramienta interactiva gráfica que permite al usuario definir y visualizar el proceso de generación de mallas geométricas en dos dimensiones, agregándole nuevos algoritmos de refinamiento de mallas, nuevas funcionalidades y mejorando las existentes. Inicialmente se tiene una aplicación que tiene la funcionalidad de mostrar y procesar una malla en dos dimensiones con un algoritmo de refinamiento/mejoramiento dado con ciertos criterios definidos por el usuario. Luego de analizar la aplicación existente, se decide rediseñar una parte de sus procesos, considerando características en su diseño como extensibilidad, y modularidad. Se decide hacer una interfaz para el usuario, desde cero, la que comunica con la nueva aplicación. Se agregan nuevas funcionalidades a la aplicación, tal como la selección de regiones para su posterior refinamiento. Un nuevo algoritmo de refinamiento es agregado a la aplicación. Como resultado se tiene una herramienta para visualizar y manejar mallas geométricas en dos dimensiones, que es poderosa, extensible, flexible y simple de usar, junto con nuevas funcionalidades y algoritmos, con respecto de la aplicación original.