Triangulación de Delaunay

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Una triangulación de Delaunay /dəlo'ne/, a veces escrito fonéticamente «Deloné», es una red de triángulos 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. Se usan triangulaciones de Delaunay en geometría por ordenador, especialmente en gráficos 3D por computadora.

Se le denomina así por el matemático ruso Boris Nikolaevich Delone (Борис Николаевич Делоне, 1890 - 1980) quien lo inventó en 1934;[1] el mismo Delone usó la forma francesa de su apellido, «Delaunay», como apreciación a sus antecesores franceses.

Aplicación[editar]

En gráficos 3D por computadora se usan redes de polígonos para modelar objetos tridimensionales, juntando los polígonos para imitar la superficie del objeto. En general se usan triángulos porque son los polígonos más simples y tienen muchas propiedades favorables, como que representan una superficie coplanaria.

Hay dos formas de modelar un objeto de superficies: modelarlo de mano o escanearlo con un range scanner. Al escanearlo se produce un relieve de la superficie formado por puntos discretos (ver Fig. 1). Para usar ese relieve hay que transformarlo en una red de triángulos (ver Fig. 2); esa transformación se llama «triangulación».

La triangulación de Delaunay maximiza los ángulos interiores de los triángulos de la triangulación. Eso es muy práctico porque al usar la triangulación como modelo tridimensional los errores de redondeo son mínimos. Por eso, en general se usan triangulaciones de Delaunay en aplicaciones gráficas.

Condición de Delaunay[editar]

Fig. 4. Los tres vértices A, B, C del triángulo ABC están a la misma distancia del circuncentro O.

La circunferencia circunscrita de un triángulo es la circunferencia que contiene los tres vértices del triángulo.

Según la definición de Delaunay la circunferencia circunscrita es vacía, si no contiene otros vértices aparte de los tres que la definen.

La condición de Delaunay dice que una red de triángulos es una triangulación de Delaunay si todas las circunferencias circunscritas de todos los triángulos de la red son vacías. Esa es la definición original para espacios bidimensionales. Es posible ampliarla para espacios tridimensionales usando la esfera circunscrita en vez de la circunferencia circunscrita. También es posible ampliarla para espacios con más dimensiones pero no se usa en la práctica.

Esa condición asegura que los ángulos del interior de los triángulos son lo más grandes posible. Es decir, maximiza la extensión del ángulo más pequeño de la red.

Propiedades[editar]

Triangulaciones de Delaunay tienen las propiedades siguientes:

  • La triangulación forma la envolvente convexa del conjunto de puntos.
  • El ángulo mínimo dentro de todos los triángulos está maximizado.
  • La triangulación es unívoca si en ningún borde de circunferencia circunscrita hay más que tres vértices.

Relación con diagramas de Voronoi[editar]

La triangulación de Delaunay con todos los circuncentros es el grafo dual del diagrama de Voronoi: los circuncentros son los vértices de los segmentos del diagrama:

Flipping[editar]

De la geometría de los triángulos se puede deducir una característica importante: Contemplando dos triángulos ABD y BCD con la arista común BD (ver Fig. 7), si la suma de los ángulos α y γ es menor o igual a 180°, los triángulos cumplen la condición de Delaunay.

Eso es importante porque de esta propiedad se puede deducir el flipping (del inglés flip «invertir»). Si los dos triángulos no cumplen la condición de Delaunay, reemplazando la arista común BD por la arista común AC produce una triangulación de Delaunay:

Construcción del algoritmo[editar]

Hay varios algoritmos que sirven para crear una triangulación de Delaunay a partir de un conjunto de puntos. En todos estos algoritmos hay que inspeccionar si un vértice está dentro de una circunferencia circunscrita o no, así que este test tiene que ser muy eficiente. Por supuesto es posible computar el circuncentro y la circunferencia circunscrita y después examinar si el vértice está dentro del círculo, pero hay un test más simple y eficiente que usa 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:

\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 - 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

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]

Incremental construction[editar]

El algoritmo Incremental construction (inglés para «construcción incremental») realiza la idea: añadir un vértice a una triangulación de Delaunay y corregir la red hasta que todos los triángulos cumplan de nuevo 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.

Divide and conquer[editar]

Este algoritmo usa el principio conocido como divide and conquer (inglés para «divide y vencerá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 and conquer 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.

Sweepline[editar]

El algoritmo sweepline (inglés para «recorrer la línea») 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.

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