Triangulación de Delaunay


Triangulación de Delaunay

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.

Contenido

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.

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.

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.

Relación con diagramas de Voronoi

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

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

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

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

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

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

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

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Polígonos de Thiessen — «Voronoi» redirige aquí. Para el matemático creador de los Diagramas de Voronoi, véase Georgi Voronói. Diagramas de Voronoi. Los polígonos de Thiessen nombrados en honor al meteorólogo estadounidense Alfred H. Thiessen son una construcción… …   Wikipedia Español

  • GvSIG — Desktop Cartografía vectorial y raster en gvSIG. Desarrollador …   Wikipedia Español

  • JUMP — Saltar a navegación, búsqueda JUMP Datos OSM almacenados en PostGIS y mostrados en capas mediante consultas SQL en OpenJump. Desarrollador …   Wikipedia Español

  • Logaritmo iterado — El término logaritmo iterado se refiere, en términos matemáticos, a una función definida por la aplicación repetida (iterada) de la función logaritmo sobre su argumento. Así, puede ser descrita como el número de veces que es necesario aplicar… …   Wikipedia Español

  • Mallas de triangulos 3D — La Malla de triangulos 3D es una colección de triángulos y vértices que aproximan una superficie en 3D. Aunque el campo de aplicación de la generación automática de una malla triangular, ha sido tradicionalmente la obtención de modelos digitales… …   Wikipedia Español

  • Geometría discreta — Una colección de círculos y el correspondiente grafo de disco unitario La geometría discreta y la geometría combinatoria son ramas de la geometría que estudian las propiedades combinatorias de objetos geométricos discretos. La mayoría de las… …   Wikipedia Español

  • Grafo de vecindad relativa — En geometría computacional, el Grafo de vecindad relativa (Relative Neighborhood Graph, RNG por sus siglas en inglés) es el subgrafo que extrae las aristas entre los vértices más próximos (respecto a una métrica dada) de un grafo genérico. Fue… …   Wikipedia Español

  • Interpolación multivariable — En análisis numérico, la interpolación multivariable o la interpolación espacial es la interpolación sobre funciones de más de una variable. La función a interpolar se conoce en puntos determinados y el problema de la interpolación consistirá en… …   Wikipedia Español

  • OpenJUMP — JUMP/OpenJUMP Datos OSM almacenados en PostGIS y mostrados en capas mediante consultas SQL en OpenJump. Desarrollador E …   Wikipedia Español

  • VTK — Desarrollador Kitware Inc.. www.vtk.org Información general Última versión estable 5.6.1 30 de septiembre de 2010 …   Wikipedia Español