Triangulación de Delaunay

En geometría computacional , una triangulación de Delaunay o triangulación de Delone de un conjunto de puntos en el plano subdivide su envoltura convexa ^[1] en triángulos cuyos círculos circunscritos no contienen ninguno de los puntos. Esto maximiza el tamaño del ángulo más pequeño en cualquiera de los triángulos y tiende a evitar los triángulos de astillas .

La triangulación recibe su nombre de Boris Delaunay por su trabajo sobre ella en 1934. ^[2]

Si todos los puntos se encuentran sobre una línea recta, la noción de triangulación se vuelve degenerada y no hay triangulación de Delaunay. Para cuatro o más puntos sobre el mismo círculo (por ejemplo, los vértices de un rectángulo), la triangulación de Delaunay no es única: cada una de las dos triangulaciones posibles que dividen el cuadrángulo en dos triángulos satisface la "condición de Delaunay", es decir, el requisito de que los círculos circunscritos de todos los triángulos tengan interiores vacíos.

Al considerar esferas circunscritas, el concepto de triangulación de Delaunay se extiende a tres dimensiones y más. Es posible generalizar a otras métricas distintas de la distancia euclidiana . Sin embargo, en estos casos no se garantiza que exista una triangulación de Delaunay ni que sea única.

Relación con el diagrama de Voronoi

La triangulación de Delaunay de un conjunto de puntos discretos $P$ en posición general corresponde al grafo dual del diagrama de Voronoi para $P$ . Los circuncentros de los triángulos de Delaunay son los vértices del diagrama de Voronoi. En el caso 2D, los vértices de Voronoi están conectados a través de aristas, que pueden derivarse de las relaciones de adyacencia de los triángulos de Delaunay: Si dos triángulos comparten una arista en la triangulación de Delaunay, sus circuncentros deben estar conectados con una arista en la teselación de Voronoi.

Los casos especiales en los que esta relación no se cumple o es ambigua incluyen casos como:

Tres o más puntos colineales , donde los círculos circunscritos son de radios infinitos .
Cuatro o más puntos en un círculo perfecto, donde la triangulación es ambigua y todos los circuncentros son trivialmente idénticos.
Las aristas del diagrama de Voronoi que van al infinito no están definidas por esta relación en el caso de un conjunto finito $P$ . Si la triangulación de Delaunay se calcula utilizando el algoritmo de Bowyer-Watson , entonces los circuncentros de los triángulos que tienen un vértice común con el "super" triángulo deben ignorarse. Las aristas que van al infinito comienzan desde un circuncentro y son perpendiculares a la arista común entre el triángulo conservado y el ignorado.

d-Delaunay dimensional

Para un conjunto $P$ de puntos en el espacio euclidiano ( $d$ -dimensional) , una triangulación de Delaunay es una triangulación $DT($ $P$ $)$ tal que ningún punto en $P$ está dentro de la circunhiperesfera de ningún $d$ - símplex en $DT($ $P$ $)$ . Se sabe ^[2] que existe una única triangulación de Delaunay para $P$ si $P$ es un conjunto de puntos en posición general ; es decir, la envoltura afín de $P$ es $d$ -dimensional y ningún conjunto de $d$ $+ 2$ puntos en $P$ se encuentra en el límite de una bola cuyo interior no interseca $a P.$

El problema de encontrar la triangulación de Delaunay de un conjunto de puntos en un espacio euclidiano de dimensión $d$ se puede convertir en el problema de encontrar la envoltura convexa de un conjunto de puntos en un espacio de dimensión ( $d$ $+ 1$ ). Esto se puede hacer dando a cada punto $p$ una coordenada adicional igual a $|$ $p$ $|$ $2$ , convirtiéndolo así en un hiperparaboloide (esto se denomina "elevación"); tomando el lado inferior de la envoltura convexa (ya que la tapa del extremo superior mira hacia arriba alejándose del origen y debe descartarse); y mapeando de nuevo al espacio de dimensión $d$ eliminando la última coordenada. Como la envoltura convexa es única, también lo es la triangulación, asumiendo que todas las facetas de la envoltura convexa son símplices . Las facetas no simpliciales solo ocurren cuando $d$ $+ 2$ de los puntos originales se encuentran en la misma hiperesfera d $,$ es decir, los puntos no están en posición general. ^[3]

