Triangulación de Delaunay

Una triangulación de Delaunay en el avión con los círculos mostrados

En matemáticas y geometría computacional, una triangulación de Delaunay (también conocida como triangulación de Delone) para un conjunto dado P de puntos discretos en una posición general es una triangulación DT(P) tal que ningún punto en P está dentro del círculo circunscrito de ningún triángulo en DT(P). Las triangulaciones de Delaunay maximizan el mínimo de todos los ángulos de los triángulos en la triangulación; tienden a evitar los triángulos de astilla. La triangulación lleva el nombre de Boris Delaunay por su trabajo sobre este tema desde 1934.

Para un conjunto de puntos en la misma línea no existe la triangulación de Delaunay (la noción de triangulación es degenerada para este caso). Para cuatro o más puntos en 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 cuadrilátero en dos triángulos satisface la "condición de Delaunay", es decir, el requisito de que los circuncírculos de todos los triángulos tengan interiores vacíos.

Al considerar esferas circunscritas, la noción de triangulación de Delaunay se extiende a tres dimensiones o más. Las generalizaciones son posibles para métricas distintas de la distancia euclidiana. Sin embargo, en estos casos no se garantiza que exista o sea única una triangulación de Delaunay.

Relación con el diagrama de Voronoi

La triangulación Delaunay con todos los círculos y sus centros (en rojo).

Conectar los centros de los círculos produce el diagrama Voronoi (en rojo).

La triangulación de Delaunay de un conjunto discreto de puntos P en posición general corresponde al gráfico 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 se conectarán 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 collineales, donde los círculos son de radio infinito.
• Cuatro o más puntos en un círculo perfecto, donde la triangulación es ambigua y todos los circuncentros son trivialmente idénticos.
• Los bordes del diagrama de Voronoi que va a la infinidad no se definen por esta relación en caso de un conjunto finito P. Si la triangulación Delaunay se calcula utilizando el algoritmo Bowyer-Watson entonces los circumcenters de triángulos que tienen un vértice común con el triángulo "super" deben ser ignorados. Los bordes que van a la infinidad comienzan desde un circumcenter y son perpendiculares al borde común entre el triángulo mantenido e ignorado.

D-dimensional Delaunay

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 circun-hiperesfera de cualquier d-simplex en DT(P). Se sabe que existe una única triangulación de Delaunay para P si P es un conjunto de puntos en posición general; es decir, el casco afín de P es d-dimensional y ningún conjunto de d + 2 puntos en P se encuentran en el límite de una bola cuyo interior no corta P.

El problema de encontrar la triangulación de Delaunay de un conjunto de puntos en un espacio euclidiano d-dimensional se puede convertir en el problema de encontrar la envolvente convexa de un conjunto de puntos en (d + 1) espacio dimensional. Esto se puede hacer dando a cada punto p una coordenada adicional igual a |p|², convirtiéndolo así en un hiperparaboloide (esto se denomina "elevación"); tomando el lado inferior del casco convexo (ya que la tapa del extremo superior mira hacia arriba lejos del origen y debe desecharse); y el mapeo de nuevo al espacio d-dimensional eliminando la última coordenada. Como el casco convexo es único, también lo es la triangulación, asumiendo que todas las facetas del casco convexo son simples. Las facetas no simplistas 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.

Propiedades

Ejemplo de medidas

Cada marco de la animación muestra una triangulación Delaunay de los cuatro puntos. A mitad de camino, los giros de borde triangulado que muestran que la triangulación Delaunay maximiza el ángulo mínimo, no la longitud de borde de los triángulos.

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

