TRIANGULACIÓN DE DELAUNAY

4.1. INTRODUCCIÓN.

La superficie terrestre se puede modelar con una superficie poliédrica de tipo terreno. Un terreno es una superficie de dos dimensiones en un espacio tridimensional, con la particularidad de que cada línea vertical la intersecta en un punto. Es decir, es una función f que asigna una altura f(p) a cada punto p del dominio A del terreno.

Pongamos como ejemplo una parcela de tierra real, nosotros no conocemos la altura de cada uno de los puntos, sólo conocemos la altura de los puntos que hemos medido previamente, es decir, conocemos la altura de un conjunto finito P contenido en A de puntos. A partir de estos puntos podemos calcular aproximadamente la altura de otros puntos del dominio. Se podría pensar en una primera aproximación en asignar a cada punto p una altura igual a la del punto más cercano, esto daría una imagen de terreno discreto que no se ajusta a la realidad. Es aquí, donde podemos introducir el concepto de triangulación.

Una triangulación de una nube de puntos del plano es una familia maximal de triángulos de interiores disjuntos cuyos vértices son puntos de la nube y en cuyo interior no hay ningún punto de la nube.

Volvamos de nuevo a las superficies de tipo terreno: supongamos que los puntos de la nube son los puntos donde hemos medido la altura, después de realizar la triangulación, elevamos dichos puntos a su altura real, la triangulación resultante en 3-D es una superficie poliédrica de tipo terreno, que puede ser utilizada como una aproximación más perfecta al terreno real.

En el siguiente gráfico se puede observar una superficie de tipo terreno, en la que se puede observar las implicaciones anteriores.

Surgen ahora nuevas cuestiones: ¿cómo triangulamos ese conjunto de puntos? Existen muchas formas de triangular conjuntos de puntos, pero, ¿cuál es la triangulación que más se aproxima a un terreno?. Al no tener información sobre otros puntos, en principio, cualquier triangulación podría ser igual de válida, aunque a simple vista unas parecen más naturales que otras. Parece más lógica la triangulación que forme los "triángulos más regulares" , que aparentemente nos dará una imagen más fiel del terreno real. De esta forma llegaremos a la Triangulación de Delaunay (o más correctamente, Triangulación de Delone)  

4.2. TRIANGULACIÓN DE UNA NUBE DE PUNTOS

Sea P = {p1, p2,...,pn} un conjunto de puntos en el plano. Definiremos una subdivisión maximal en el plano como una subdivisión S, tal que ningún lado conectado a dos vértices pueda ser añadido a S sin perder su estado plano, es decir, ningún lado de S intersecta con otro lado existente. Así, una triangulación se define como una subdivisión maximal planar cuyo conjunto de vértices es P. Es sencillo demostrar que esta subdivisión está formada por triángulos.     

En los gráficos anteriores se puede observar dos de las muchas posibilidades para triangular una nube de puntos, la primera de ellas es una triangulación "normal" y la segunda, la ya comentada triangulación de Delaunay.

No se van a tratar los métodos para triangular una nube de puntos, existiéndo para ello numerosa bibliografía, pasaremos directamente a hablar de esa clase especial de triangulación, la triangulación de Delaunay.  

4.3. TRIANGULACIÓN DE DELAUNAY.

La idea de la Triangulación de Delaunay consiste en: dada una nube de puntos en el plano, hallar una triangulación en la que los puntos más próximos entre sí estén conectados por una arista, o dicho de otra forma, en la que los triángulos resultantes sean lo más regulares posibles.

4.3.1. Caracterización de la Triangulación de Delaunay.

Sea P = {p1, p2,...,pn} un conjunto de puntos en el plano, una Triangulación de Delaunay de P cumplirá las siguientes propiedades:

• Tres puntos pi, pj y pk pertenecientes a P son vértices de la misma cara de la Triangulación de Delaunay de P, si y solamente si, el círculo que pasa por los puntos pi, pj y pk no contiene puntos de P en su interior.

Podemos observarlo en el siguiente gráfico:

• Dos puntos pi y pj pertenecientes a P forman un lado de la Triangulación de Delaunay de P, si y solamente si, existe un círculo que contiene a pi y pj en su circunferencia y no contiene en su interior ningún punto de P.

De igual manera podemos observarlo en el gráfico siguiente:

Con estas dos propiedades podemos caracterizar la Triangulación de Delaunay de la siguiente manera:

Sea P un conjunto de puntos en el plano y T una triangulación de P. T es una Triangulación de Delaunay de P, si y solamente si, la circunferencia circunscrita de cualquier triángulo de T no contiene puntos de P.

Veamos gráficamente lo que denominaremos como arista ilegal:

Se puede observar, que en la figura de la izquierda, la circunferencia circunscrita al triángulo sombreado contiene a otro punto en su interior, la arista que pertenece a los dos triángulos (línea más gruesa) es una arista ilegal. Realizando un intercambio de aristas o flip se consigue una triangulación válida, tal y como se observa en el dibujo de la derecha. Hemos convertido una arista ilegal en legal.

