Aplicación e Introducción a la Triangulacion de Delaunay

Seminario EDAA
Triangulación de Dalaunay y
Diagramas de Voronoi


• La triangulación es la división de una superficie o polígono plano en un
conjunto de triángulos, con la restricción de que cada lado del triángulo se
reparta entre dos triángulos adyacentes.
• Análogamente se define una triangulación de una nube de puntos del
plano como una partición del cierre convexo en triángulos. Laestructura 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.

Como podemos observar, de una misma nube de puntos se
pueden crear diferentes triangulaciones

TRIANGULACIÓN DE DELAUNAY
• La condición de Delaunay dice que una red de triángulos es una
triangulación de Delaunay si todas lascircunferencias circunscritas de todos
los triángulos de la red son vacías, es decir, la circunferencia circunscrita de
cada triángulo de la red no contiene otros vértices aparte de los tres que
definen el triángulo.
• Es posible ampliar la definición para espacios tridimensionales usando la
esfera en vez de la circunferencia circunscrita.

TRIANGULACIÓN DE DELAUNAY
Esta condición aseguraque los ángulos del interior de los triángulos son lo
más grandes posibles, la longitud de los lados de los triángulos es mínima y
la triangulación formada es única.
• Por lo tanto, la triangulación de Delaunay es una red de triángulos que se
caracteriza por formar los triángulos más equiláteros posibles, es decir,
maximiza el mínimo ángulo de los triángulos. De esta forma, los puntos máspróximos entre sí, estarán conectados por una arista, en la que los triángulos
resultantes serán lo más regulares posibles.
•

TRIANGULACIÓN DE DELAUNAY

TRIANGULACIÓN DE DELAUNAY
PROPIEDADES DE UNA TRIANGULACION DE DELAUNAY

• La triangulación es unívoca si ningún círculo rodeado por los vértices de un
triángulo contiene otros puntos del espacio.
• El ángulo mínimo dentro de todos lostriángulos está maximizado y la
longitud de los lados de los triángulos es mínima.
• Las aristas que pertenecen al perímetro de la triangulación conforman el
cierre convexo de la nube de puntos. Estas aristas formarán parte de un
sólo triángulo, mientras que las aristas interiores a la triangulación van a
formar parte de dos triángulos. Los triángulos que conforman el cierre
convexo suelen seralargados.

TRIANGULACIÓN DE DELAUNAY
CARACTERIZACIÓN FORMAL

Propiedad 1:
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.

TRIANGULACIÓN DE DELAUNAY
CARACTERIZACIÓN FORMAL

Propiedad 2:
Dos puntos Pi, Pjpertenecientes a P forman un
lado de la Triangulación de Delaunay de P, sí y
solamente sí, existe un círculo Pi, Pj en su
circunferencia y no contiene en su interior ningún
punto de P.

TRIANGULACIÓN DE DELAUNAY
CARACTERIZACIÓN FORMAL

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

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

Se llama arista legal, a toda arista de una triangulación que pertenece a
dos triángulos tal que lacircunferencia circunscrita a uno de los triángulos
no contiene al punto restante que pertenece al otro triángulo.

•

Una arista ilegal de una triangulación es la arista que pertenece a dos
triángulos tales que forman un cuadrilátero convexo y si se intercambia
dicha arista por la otra diagonal del cuadrilátero mejora el vector de
ángulos.

TRIANGULACIÓN DE DELAUNAY
• A esta operación que...