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.
Se le denomina así por el matemático ruso Borís Nikolaevich Delone quien lo ideó en 1934; el mismo Delone usó la forma francesa de su apellido, «Delaunay», como apreciación a sus antecesores franceses.
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.
Las triangulación de Delaunay de un conjunto de puntos cumple las siguientes propiedades:
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.
Existen varias posibles estrategias para calcular la triangulación de Delaunay a partir de un conjunto de puntos de entrada.
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.
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 lo que lo hace inviable salvo que el conjunto de entrada sea de unos pocos puntos.
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.
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.
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.
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. 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.
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. La idea fue revisada en 1980 para computar la triangulación de Delaunay y mejorada por Guibas y Stolfi in 1985. En 1986 Dwyer presentó una modificación que mejoró la cota ajustada asintótica y en 1992 Leach presentó otra aceleración del método. 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.
Usando el algoritmo más avanzado, ese método resulta en una cota superior asintótica de O(n log n) 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.