Triangulación de Delaunay

Una triangulación de Delaunay (pronunciado /dəlo'ne/, a veces escrito fonéticamente «Deloné»), es una red de triángulos conexa y convexa que cumple la condición de Delaunay. Esta condición dice que la circunferencia circunscrita de cada triángulo de la red no debe contener ningún vértice de otro triángulo. Las triangulaciones de Delaunay tienen importante relevancia en el campo de la geometría computacional, especialmente en gráficos 3D por computadora.

Triangulación de Delaunay de 10 puntos. El circuncírculo de cada triángulo no contiene vértices en su interior.

Se le denomina así por el matemático ruso Borís Nikolaevich Delone quien lo ideó en 1934;^[1]​ el mismo Delone usó la forma francesa de su apellido, «Delaunay», como apreciación a sus antecesores franceses.

Condición de Delaunay

 

Vértice completamente en el interior de la circunferencia circunscrita. No se cumple la condición de Delaunay

 

Vértice en el exterior de la circunferencia circunscrita. Se cumple la condición de Delaunay

La condición de Delaunay de un triángulo establece que la circunferencia circunscrita del mismo no debe contener ningún otro vértice de la triangulación en su interior, aunque sí se admiten vértices situados sobre la circunferencia.

Se dice que una red de triángulos es una triangulación de Delaunay si todos los triángulos de la misma cumplen la condición de Delaunay. Es decir, que cada circunferencia circunscrita de cada triángulo no contiene vértices de la triangulación en su interior. Esta definición original para espacios bidimensionales se puede ampliar a espacios tridimensionales o incluso dimensiones superiores, usando la esfera circunscrita en vez de la circunferencia circunscrita.

Propiedades de la triangulación de Delaunay

 

Conectando los centros de las circunferencias circunscritas se produce el diagrama de Voronoi (en rojo).

Las triangulación de Delaunay de un conjunto de puntos cumple las siguientes propiedades:

• La frontera externa de triangulación forma la envolvente convexa del conjunto de puntos.
• El ángulo mínimo dentro de todos los triángulos está maximizado, es decir, se evita obtener resultados con ángulos demasiado agudos.
• Como consecuencia de lo anterior, los triángulos generados en una triangulación de Delaunay tienden a ser lo más equiláteros posible. Esto es debido a que todo triángulo no equilátero siempre tiene algún ángulo menor que 60º.
• La triangulación de Delaunay es unívoca salvo en casos donde los vértices presentan una alineación perfecta. Por ejemplo, en caso de los vértices estén situados en una rejilla equidistante, o sean vértices de un polígono regular. En estos casos, aparecerán circunferencias circunscrita con más que tres vértices y será necesario decidir entre varias posibles decisiones.
• El grafo de Gabriel es un subgrafo de las aristas de la triangulación de Delaunay. Es decir, todas las aristas del grafo de Gabriel pertenecen a algún triángulo de la triangulación.
• El grafo del vecino más cercano es un subgrafo de las aristas de la triangulación de Delaunay. Es decir, todas las aristas del grafo del vecino más cercano pertenecen a algún triángulo de la triangulación.
• Como consecuencia de lo anterior, cada punto del conjunto de entrada tendrá una arista que lo une con su punto más cercano.
• La triangulación de Delaunay y el diagrama de Voronoi de una serie de puntos son grafos duales, por lo que la construcción de uno es trivial a partir del otro. En este sentido, los circuncentros de los triángulos de Delaunay coinciden con los vértices de las regiones del diagrama de Voronoi. Dos vértices del diagrama de Voronoi estarán conectados si sus triángulos de Delaunay correspondientes son vecinos entre sí.
• En un grafo construido a partir de las aristas de la triangulación de Delaunay, el camino más corto entre dos puntos nunca será mayor que ${\displaystyle {\frac {4\pi }{3{\sqrt {3}}}}\approx 2.418}$ veces la distancia euclídea entre ellos.

La propiedad de la triangulación de Delaunay de maximizar los ángulos interiores de los triángulos es especialmente práctica en geometría computacional porque evita errores de redondeo que pueden aparecer al realizar cálculos con triangulaciones arbitrarias donde pueden aparecer ángulos demasiado pequeños.

Algoritmos de cálculo de la Triangulación de Delaunay

Existen varias posibles estrategias para calcular la triangulación de Delaunay a partir de un conjunto de puntos de entrada.

Test robusto de pertenencia al interior de una circunferencia

 

Es necesario determinar si el punto D es interior a la circunferencia que pasa por ABC

Vista la definición de la Condición de Delaunay, es importante realizar la comprobación de si un vértice está dentro de una circunferencia circunscrita o no de forma eficiente.

Por supuesto es posible calcular el radio y las coordenadas del circuncentro de la circunferencia circunscrita a un triángulo, y después examinar si el vértice está dentro de la circunferencia calculando la distancia al centro, pero hay un test eficiente basado en el determinante de una matriz.^[2]​^[3]​

En dos dimensiones. Si los tres puntos A, B y C forman un triángulo —con los puntos denominados en sentido contrario al de las agujas del reloj—, el punto D está dentro de su circunferencia circunscrita si y sólo si:

${\displaystyle {\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}={\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\\\end{vmatrix}}>0}$ 

Es decir, si el determinante de este matriz es mayor que 0. En este caso es suficiente conocer el signo aritmético, así que este cómputo puede ser acelerado fácilmente.^[4]​

 

La entrada del problema es una nube de puntos

 

Revisión de la condición de Delaunay tras el cálculo de la solución. Para cada triángulo se muestra el circuncírculo (gris) y sus centro (rojo)

Algoritmo de fuerza bruta

El algoritmo más trivial para calcular la triangulación de Delaunay es mediante una búsqueda de fuerza bruta, que consiste en generar todas las combinaciones posibles de tres puntos del conjunto de entrada, y comprobar si algún otro punto del conjunto de entrada está en el interior de la circunferencia que pasa por dicha terna de puntos. Si la circunferencia no contiene ningún punto, podemos asegurar que la terna forma un triángulo que pertenece a la triangulación de Delaunay. Este algoritmo, aunque de implementación trivial, tiene un orden ${\displaystyle O(n^{4})}$  lo que lo hace inviable salvo que el conjunto de entrada sea de unos pocos puntos.

Algoritmos de giro de aristas

Este algoritmo (o familia de algoritmos) comienza creando una triangulación cualquiera de los puntos de entrada y recorre todas las aristas internas revisando si el par de triángulos adyacentes a la arista cumple la condición de Delaunay de forma aislada. De no ser así, se aplica una operación de giro de arista, de forma que va introduciendo la condición de Delaunay poco a poco en la triangulación. Desafortunadamente, el proceso puede tomar O(n²) giros de arista y solamente está asegurada su convergencia para triangulaciones en 2 dimensiones.^[5]​

La operación de giro de aristas (Flipping)

Para un par de triángulos adyacentes con una arista en común, es posible demostrar que ambos triángulos cumplen la condición de Delaunay si (y sólo si) la suma de los ángulos opuestos a la arista común es menor o igual a 180°.

Esta propiedad nos permite definir una operación geométrica importante denominada Giro de arista (o flipping en inglés). Si los dos triángulos no cumplen la condición de Delaunay, podemos reemplazar la arista común por una nueva arista que una los vértices opuestos a la anterior. El resultado es un nuevo par de triángulos con la misma frontera que el par de triángulos original, pero que sí cumplen la condición de Delaunay.

•  

  Este par de triángulos no cumple la condición de Delaunay.

•  

  El giro de la arista común produce un nuevo par de triángulos que sí cumple la condición de Delaunay.

Algoritmo incremental de Bowyer-Watson

Artículo principal: Algoritmo de Bowyer-Watson

El Algoritmo de Bowyer-Watson es un método incremental donde se añaden los vértices a una triangulación de Delaunay trivial que es corregida en cada paso para mantener la condición de Delaunay.

Hay varias posibilidades para seleccionar el vértice siguiente, incidentalmente, ordenado por una coordenada o usando un árbol. La selección del vértice siguiente tiene una gran influencia en el tiempo de ejecución del algoritmo.

Algoritmos de barrido o Sweepline

Existe un algoritmo de tipo barrido (sweepline en inglés) publicado en 2005 por Borut Žalik para calcular directamente la triaángulación de Delaunay. ^[6]​ Se basa en un principio similar a la construcción incremental: construir una pequeña parte de la triangulación final y después seguir añadiendo vértices en el orden en que son barridos por una recta hasta que la triangulación esté completa.

El algoritmo de Fortune es otro algoritmo de tipo barrido (sweepline en inglés) publicado por Steven Fortune en 1986 para calcular el diagrama de Voronoi, del cual puede extraerse fácilmente la triangulación de Delaunay. ^[7]​

Algoritmo recursivo Divide y venceras

Este algoritmo usa el principio conocido como divide y vencerás (divide and conquer en inglés): dividir el conjunto de puntos en dos partes de igual tamaño, calcular la triangulación de Delaunay para cada parte individualmente y después reunir las dos triangulaciones corrigiendo los errores.

La idea de usar el principio divide y vencerás para computar un diagrama de Voronoi en dos dimensiones fue introducida en 1975.^[8]​ La idea fue revisada en 1980 para computar la triangulación de Delaunay^[9]​ y mejorada por Guibas y Stolfi in 1985.^[10]​ En 1986 Dwyer presentó una modificación que mejoró la cota ajustada asintótica^[11]​ y en 1992 Leach presentó otra aceleración del método.^[12]​ En 1997 Cigoni, Montani y Scopigno presentaron el algoritmo DeWall, que hace posible el cálculo de una triangulación de Delaunay usando divide and conquer para cualquier número de dimensiones.^[13]​

Usando el algoritmo más avanzado, ese método resulta en una cota superior asintótica de O(n log n)^[12]​ y una cota ajustada asintótica de O(n log (log n)); en algunos casos especiales es posible reducir la cota ajustada a la cota superior. Se ha demostrado que la técnica divide y vencerás es la más rápida en generar la triangulación de Delaunay.^[14]​^[15]​

Enlaces externos

• UNSW Engineering - School of Computer Science and Engineering, Austria: Delaunay Triangulation Algorithms — applet Java que demuestra los algoritmos Incremental construction, Gift wrap, Divide and conquer y QuickHull (en inglés)
• Prof. David Eppstein, University of California, Irvine: Geometry in action - Delaunay triangulation — aplicaciones de la triangulación de Delaunay en geometría por computadora (en inglés)
• Universidad Politécnica de Madrid - Departamento de Matemática Aplicada: Geometría Computacional — varios applets que demuestran la triangulación de Delaunay y diagramas de Voronoi
• Grima, Clara (17 de abril de 2014). «Me gustan los triángulos». Consultado el 1 de marzo de 2017. 

Fuentes

1. B. Delaunay: Sur la sphere vide. A la mémoire de Georges Voronoi. Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk (Bulletin of Academy of Sciences of the USSR), 7, págs. 793-800, 1934
2. Guibas, Leonidas; Stolfi, Jorge (1985). «Primitives for the manipulation of general subdivisions and the computation of Voronoi». ACM Transactions on Graphics 4 (2): 74-123. doi:10.1145/282918.282923. 
3. Jonathan Richard Shewchuk: Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry.
4. Jonathan Richard Shewchuk: 18:305-363, 1997
5. Hurtado, F.; M. Noy; J. Urrutia (1999). «Flipping Edges in Triangulations». Discrete & Computational Geometry 22 (3). pp. 333-346. doi:10.1007/PL00009464. 
6. Žalik, Borut (2005). «An efficient sweep-line Delaunay triangulation algorithm». Computer-Aided Design 37 (10): 1027-1038. doi:10.1016/j.cad.2004.10.004. 
7. Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313–322. 1986. ISBN 0-89791-194-6. ACM Digital LibrarySpringerLink
8. Shamos, Michael; Hoey, Dan (1975). «Closest-point problems». Proceedings of the 16th Annual Symposium on Foundations of Computer Science: 151-162. doi:10.1109/SFCS.1975.8. 
9. D. T. Lee, B. Schachter: Two Algorithms for Constructing Delaunay Triangulations. In International Journal of Computer Information Sciences, 9(3):219-242, 1980
10. L. Guibas, J. Stolfi: Primitives for the Manipulation of General Subdivisions and the Computation of Vornoi Diagrams. In ACM Transactions on Graphics, 4:74-123, April 1985
11. R. A. Dwyer: A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time. In Proceedings of the second annual symposium on Computational geometry, págs. 276-284, 1986
12. G. Leach: June 1992
13. P. Cignoni, C. Montani, R. Scopigno: DeWall: A Fast Divide And Conquer Delaunay Triangulation Algorithm in E^d. October 1997
14. A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf
15. Shewchuk, Jonathan Richard (1996). «Triangulation Algorithms and Data Structures». Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. Consultado el 24 de febrero de 2017. 

•   Datos: Q192445
•   Multimedia: Delaunay triangulation