Triangulación de Delaunay

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Triangulación de Delaunay de 10 puntos. El circuncírculo de cada triángulo no contiene vértices en su interior.

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.

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[editar]

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[editar]

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 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 triangulo 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 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[editar]

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[editar]

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:

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[editar]

El algoritmo mas 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 lo que lo hace inviable salvo que el conjunto de entrada sea de unos pocos puntos.

Algoritmos de giro de aristas[editar]

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(n2) giros de arista y solamente está asegurada su convergencia para triangulaciones en 2 dimensiones.[5]

La operación de giro de aristas (Flipping)[editar]

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.

Algoritmo incremental de Bowyer-Watson[editar]

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.

Algoritmo de barrido o Sweepline[editar]

El algoritmo de barrido (sweepline en inglés) 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 hasta que la triangulación esté completa. La diferencia estriba en que no hay que corregir ningún de los errores que pudieran presentarse.

Algoritmo recursivo Divide y venceras[editar]

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.[6]​ La idea fue revisada en 1980 para computar la triangulación de Delaunay[7]​ y mejorada por Guibas y Stolfi in 1985.[8]​ En 1986 Dwyer presentó una modificación que mejoró la cota ajustada asintótica[9]​ y en 1992 Leach presentó otra aceleración del método.[10]​ 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.[11]

Usando el algoritmo más avanzado, ese método resulta en una cota superior asintótica de O(n log n)[10]​ 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.[12][13]

Enlaces externos[editar]

Fuentes[editar]

  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: Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. In Discrete & Computational Geometry, 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. 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. 
  7. D. T. Lee, B. Schachter: Two Algorithms for Constructing Delaunay Triangulations. In International Journal of Computer Information Sciences, 9(3):219-242, 1980
  8. 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
  9. 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
  10. a b G. Leach: Improving Worst-Case Optimal Delaunay Triangulation Algorithms. June 1992
  11. P. Cignoni, C. Montani, R. Scopigno: DeWall: A Fast Divide And Conquer Delaunay Triangulation Algorithm in Ed. October 1997
  12. A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf
  13. 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.