Propiedades

Sea $n$ el número de puntos y $d$ el número de dimensiones.

La unión de todos los símplices en la triangulación es la envoltura convexa de los puntos.
La triangulación de Delaunay contiene ⁠ ⁠ $\textstyle O{\bigl (}n^{\lceil d/2\rceil }{\bigr )}$ símplices. ^[4]
En el plano ( $d = 2$ ), si hay $b$ vértices en la envoltura convexa, entonces cualquier triangulación de los puntos tiene como máximo $2 n - 2 - b$ triángulos, más una cara exterior (véase característica de Euler ).
Si los puntos se distribuyen según un proceso de Poisson en el plano con intensidad constante, entonces cada vértice tiene en promedio seis triángulos circundantes. De manera más general, para el mismo proceso en $d$ dimensiones, el número promedio de vecinos es una constante que depende únicamente de $d$ . ^[5]
En el plano, la triangulación de Delaunay maximiza el ángulo mínimo. Comparada con cualquier otra triangulación de puntos, el ángulo más pequeño en la triangulación de Delaunay es al menos tan grande como el ángulo más pequeño en cualquier otra. Sin embargo, la triangulación de Delaunay no necesariamente minimiza el ángulo máximo. ^[6] La triangulación de Delaunay tampoco minimiza necesariamente la longitud de las aristas.
Un círculo que circunscribe cualquier triángulo de Delaunay no contiene ningún otro punto de entrada en su interior.
Si un círculo que pasa por dos de los puntos de entrada no contiene ningún otro punto de entrada en su interior, entonces el segmento que conecta los dos puntos es un borde de una triangulación de Delaunay de los puntos dados.
Cada triángulo de la triangulación de Delaunay de un conjunto de puntos en espacios $d$ -dimensionales corresponde a una faceta de la envoltura convexa de la proyección de los puntos sobre un paraboloide ( $d + 1$ )-dimensional , y viceversa.
El vecino más cercano $b$ a cualquier punto $p$ está en un borde $bp$ en la triangulación de Delaunay ya que el gráfico del vecino más cercano es un subgrafo de la triangulación de Delaunay.
La triangulación de Delaunay es una llave geométrica : en el plano ( $d = 2$ ), se sabe que el camino más corto entre dos vértices, a lo largo de los bordes de Delaunay, no es mayor que 1,998 veces la distancia euclidiana entre ellos. ^[7]

Definición visual de Delaunay: volteo

De las propiedades anteriores surge una característica importante: mirando dos triángulos $△ ABD, △ BCD$ con el borde común $BD$ (ver figuras), si la suma de los ángulos $α + γ \leq 180°$ , los triángulos cumplen la condición de Delaunay.

Esta es una propiedad importante porque permite el uso de una técnica de inversión . Si dos triángulos no cumplen la condición de Delaunay, al cambiar la arista común $BD$ por la arista común $AC$ se obtienen dos triángulos que sí cumplen la condición de Delaunay:

Esta triangulación no cumple la condición de Delaunay (la suma de $α$ y $γ$ es mayor que 180°).
Este par de triángulos no cumple la condición de Delaunay (hay un punto dentro del interior del círculo circunscrito).
Al invertir el borde común se obtiene una triangulación de Delaunay válida para los cuatro puntos.

Esta operación se llama flip y puede generalizarse a tres dimensiones y más. ^[8]

Algoritmos