• La unión de todos los simplices en la triangulación es el casco convexo de los puntos.
• La triangulación Delaunay contiene O()n^{⌈d/ 2⌉}Simplices.
• En el aviónd = 2), si hay b vértices en el casco convexo, entonces cualquier triangulación de los puntos tiene a la mayoría 2n− 2 −b triángulos, más una cara exterior (ver característica de Euler).
• Si los puntos se distribuyen según un proceso Poisson en el plano con intensidad constante, entonces cada vértice tiene en promedio seis triángulos circundantes. Más generalmente para el mismo proceso en d dimensiones el número promedio de vecinos es una constante dependiendo sólo de d.
• En el plano, la triangulación Delaunay maximiza el ángulo mínimo. Comparado con cualquier otra triangulación de los puntos, el ángulo más pequeño de la triangulación Delaunay es al menos tan grande como el ángulo más pequeño de cualquier otro. Sin embargo, la triangulación Delaunay no minimiza necesariamente el ángulo máximo. La triangulación Delaunay tampoco minimiza necesariamente la longitud de los bordes.
• Un círculo circunscribiendo cualquier triángulo Delaunay no contiene otros puntos de entrada en su interior.
• Si un círculo que pasa por dos de los puntos de entrada no contiene otros puntos de entrada en su interior, entonces el segmento que conecta los dos puntos es un borde de una triangulación Delaunay de los puntos dados.
• Cada triángulo de la triangulación Delaunay de un conjunto de puntos en d- los espacios dimensionales corresponden a una faceta de casco convexo de la proyección de los puntos sobre una (d+ 1)-paraboloide dimensional, y viceversa.
• El vecino más cercano b a cualquier punto p está en un borde bp en la triangulación Delaunay ya que el gráfico vecino más cercano es un subgraph de la triangulación Delaunay.
• La triangulación Delaunay es un spanner geométrico: En el aviónd = 2), el camino más corto entre dos vértices, a lo largo de los bordes de Delaunay, se sabe que no es más de 1.998 veces la distancia de Euclidea entre ellos.

Definición visual de Delaunay: Voltear

De las propiedades anteriores surge una característica importante: Mirando dos triángulos ABD y BCD con el borde común BD (ver figuras), si la suma de los ángulos α y γ es menor o igual a 180°, los triángulos se encuentran la condición de Delaunay.

Esta es una propiedad importante porque permite el uso de una técnica de volteo. 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 con la condición Delaunay (la suma de α y γ es mayor que 180°).

• 

  Este par de triángulos no cumple con la condición Delaunay (hay un punto dentro del interior del círculo).

• 

  Flipping el borde común produce una triangulación Delaunay válida para los cuatro puntos.

Esta operación se llama voltear y se puede generalizar a tres dimensiones o más.

Algoritmos

Necesitamos una manera robusta y rápida de detectar si punto D mentiras en el círculo de A, B, C

Muchos algoritmos para calcular las triangulaciones de Delaunay se basan en operaciones rápidas para detectar cuándo un punto está 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 para evaluar el determinante:

0end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">SilencioAxASí.Ax2+ASí.21BxBSí.Bx2+BSí.21CxCSí.Cx2+CSí.21DxDSí.Dx2+DSí.21Silencio=SilencioAx− − DxASí.− − DSí.()Ax2− − Dx2)+()ASí.2− − DSí.2)Bx− − DxBSí.− − DSí.()Bx2− − Dx2)+()BSí.2− − DSí.2)Cx− − DxCSí.− − DSí.()Cx2− − Dx2)+()CSí.2− − DSí.2)Silencio■0{cH00} {cH00} {cH00} {cH00}} {cH00}} {cH00}} {ccH00}} {cH00} {cH00}} {cH00}} {ccH00}} {ccH00} {cH00}} {cH00}}}}}}}}}} {cH00}}} {ccH00}}}ccH00} {cH00}}}}} {cccccH00}}}ccH00}}}}}}}}}}}}}}}}} {cccccH00}} {ccccH00}cccccH00}}}}cH00}}}ccccH00}}cH00}}}}}}}}}0end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4283d2ae1914af7b7c13c9debc8eaa91cff00bca" style="vertical-align: -12.338ex; margin-top: -0.281ex; width:55.627ex; height:25.843ex;"/>

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

Algoritmos de volteo