Se puede generalizar y afirmar que una triangulación T de un conjunto P de puntos en el plano es una Triangulación de Delaunay, si y solamente si, todas las aristas son legales.  

4.3.2. Un Primer Algoritmo.

Con las afirmaciones anteriores podríamos pensar en un primer algoritmo para el cálculo de la Triangulación de Delaunay de un conjunto de puntos en el plano:  

TRIANGULACION_DELAUNAY (P)

Entrada: Un conjunto P de puntos en el plano.Salida: La Triangulación de Delaunay de P.1. Obtener una triangulación T cualquiera de P.2. mientras existan arista ilegales en T

hacer el flip correspondiente de la arista.4. Fin

Como hemos comentado no vamos a partir de una triangulación dada, sino que vamos a construir la Triangulación de Delaunay de manera incremental a medida que van insertándose nuevos puntos.

4.3.3. Otro Algoritmo.

Realmente no es un nuevo algoritmo, es una modificación del anterior para adaptarlo al mecanismo incremental.

Partimos de un triángulo p-1 p-2 p-3, suficientemente grande, que contenga toda la nube de puntos.

La idea es computar la Triangulación de Delaunay de la nube de puntos sin que el triángulo externo p-1 p-2 p-3 afecte a la misma. Finalmente descartaremos las aristas que partan de p-1, p-2 ó p-3

Veamos el algoritmo:  

TRIANGULACION_DELAUNAY (P)Entrada: Un conjunto P de puntos en el plano.Salida: La Triangulación de Delaunay de P.1. Sean p-1, p-2 y p-3 tres puntos tales que P está contenido en el triángulo que forman.2. Inicializamos T como una triangulación de un único triángulo p-1 p-2 p-3

3. Realizar una permutación cualquiera p1, p2,..., pn de P4. for r:=1 to n5.     hacer (* Insertar pr en T *)6.     Encontrar un triángulo pi pj pk de T que contenga a pr

7.     si pr cae en el interior del triángulo pi pj pk

8.         entonces               Añadir aristas desde pr a los tres vértices de pi pj pk,               dividiendo este triángulo en tres9.             LEGALIZA_LADO (pr, pi pj,T)10.            LEGALIZA_LADO (pr, pj pk,T)11.            LEGALIZA_LADO (pr, pk pi,T)12.        en caso contrario               (* pr cae encima de uno de los lados del triángulo pi pj pk,                  por ejemplo el lado pi pj *)13.            Añadir aristas desde pr a pk y al tercer vértice pl del otro

               triángulo que comparte la arista pi pj, de esta forma dividimos               los dos triángulos que comparten la arista pi pj en cuatro triángulos.14.            LEGALIZA_LADO (pr, pi pl,T)15.            LEGALIZA_LADO (pr, pl pj,T)16.            LEGALIZA_LADO (pr, pj pk,T)17.            LEGALIZA_LADO (pr, pk pi,T)18. Descartar p-1, p-2 y p-3 y todas las aristas que parten de ellos de T19. devuelve T

Veamos el algoritmo algo más en detalle:

En el punto 6. se nos pide que encontremos el triángulo que contiene a ese punto, éste es un típico problema de localización de punto tratado en numerosa bibliografía.

En el punto 7. (el punto está en el interior del triángulo) nos encontramos en la situación que se presenta en el siguiente gráfico:

Vemos como conectamos el vértice insertado con los vértices del triángulo, partiendo de esta forma el triángulo original en tres.

En el punto 12. en cambio, el punto cae justamente en medio de una arista compartida por dos triángulos, en este caso dividimos los dos triángulos iniciales en cuatro, tal y como muestra el gráfico siguiente:

En ambos casos hemos generado nuevos triángulos y no tenemos la garantía de que las aristas externas sean aristas legales, por eso, desde el punto 9. al 11. y desde el 14. al 17. del algoritmo se realiza la legalización de los lados más externos, realizando flips, si es necesario (procedimiento LEGALIZA_LADO).  

Veamos ahora el procedimiento LEGALIZA_LADO:  

LEGALIZA_LADO (pr, pi pj, T) 1. (* El punto que se está insertando es pr, y pi pj es la arista de T a la que puede ser necesario hacer un flip *) 2. si pi pj es ilegal 3.     entonces            Sea pi pj pk el triángulo adyacente a pr pi pj compartiendo la arista pi pj 4.         (* Flip pi pj *) Reemplazar pi pj por pr pk 5.        LEGALIZA_LADO (pr,pi pk, T) 6.        LEGALIZA_LADO (pr,pk pj, T)

Es decir comprueba que la legalidad de la arista, si es ilegal hace el flip correspondiente y chequea de nuevo la legalidad de los nuevos lados.

Anteriormente ya comentamos cuando un lado es ilegal, pero por la construcción del algoritmo, existen tres puntos (los del triángulo externo) que insertamos al comienzo y no deben afectar a la triangulación de la nube de puntos, por esto hay que realizar una modificación al test de comprobación de la legalidad de la arista cuando uno de los puntos del triángulo externo está implicado. Veamos esta modificación.

