LISTAS DE FORMAS - TRIÁNGULOS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Se muestra una triangulación de Delaunay en el plano con círculos circunferenciales

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

Para un conjunto de puntos en la misma línea no hay 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 posibles triangulaciones que dividen el cuadrángulo en dos triángulos satisface la "condición de Delaunay", es decir, el requisito de que Los círculos de todos los triángulos tienen interiores vacíos.

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

Relación con el diagrama de Voronoi [ editar ]

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

Al conectar los centros de los círculos circunferenciales se produce el diagrama de Voronoi (en rojo).

El Delaunay triangulación de un discreto conjunto de puntos P en la posición general corresponde al gráfico doble del diagrama Voronoi de 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 bordes, que pueden derivarse de las relaciones de adyacencia de los triángulos de Delaunay: si dos triángulos comparten un borde en la triangulación de Delaunay, sus circuncentros deben conectarse con un borde en la teselación de Voronoi .

Los casos especiales en los que esta relación no es válida o es ambigua, incluyen casos como:

• Tres o más puntos colineales , donde los círculos 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.
• Los bordes del diagrama Voronoi va a infinito no se definen por esta relación en el caso de un conjunto finito P . Si la triangulación de Delaunay se calcula usando el algoritmo Bowyer-Watson, entonces los circuncentros de triángulos que tienen un vértice común con el triángulo "super" deben ignorarse. Los bordes que van al infinito comienzan desde un circuncentro y son perpendiculares al borde común entre el triángulo mantenido e ignorado.

d- dimensional Delaunay [ editar ]

Para un conjunto P de puntos en el espacio euclidiano ( d- dimensional) , una triangulación de Delaunay es una triangulación DT ( P ) de tal manera que ningún punto en P está dentro de la circun-hiperesfera de cualquier d - simplex en DT ( P ). Se sabe ^[1] que existe una triangulación de Delaunay única 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 no tiene un conjunto de d + 2 puntos en P se encuentran en el límite de una bola cuyo interior no lo hace de intersección P .

El problema de encontrar la triangulación de Delaunay de un conjunto de puntos en el espacio euclidiano d- dimensional se puede convertir en el problema de encontrar el casco convexo de un conjunto de puntos en el  espacio ( d + 1) -dimensional, dando a cada punto p un coordenada extra igual a | p | ² , tomar el lado inferior del casco convexo y volver a mapear al espacio d- dimensional eliminando la última coordenada. Como el casco convexo es único, también lo es la triangulación, suponiendo que todas las facetas del casco convexo sean simples . Las facetas no simbólicas solo ocurren cuando d  + 2 de los puntos originales se encuentran en el mismod - hiperesfera , es decir, los puntos no están en posición general. ^[2]

Propiedades [ editar ]

Pasos de ejemplo

Cada cuadro de la animación muestra una triangulación de Delaunay de los cuatro puntos. A la mitad, el borde de triangulación se voltea y muestra que la triangulación de Delaunay maximiza el ángulo mínimo, no la longitud del borde de los triángulos.

Sea n el número de puntos yd 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 de Delaunay contiene O ( n ^{⌈ d  / 2⌉} ) simplices. ^[3]
• En el plano ( d = 2), si hay b vértices en el casco convexo, entonces cualquier triangulación de los puntos tiene como máximo 2 n  - 2 -  b triángulos, más una cara exterior (ver la característica de Euler ).
• Si los puntos se distribuyen de acuerdo con un proceso de 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 que depende solo de d . ^[4]
• En el plano, la triangulación de Delaunay maximiza el ángulo mínimo. En comparación con cualquier otra triangulación de los 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 otro. Sin embargo, la triangulación de Delaunay no minimiza necesariamente el ángulo máximo. ^[5] La triangulación de Delaunay tampoco minimiza necesariamente la longitud de los bordes.
• 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 ninguno de ellos 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 del casco convexo de la proyección de los puntos en 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 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 más largo que$${\ displaystyle {\ frac {4 \ pi} {3 {\ sqrt {3}}}} \ aprox 2.418}veces la distancia euclidiana entre ellos. ^[6]

Definición de Delaunay visual: voltear [ editar ]

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 cumplen 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 con la condición de Delaunay, cambiar el borde común BD por el borde común AC produce dos triángulos que sí cumplen con 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 con la condición de Delaunay (el círculo contiene más de tres puntos).
 
