Triangulación de Delaunay

De Wikipedia, la enciclopedia libre

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 tiene que ser vacía. Se usan triangulaciones de Delaunay en geometría por ordenar, 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.

[editar] Aplicación

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 coplanar.

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.

Fig. 1. De algunos puntos se quiere construir una triangulación.

Fig. 2. Es fácil construir cualquiera triangulación simplemente conectando los vértices.

Fig. 3. Con la condición de Delauany se puede examinar si la triangulación es útil.

[editar] Condición de Delaunay

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.

[editar] Propiedades

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.

[editar] Relación con diagramas de Voronoi

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

Fig. 5. La triangulación del imagen 3 con todas las circunferencias circunscritas y sus centros (en rojo).

Fig. 6. Conectando los centros de las circunferencias circunscritas se produce la diagrama de Voronoi (en rojo).

[editar] Flipping

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:

Fig. 7. Esta triangulación no cumple la condición de Delaunay.

Fig. 8. Esta triangulación no cumple la condición de Delaunay.

Fig. 9. Flipping de la arista común produce una triangulación cumpleando la condición de Delaunay.

[editar] Construcción algoritmo

Hay varios algoritmos que sirven para crear una triangulación de Delaunay de un conjunto de puntos. En todos esos algoritmos hay que inspeccionar si un vértex está dentro de una circunferencia circunscrita o no, así que este test tiene que ser muy eficaz. Por supuesto es posible computar el circuncentro y la circunferencia circunscrita y después examinar si el vértex está dentro del círculo, pero hay un test más simple y eficaz 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 contra el sentido de las agujas del reloj—, el punto D está dentro de su circunferencia circunscrita 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 esta computación puede ser acelerado^[2].

[editar] Incremental construction

El algoritmo Incremental construction (inglés para «construcción incremental») realiza la idea: añada un vértex a una triangulación de Delaunay y corrija la red hasta que todos los triángulos de nuevo cumplen la condición de Delaunay.

Hay varias posibilidades como se puede seleccionar el vértex siguiente, incidentalmente, ordenado por una coordinada o usando un árbol. La selección del vértex siguiente tiene gran influjo en el tiempo de ejecución del algoritmo.

[editar] Divide and conquer

Este algoritmo usa el principio de la informática conocido como divide and conquer (inglés para «divida y conquista»): divida el conjunto de puntos en dos partes de igual tamaño, compute la triangulación de Delaunay por cada parte individualmente y después reúna las dos triangulaciones corrigiendo los errores.

La idea de usar el principio divide and conquer para computar una diagrama de Voronoi en dos dimensiones fue introducido en 1977^[3]. La idea fue revisado en 1980 para computar la triangulación de Delaunay^[4] y mejorado por Guibas y Stolfi in 1985^[5]. En 1986 Dwyer presentó una modificación que mejoró la cota ajustada asintótica^[6] en 1992 Leach presentó otra aceleración del método^[7]. En 1997 Cigoni, Montani y Scopigno presentaron el algoritmo DeWall, cual hace posible computar una triangulación de Delaunay usando divide and conquer en cualquier cantidad de dimensiones^[8].

Usando el algoritmo más avanzado ese método resulta en cota superior asintótica de O(n log n)^[7] y cota ajustada asintótica de Θ(n log log n); en algunos casos especiales es posible reducir la cota ajustada a la cota superior.

[editar] Sweepline

El algoritmo sweepline (inglés para «recorra la línea») realiza un principio similar a lo de la construcción incremental: construya un pequeño parte de la triangulación final y después siga añadiendo vértex por vértex hasta la triangulación está completa. El diferente es que aquí no hay que corregir ningunos errores.

[editar] Enlaces externos

• UNSW Engineering - School of Computer Science and Engineering, Austria: Delaunay Triangulation Algorithms — applet Java que demuestra los algoritmos Incremental construction, Gift wrap, Divide and conquer y QuickHull (en inglés)
• Prof. David Eppstein, University of California, Irvine: Geometry in action - Delaunay triangulation — aplicaciones de la triangulación de Delaunay en geometría por computadora (en inglés)
• Universidad Politécnica de Madrid - Departamento de Matemática Aplicada: Geometría Computacional — varios applets que demuestran la triangulación de Delaunay y diagramas de Voronoi

[editar] Fuentes

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, 1977
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 E^d. October 1997