Muchos algoritmos para calcular triangulaciones de Delaunay se basan en operaciones rápidas para detectar cuándo un punto se encuentra dentro del círculo circunscrito de un triángulo y en una estructura de datos eficiente para almacenar triángulos y aristas. En dos dimensiones, una forma de detectar si el punto $D$ se encuentra en el círculo circunscrito de $A, B, C$ es evaluar el determinante : ^[9]

{\begin{aligned}&{\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}}\\[8pt]={}&{\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\end{alineado}}

Cuando $A, B, C$ se ordenan en sentido antihorario , este determinante es positivo solo si $D$ se encuentra dentro del círculo circunscrito.

Algoritmos de inversión

Como se mencionó anteriormente, si un triángulo no es Delaunay, podemos invertir uno de sus bordes. Esto conduce a un algoritmo sencillo: construir cualquier triangulación de los puntos y luego invertir los bordes hasta que ningún triángulo sea no Delaunay. Desafortunadamente, esto puede requerir $Ω(n 2)$ inversiones de bordes. ^[10] Si bien este algoritmo se puede generalizar a tres dimensiones y dimensiones superiores, su convergencia no está garantizada en estos casos, ya que está condicionado a la conectividad del gráfico de inversión subyacente : este gráfico está conectado para conjuntos de puntos bidimensionales, pero puede estar desconectado en dimensiones superiores. ^[8]

Incremental

La forma más sencilla de calcular de manera eficiente la triangulación de Delaunay es agregar repetidamente un vértice a la vez, retriangulando las partes afectadas del grafo. Cuando se agrega un vértice $v$ , dividimos en tres el triángulo que contiene $v$ y luego aplicamos el algoritmo de volteo. Si lo hacemos de manera ingenua, esto tomará $O(n)$ tiempo: buscamos entre todos los triángulos para encontrar el que contiene $v$ y luego potencialmente volteamos todos los triángulos. Entonces, el tiempo de ejecución total es $O(n 2)$ .

Si insertamos vértices en orden aleatorio, resulta (mediante una prueba algo intrincada) que cada inserción volteará, en promedio, solo $O(1)$ triángulos, aunque a veces volteará muchos más. ^[11] Esto aún deja el tiempo de ubicación del punto para mejorar. Podemos almacenar el historial de las divisiones y volteretas realizadas: cada triángulo almacena un puntero a los dos o tres triángulos que lo reemplazaron. Para encontrar el triángulo que contiene $v$ , comenzamos en un triángulo raíz y seguimos el puntero que apunta a un triángulo que contiene $v$ , hasta que encontramos un triángulo que aún no ha sido reemplazado. En promedio, esto también tomará $O(log n)$ tiempo. Sobre todos los vértices, entonces, esto toma $O(n log n)$ tiempo. ^[12] Si bien la técnica se extiende a dimensiones superiores (como lo demostraron Edelsbrunner y Shah ^[13] ), el tiempo de ejecución puede ser exponencial en la dimensión incluso si la triangulación de Delaunay final es pequeña.

El algoritmo Bowyer-Watson ofrece otro enfoque para la construcción incremental. Ofrece una alternativa a la inversión de aristas para calcular los triángulos de Delaunay que contienen un vértice recién insertado.

Desafortunadamente, los algoritmos basados en volteretas son generalmente difíciles de paralelizar, ya que agregar un punto determinado (por ejemplo, el punto central de una rueda de carreta) puede llevar a hasta $O(n)$ volteretas consecutivas. Blelloch et al. ^[14] propusieron otra versión del algoritmo incremental basado en rip-and-tent, que es práctico y altamente paralelizado con span polilogarítmico .

Divide y vencerás

Lee y Schachter desarrollaron un algoritmo de división y conquista para triangulaciones en dos dimensiones, que fue mejorado por Guibas y Stolfi ^[9]^[15] y, más tarde, por Dwyer ^[16] . En este algoritmo, se dibuja recursivamente una línea para dividir los vértices en dos conjuntos. Se calcula la triangulación de Delaunay para cada conjunto y, a continuación, se fusionan los dos conjuntos a lo largo de la línea divisoria. Con algunos trucos ingeniosos, la operación de fusión se puede realizar en un tiempo $O(n)$ , por lo que el tiempo total de ejecución es $O(n log n)$ . ^[17]