• 

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

Esta operación se llama volteo y se puede generalizar a tres o más dimensiones. ^[7]

Algoritmos [ editar ]

Necesitamos una forma robusta y rápida de detectar si el punto D se encuentra 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 de un triángulo y una estructura de datos eficiente para almacenar triángulos y bordes. En dos dimensiones, una forma de detectar si el punto D se encuentra en el círculo de A , B , C es evaluar el determinante : ^[8]

${\displaystyle {\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}}={\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\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{aligned}}}$

Cuando A , B y C se ordenan en sentido contrario a las agujas del reloj , este determinante es positivo si y solo si D se encuentra dentro del círculo.

Voltear algoritmos [ editar ]

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

Incremental [ editar ]

La forma más directa de calcular eficientemente la triangulación de Delaunay es agregar repetidamente un vértice a la vez, triangulando de nuevo 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 de volteo. Hecho ingenuamente, esto llevará tiempo O ( n ): buscamos a través de todos los triángulos para encontrar el que contiene v , luego potencialmente volteamos cada triángulo. Entonces el tiempo de ejecución general es O ( n ² ).

Si insertamos vértices en orden aleatorio, resulta (por una prueba algo intrincada) que cada inserción volteará, en promedio, solo triángulos O (1), aunque a veces volteará muchos más. ^[10] 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 aún no 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 ).^[11] Si bien la técnica se extiende a una dimensión superior (como lo demuestran Edelsbrunner y Shah ^[12] ), 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 Bowyer-Watson proporciona otro enfoque para la construcción incremental. Ofrece una alternativa al cambio de borde para calcular los triángulos de Delaunay que contienen un vértice recién insertado.

Desafortunadamente, los algoritmos basados ​​en volteo generalmente son difíciles de paralelizar, ya que agregar cierto punto (por ejemplo, el punto central de una rueda de carreta) puede conducir a O ( n ) volteos consecutivos. Blelloch y col. ^[13] propuso otra versión del algoritmo incremental basado en rip-and-tent, que es práctico y altamente paralelizado con el alcance pollogarítmico .

Divide y conquista [ editar ]

Un algoritmo divide y vencerás para triangulaciones en dos dimensiones fue desarrollado por Lee y Schachter y mejorado por Guibas y Stolfi ^[14] y más tarde por 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 fusión se puede realizar en el tiempo O ( n ), por lo que el tiempo total de ejecución es O ( n  log  n ). ^[15]

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

P. Cignoni, C. Montani, R. Scopigno presenta un paradigma de divide y vencerás para realizar una triangulación en d dimensiones en "DeWall: un algoritmo de triangulación de Delaunay de división rápida en E ^d ". ^[dieciséis]

El algoritmo de divide y vencerás ha demostrado ser la técnica de generación de DT más rápida. ^[17] [18]

Sweephull [ editar ]

Sweephull ^[19] es una técnica híbrida para la triangulación 2D 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 no superpuesta. Se puede construir un casco convexo de esta manera siempre que el orden de puntos garantice que ningún punto caiga dentro del triángulo. Pero, la clasificación radial debería minimizar el volteo al ser muy Delaunay para comenzar. Esto luego se combina con un paso de volteo de triángulo iterativo final.

Aplicaciones [ editar ]

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 puede explotarse para calcularlo de manera eficiente.

Para modelar terrenos u otros objetos dados un conjunto de puntos de muestra, la triangulación de Delaunay proporciona un buen conjunto de triángulos para usar como polígonos en el modelo. En particular, la triangulación de Delaunay evita triángulos estrechos (ya que tienen círculos grandes en comparación con su área). Ver red triangular irregular .

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

La triangulación de Delaunay de un conjunto aleatorio de 100 puntos en un plano.

Las triangulaciones de Delaunay a menudo se usan para construir mallas para solucionadores discretos 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 ángulo y porque se han desarrollado algoritmos de triangulación rápidos. Típicamente, el dominio que se va a mallar se especifica como un complejo simplicio grueso ; para que la malla sea numéricamente estable, debe ser refinada, 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 límite 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 las ubicaciones nodales para minimizar la distorsión del elemento. El método de grilla estirada permite la generación de mallas pseudo-regulares 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 restringida de Delaunay ha encontrado aplicaciones en la planificación de rutas en la conducción automatizada.