Partimos de la nube inicial de puntos P = {p1, p2,...,pn} a la que le añadimos los puntos que forman el triangulo externo que contiene a P, es decir, p-1, p-2 y p-3. Queremos comprobar si la aristapi pj es o no ilegal. Surgen varias posibilidades:

• i y j son negativos.

En este caso decidimos que la arista pi pj es legal, ya que tenemos que preservar las aristas del triángulo externo p-1 p-2 p-3.

Para el resto de los casos asumimos que pk y pl son los otros dos vértices de los triángulos que comparten la arista pi pj.

• i, j, k, l son todos positivos.

Este es el caso normal comentado anteriormente, la arista pi pj es ilegal, si y solamente si, pl cae dentro del círculo definido por pi pj y pk

• Solamente uno de los índices i, j, k, l es negativo.

No queremos que este punto especial destruya alguna arista de Delaunay entre puntos de P. Para ello, si i o j son negativos (pi o pj son puntos del triángulo externo), decidimos que la arista pi pjes ilegal y será reemplazada por la arista pk pl, en caso contrario la arista pi pj es legal.

• Dos de los índices i, j, k, l son negativos.

En este caso uno de los índices i, j y otro de los índices k,l deben ser negativos; no podemos tener k y l negativos y si i y j lo fueran estaríamos en el primer caso. Si el indice negativo de i, j es menor que el indice negativo de k, l entonces decidimos que la arista pi pj es legal, en caso contrario, ilegal.

• Tres de los índices i, j, k, l son negativos.

Este caso nunca puede ocurrir: si i y j son negativos estaríamos en el primer caso, además k y l no pueden ser ambos negativos ya que uno de los dos debe ser el punto pr que acabamos de insertar.

Como hemos visto, este algoritmo, no es directamente incremental, ya que se parte de un conjunto de puntos inicial. Todas las afirmaciones anteriores son válidas en el caso de que los puntos sean insertados, por ejemplo, por pulsaciones del ratón, a excepción de la elección del triángulo externo que deberemos de prefijarla al comienzo de la ejecución.

Existe una variación sobre el algoritmo que no utiliza el triángulo externo que contiene a toda la nube de puntos. Se basa en el siguiente planteamiento:

Si el punto que insertamos está dentro de un triángulo de Delaunay (o en una arista),es decir, está dentro del cierre convexo de la nube de puntos, operamos de igual forma que el algoritmo descrito.

Pero si está fuera de la nube, trazaríamos aristas desde el punto a todos los vértices del cierre convexo visibles desde él, aplicando posteriormente el algoritmo LEGALIZA_LADO a las aristas internas de los nuevos triángulos generados, que propagarán al legalización de los lados hacia el interior. Quizá un gráfico ilustre mejor la idea:     

Hemos insertado el punto p en el exterior, creamos aristas desde p a los puntos del cierre convexo que son visibles desde p es decir a c1, c2 y c3 , generando tres nuevos triángulos, que en principio, no tienen porqué ser válidos, deberemos chequear la legalidad de los lados 1, 2 y 3 y realizar los flips si son necesarios, y por supuesto propagar la legalización según lo indicado en el algoritmo LEGALIZA_LADO.

Como se habrá podido observar existen muchas relaciones entre los Diagramas de Voronoi y la Triangulación de Delaunay, hasta tal punto que son estructuras duales, como veremos en el siguiente punto.  

4.4. VORONOI vs DELAUNAY.

Nada mejor que un ejemplo gráfico para ver las relaciones entre el Diagrama de Voronoi y la Triangulación de Delaunay. En la ilustración siguiente podemos observar el Diagrama de Voronoi de una nube de puntos y, superpuesto, la Triangulación de Delaunay:     

Podemos observar:

• Cada vértice de Delaunay tiene una región de Voronoi dual.

• Cada arista de Delaunay tiene una arista de Voronoi dual (perpendiculares).

• Cada triángulo de Delaunay tiene un vértice de Voronoi dual, que coincide con el circuncentro del triángulo.

Con estas observaciones, los dos problemas a resolver son el mismo, obteniendo uno de los dos diagramas, el dual también está resuelto.

http://www.dma.fi.upm.es/mabellanas/voronoi/delone/delone.html

Triangulación de DelaunayUna 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.

[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 Delaunay 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 del diagrama de Voronoi: los

circuncentros son los vértices de los segmentos del diagrama:

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

 

Fig. 6. Conectando los centros de las circunferencias circunscritas se produce el 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 que cumple la condición de Delaunay.

[editar]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:

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

[editar]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.

[editar]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

Delaunay4 y mejorada por Guibas y Stolfi in 1985.5 En 1986 Dwyer presentó una modificación que

mejoró la cota ajustada asintótica6 y en 1992 Leach presentó otra aceleración del método.7En 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.

[editar]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

http://es.wikipedia.org/wiki/Triangulación_de_Delaunay