Para ciertos tipos de conjuntos de puntos, como una distribución aleatoria uniforme, al seleccionar inteligentemente las líneas de división, el tiempo esperado se puede reducir a $O(n log log n)$ mientras se mantiene el rendimiento en el peor de los casos.

En "DeWall: A fast divide and acquire Delaunay triangulation algorithm in E ^d " de P. Cignoni, C. Montani y R. Scopigno se presenta un paradigma de "dividir y vencer" para realizar una triangulación en $d dimensiones.$ ^[18]

Se ha demostrado que el algoritmo de dividir y vencer es la técnica de generación de DT más rápida a nivel secuencial. ^[19]^[20]

Casco de barrido

Sweephull ^[21] es una técnica híbrida para la triangulación de Delaunay 2D que utiliza una envoltura de barrido que se propaga radialmente y un algoritmo de inversión. La envoltura de barrido se crea de forma secuencial iterando un conjunto de puntos 2D ordenados radialmente y conectando triángulos a la parte visible de la envoltura convexa, lo que da una triangulación sin superposición. Se puede construir una envoltura convexa de esta manera siempre que el orden de los puntos garantice que ningún punto caiga dentro del triángulo. Pero la ordenación radial debería minimizar la inversión al ser altamente Delaunay para empezar. Esto se combina luego con un paso final iterativo de inversión de triángulos.

Aplicaciones

El árbol de expansión mínimo euclidiano de un conjunto de puntos es un subconjunto de la triangulación de Delaunay de los mismos puntos, ^[22] y esto se puede aprovechar para calcularlo de manera eficiente.

Para modelar terrenos u otros objetos a partir de una nube de puntos , la triangulación de Delaunay proporciona un conjunto de triángulos muy útil para utilizar como polígonos en el modelo. En particular, la triangulación de Delaunay evita los triángulos estrechos (ya que tienen circunferencias circunscritas grandes en comparación con su área). Véase red irregular triangulada .

Las triangulaciones de Delaunay se pueden utilizar para determinar la densidad o intensidad de muestreos de puntos mediante el estimador de campo de teselación de Delaunay (DTFE) .

Las triangulaciones de Delaunay se utilizan a menudo para generar mallas para solucionadores discretizados en el espacio, como el método de elementos finitos y el método de volumen finito de simulación física, debido a la garantía de ángulos y porque se han desarrollado algoritmos de triangulación rápidos. Normalmente, el dominio que se va a mallar se especifica como un complejo simplicial grueso ; para que la malla sea numéricamente estable, debe refinarse, por ejemplo, utilizando el algoritmo de Ruppert .

La creciente popularidad de las técnicas del método de elementos finitos y del método de elementos de contorno aumenta el incentivo para mejorar los algoritmos de mallado automático. Sin embargo, todos estos algoritmos pueden crear elementos de malla distorsionados e incluso inutilizables. Afortunadamente, existen varias técnicas que pueden tomar una malla existente y mejorar su calidad. Por ejemplo, el suavizado (también conocido como refinamiento de malla) es uno de esos métodos, que reposiciona los nodos para minimizar la distorsión de los elementos. El método de malla estirada permite la generación de mallas pseudoregulares que cumplen con los criterios de Delaunay de manera fácil y rápida en una solución de un solo paso.

La triangulación de Delaunay restringida ha encontrado aplicaciones en la planificación de rutas en la conducción automatizada y en la topografía. ^[23]

Véase también