Como se mencionó anteriormente, si un triángulo no es Delaunay, podemos voltear uno de sus bordes. Esto conduce a un algoritmo sencillo: construya cualquier triangulación de los puntos y luego invierta los bordes hasta que ningún triángulo sea diferente a Delaunay. Desafortunadamente, esto puede tomar cambios de borde de Ω(n²). Si bien este algoritmo se puede generalizar a tres dimensiones o más, su convergencia no está garantizada en estos casos, ya que está condicionada a la conexión del gráfico de rotafolio subyacente: este gráfico está conectado para conjuntos de puntos bidimensionales, pero puede estar desconectado en dimensiones superiores.

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 gráfico. Cuando se agrega un vértice v, dividimos en tres el triángulo que contiene v, luego aplicamos el algoritmo flip. Hecho de manera ingenua, esto tomará O(n) tiempo: buscamos a través de todos los triángulos para encontrar el que contiene v, luego potencialmente damos la vuelta a cada triángulo. Entonces, el tiempo de ejecución general es O(n²).

Si insertamos vértices en orden aleatorio, resulta (mediante una prueba un tanto compleja) que cada inserción volteará, en promedio, solo O(1) triángulos, aunque a veces volteará muchos más. Esto todavía deja el tiempo de ubicación del punto para mejorar. Podemos almacenar el historial de las divisiones y volteos realizados: 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 no tiene todavía ha sido reemplazado. En promedio, esto también tomará tiempo O(log n). Sobre todos los vértices, entonces, esto toma tiempo O(n log n). Si bien la técnica se extiende a una dimensión superior (como lo demostraron Edelsbrunner y Shah), el tiempo de ejecución puede ser exponencial en la dimensión incluso si la triangulación final de Delaunay es pequeña.

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

Desafortunadamente, los algoritmos basados en volteo son generalmente difíciles de paralelizar, ya que agregar un cierto punto (por ejemplo, el punto central de una rueda de carreta) puede generar hasta O(n) volteos consecutivos. Blelloch et al. propuso otra versión del algoritmo incremental basado en rip-and-tent, que es práctico y altamente paralelizado con lapso polilogarítmico.

Divide y vencerás

Lee y Schachter desarrollaron un algoritmo divide y vencerás para triangulaciones en dos dimensiones, y Guibas y Stolfi lo mejoraron, y más tarde Dwyer. En este algoritmo, uno dibuja recursivamente una línea para dividir los vértices en dos conjuntos. La triangulación de Delaunay se calcula para cada conjunto y luego los dos conjuntos se fusionan a lo largo de la línea de división. Usando algunos trucos inteligentes, la operación de combinación se puede realizar en el tiempo O(n), por lo que el tiempo total de ejecución es O(n log n).

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 n) mientras se mantiene el rendimiento en el peor de los casos.

Un paradigma de divide y vencerás para realizar una triangulación en d dimensiones se presenta en "DeWall: Un algoritmo rápido de división y conquista de triangulación de Delaunay en E^d" por P. Cignoni, C. Montani, R. Scopigno.

Se ha demostrado que el algoritmo divide y vencerás es la técnica de generación de DT más rápida de forma secuencial.

Barrido de casco

Sweephull es una técnica híbrida para la triangulación 2D de Delaunay que utiliza un casco de barrido que se propaga radialmente y un algoritmo de volteo. El casco de barrido se crea secuencialmente iterando un conjunto de puntos 2D ordenados radialmente y conectando triángulos a la parte visible del casco convexo, lo que proporciona una triangulación que no se superpone. Se puede construir un casco convexo de esta manera siempre que el orden de los puntos garantice que ningún punto caiga dentro del triángulo. Pero, la clasificación radial debería minimizar el volteo al ser altamente Delaunay para comenzar. Esto luego se empareja con un último paso iterativo de volteo 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, y esto se puede aprovechar para calcularlo de manera eficiente.

Para modelar terrenos u otros objetos dados una nube de puntos, la triangulación de Delaunay brinda un buen conjunto de triángulos para usar como polígonos en el modelo. En particular, la triangulación de Delaunay evita los triángulos angostos (ya que tienen circunferencias circunscritas grandes en comparación con su área). Ver red irregular triangulada.

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

Una triangulación Delaunay de un conjunto aleatorio de 100 puntos en un avión.

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 del ángulo y porque se han desarrollado algoritmos de triangulación rápidos. Por lo general, 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 del método de elementos finitos y las técnicas 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 cuadrícula 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 rejilla estirada permite la generación de mallas pseudo-regulares que cumplen con los criterios de Delaunay fácil y rápidamente en una solución de un solo paso.

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