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]

Los vértices en el interior de los círculos indican que no 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.

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 original, pero que sí cumplen la condición de Delaunay.


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 triangulo 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.
  • 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 cuando se tiene el 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í.

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]

Nube de puntos de entrada
Revisión de la condición de Delaunay. Para cada triángulo se muestra el circuncírculo (gris) y sus centro (rojo)

Test de pertenencia al interior de una circunferencia[editar]

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.

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.[2]

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

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

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. Jonathan Richard Shewchuk: Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. In Discrete & Computational Geometry, 18:305-363, 1997
  3. M. I. Shamos, D. Hoey: Closest-point problems. In Proceedings of the 16th IEEE Symposium on Foundations of Computer Science, págs. 151-162, 1975
  4. D. T. Lee, B. Schachter: Two Algorithms for Constructing Delaunay Triangulations. In International Journal of Computer Information Sciences, 9(3):219-242, 1980
  5. 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
  6. 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
  7. a b G. Leach: Improving Worst-Case Optimal Delaunay Triangulation Algorithms. June 1992
  8. P. Cignoni, C. Montani, R. Scopigno: DeWall: A Fast Divide And Conquer Delaunay Triangulation Algorithm in Ed. October 1997
  9. A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf
  10. 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.