Esqueleto beta
Teselación de Voronoi centroidal
Algoritmos de envoltura convexa
El refinamiento de Delaunay
Conjunto Delone : también conocido como conjunto Delaunay
Hiperuniformidad desordenada
Recorrido más lejano primero : inserción incremental de Voronoi
Gráfico de Gabriel
Calzada del Gigante
Análisis de patrones de gradiente
Límite de Hamming – límite de empaquetamiento de esferas
Algoritmo de Linde-Buzo-Gray
Algoritmo de Lloyd : iteración de Voronoi
Conjunto Meyer
Número de Pisot–Vijayaraghavan
Triangulación de Pitteway
Plesioedro
Cuasicristal
Cuasitriangulación
Número de Salem
Punto de Steiner (triángulo)
Malla triangular
Gráfico de Urquhart
Diagrama de Voronoi

Referencias

^ En términos generales, se trata de la región que una banda elástica estirada alrededor de los puntos encerraría.
^ ab Delaunay, Boris (1934). "Sur la sphère vide" [Sobre la esfera vacía]. Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles (en francés). 6 : 793–800.
^ Fukuda, Komei . "Preguntas frecuentes sobre computación poliédrica". www.cs.mcgill.ca . Consultado el 29 de octubre de 2018 .
^ Seidel, Raimund (1995). "El teorema del límite superior para politopos: una demostración sencilla de su versión asintótica". Geometría computacional . 5 (2): 115–116. doi :10.1016/0925-7721(95)00013-Y.
^ Meijering, JL (1953). "Área de interfaz, longitud de arista y número de vértices en agregados cristalinos con nucleación aleatoria" (PDF) . Philips Research Reports . 8 : 270–290. Archivado desde el original (PDF) el 8 de marzo de 2017.Según lo citado por Dwyer, Rex A. (1991). "Diagramas de Voronoĭ de dimensiones superiores en tiempo esperado lineal". Geometría discreta y computacional . 6 (4): 343–367. doi : 10.1007/BF02574694 . MR 1098813.
^ Edelsbrunner, Herbert ; Tan, Tiow Seng; Waupotitsch, Roman (1992). "Un algoritmo de tiempo O(n2 log n) para la triangulación de ángulos minmax" (PDF) . Revista SIAM sobre computación científica y estadística . 13 (4): 994–1008. CiteSeerX 10.1.1.66.2895 . doi :10.1137/0913058. MR 1166172. Archivado desde el original (PDF) el 2017-02-09 . Consultado el 2017-10-24 . .
^ Xia, Ge (2013). "El factor de estiramiento de la triangulación de Delaunay es menor que 1,998". Revista SIAM de Computación . 42 (4): 1620–1659. arXiv : 1103.4361 . doi :10.1137/110832458. MR 3082502. S2CID 6646528.
^ ab De Loera, Jesús A. ; Rambau, Jörg; Santos, Francisco (2010). Triangulaciones, estructuras para algoritmos y aplicaciones . Algoritmos y computación en matemáticas. Vol. 25. Springer.
^ ab Guibas, Leonidas ; Stolfi, Jorge (1985). "Primitivas para la manipulación de subdivisiones generales y el cálculo de Voronoi". ACM Transactions on Graphics . 4 (2): 74–123. doi : 10.1145/282918.282923 . S2CID 52852815.
^ Hurtado, F. ; Noy, M.; Urrutia, J. (1999). "Inversión de aristas en triangulaciones". Geometría discreta y computacional . 22 (3): 333–346. doi : 10.1007/PL00009464 .
^ Guibas, Leonidas J. ; Knuth, Donald E. ; Sharir, Micha (1992). "Construcción incremental aleatoria de diagramas de Delaunay y Voronoi". Algorithmica . 7 (1–6): 381–413. doi :10.1007/BF01758770. S2CID 3770886.
^ de Berg, Marcos; Otfried Cheong ; Marc van Kreveld; Mark Overmars (2008). Geometría computacional: algoritmos y aplicaciones (PDF) . Springer-Verlag. ISBN 978-3-540-77973-5Archivado desde el original (PDF) el 28 de octubre de 2009. Consultado el 23 de febrero de 2010 .
^ Edelsbrunner, Herbert ; Shah, Nimish (1996). "La inversión topológica incremental funciona para triangulaciones regulares". Algorithmica . 15 (3): 223–241. doi :10.1007/BF01975867. S2CID 12976796.
^ Blelloch, Guy; Gu, Yan; Shun, Julian; y Sun, Yihan. Paralelismo en algoritmos incrementales aleatorios Archivado el 25 de abril de 2018 en Wayback Machine . SPAA 2016. doi:10.1145/2935764.2935766.
^ Peterson, Samuel. "CÁLCULO DE TRIANGULACIONES DE DELAUNAY CON RESTRICCIONES EN EL PLANO". www.geom.uiuc.edu . Archivado desde el original el 22 de septiembre de 2017 . Consultado el 25 de abril de 2018 .
^ Dwyer, Rex A. (noviembre de 1987). "Un algoritmo de divide y vencerás más rápido para construir triangulaciones de Delaunay". Algorithmica . 2 (1–4): 137–151. doi :10.1007/BF01840356. S2CID 10828441.
^ Leach, G. (junio de 1992). "Mejora de los algoritmos de triangulación de Delaunay óptimos en el peor de los casos". 4.ª Conferencia canadiense sobre geometría computacional . CiteSeerX 10.1.1.56.2323 .
^ Cignoni, P.; C. Montani; R. Scopigno (1998). "DeWall: Un algoritmo de triangulación de Delaunay rápido de divide y vencerás en E ^d ". Diseño asistido por computadora . 30 (5): 333–341. doi :10.1016/S0010-4485(97)00082-1.
^ Comparación de algoritmos de triangulación secuencial de Delaunay "Copia archivada" (PDF) . Archivado desde el original (PDF) el 8 de marzo de 2012 . Consultado el 18 de agosto de 2010 .{{cite web}}: CS1 maint: copia archivada como título ( enlace )
^ "Algoritmos de triangulación y estructuras de datos". www.cs.cmu.edu . Archivado desde el original el 10 de octubre de 2017 . Consultado el 25 de abril de 2018 .
^ "S-hull" (PDF) . s-hull.org . Archivado (PDF) del original el 27 de octubre de 2013 . Consultado el 25 de abril de 2018 .
^ Franz Aurenhammer; Rolf Klein; Der-tsai Lee (26 de junio de 2013). Diagramas de Voronoi y triangulaciones de Delaunay. World Scientific Publishing Company. pp. 197–. ISBN 978-981-4447-65-2.
^ Sterling J Anderson; Sisir B. Karumanchi; Karl Iagnemma (5 de julio de 2012). "Planificación y control basados en restricciones para el funcionamiento seguro y semiautónomo de vehículos" (PDF) . Simposio sobre vehículos inteligentes IEEE 2012. IEEE. doi :10.1109/IVS.2012.6232153. Archivado desde el original (PDF) el 28 de febrero de 2019. Consultado el 27 de febrero de 2019 .

Enlaces externos

Triangulación de Delaunay en CGAL , la biblioteca de algoritmos de geometría computacional:
- Mariette Yvinec . Triangulación 2D. Recuperado en abril de 2010.
- Pion, Sylvain; Teillaud, Monique . Triangulaciones 3D. Recuperado en abril de 2010.
- Horno, Samuel; Devillers, Olivier; Jamín, Clemente. dD Triangulaciones.
- Hert, Susan; Seel, Michael. dD Convex Hulls and Delaunay Triangulations. Recuperado en abril de 2010.
"Poly2Tri: triangulación de Delaunay incremental con restricciones. Implementación en C++ de código abierto. Consultado en abril de 2019.
"Construcción de triangulación de Delaunay con el método Divide & Conquer". Implementación de código abierto C99. Consultado en abril de 2019.
"CDT: Triangulación de Delaunay restringida en C++". Implementación de código abierto en C++. Consultado en agosto de 2022.