Implementación de una Biblioteca de Triangulación de Polígonos Basada en el Algoritmo LEPP Delaunay

Abstract

Las mallas de triángulos son ampliamente utilizadas en aplicaciones científicas e ingeniería. Una triangulación de un conjunto de puntos puede construirse utilizando diversos algoritmos, pero usualmente se prefiere aquellos que además de ser eficientes en tiempo y espacio, entreguen triángulos cuyo menor ángulo se encuentre sobre cierta cota.

La triangulación de Delaunay de un conjunto de puntos maximiza el ángulo mínimo de todos los triángulos de la triangulación. Sin embargo, el ángulo mínimo en una triangulación de Delaunay puede ser menor que el valor requerido en una aplicación dada.

Existen métodos de refinamiento de triangulaciones basados en la inserción de nuevos puntos en la malla que incrementalmente mejoran el ángulo mínimo de una triangulación. De especial interés es la familia de métodos de refinamiento basados LEPP, que recorren los triángulos de una malla a través de las aristas más largas de los triángulos.

El uso de los métodos de refinamiento basados en LEPP-Delaunay en aplicaciones, requiere la implementación de estructuras de datos para la representación de la malla, primitivas geométricas, algoritmos de triangulación y algoritmos de manipulación de los datos. El costo de escribir una aplicación desde cero se eleva al considerar los requisitos anteriormente mencionados.

El presente informe describe la implementación de una biblioteca reusable y general que ofrece la funcionalidad de los métodos LEPP-Delaunay. De esta manera, es posible crear aplicaciones que utilicen dichos métodos sin la necesidad de invertir tiempo de desarrollo en los algoritmos y estructuras de datos asociadas. En otras palabras, el foco del desarrollo puede estar completamente en la aplicación de los métodos

LEPP-Delaunay y no en sus detalles de implementación.

La biblioteca LEPP-Delaunay fue construida utilizando las estructuras de datos de OpenMesh, proyecto que ofrece una implementación extensible y flexible de la representación de una malla en base a la estructura de datos halfedge.

Para mostrar las capacidades de la biblioteca LEPP-Delaunay se implementó una herramienta gráfica para el análisis de mallas que hace uso de la funcionalidad provista por la biblioteca LEPP-Delaunay.