Geometría Computacional
Delaunay – Voronoil
Gina Ostos
Edwin Peña
Diego Cardozo
Gabriel Aristizabal
Introducción
La Geometría Computacional se define como el
estudio de problemas algorítmicos que involucran
geometría.
Una parte esencial es el diseño y análisis de
algoritmos para la solución eficiente de problemas
geométricos. Como consecuencia, una tarea
fundamental es identificar conceptos,
propiedades y técnicas, las cuales ayudan al
desarrollo de algoritmos eficientes.
Historia
Los primeros resultados constructivos de la Geometría
Computacional (G.C.) datan de la época de Euclides,
existió un nacimiento separado de la Geometría y de
los algoritmos. En 1978 se inicia el estudio de problemas
geométricos usando algoritmos con la prestigiosa tesis
de Doctorado de. Shamos (1978), aunque antes, con el
trabajo de Graham en 1972, se presenta uno de los
algoritmos más conocidos para el cálculo de la
envolvente convexa en el plano en tiempo óptimo. La
Geometría Computacional es una disciplina joven, ya
cuenta con más de 8000 publicaciones relevantes.
Definición
La Geometría Computacional resuelve
algorítmicamente problemas de
naturaleza geométrica y se ha centrado
en problemas dentro del plano y otros
espacios euclídeos.
Mallas Geométricas
La generación de mallas en dos
dimensiones consiste en
aproximar el dominio de
simulación por un polígono el
cual se divide en elementos
geométricos sencillos
(cuadriláteros o triángulos) lo
cual quiere decir que la
interacción de dichos
elementos, sea una arista un
vértice o un conjunto vacio. En
el cual se tiene un dominio
rectangular.
• Método frontal o del
frente de avance.
• Triangulación Delaunay
de un conjunto de
puntos.
• Subdivisiones sucesivas.
Método frontal o
frente de avance
Consiste en la modificación del dominio original por
la remoción sucesiva de triángulos a partir de su
borde. La frontera del dominio evoluciona durante la
generación de triángulos.
Triangulación
Consiste en la generación de puntos sobre el dominio y luego
conectarlos para formar una triangulación que satisfaga alguna
propiedad de optimalidad. Por ejemplo, puede
hallarse la triangulación que maximice el
mínimo de los ángulos de cada par de
triángulos adyacentes. La condición del ángulo
mínimo es equivalente a la del círculo
circunscrito. El círculo que pasa por los tres
vértices de cada triángulo no contiene a otros
puntos de la triangulación. Esta propiedad se
utiliza para la construcción de la triangulación Delaunay. La
utilización de triangulaciones Delaunay en la generación de
mallas se remonta a los trabajos de Cavedish y puede
extenderse al caso tridimensional.
Subdivisiones sucesivas
Se basa en la utilización de la cuadrícula que se superpone al
dominio. Las celdas exteriores se descartan, mientras que el
resto se puede subdividir sucesivamente de acuerdo al grado
de discretización deseado en cada región del dominio.
Finalmente se dividen las celdas interiores en triángulos, de
modo de mantener la compatibilidad con las celdas vecinas.
Las celdas que interceptan a la frontera requieren un
tratamiento especial (pueden triangularse por ejemplo
utilizando el método frontal). Esta técnica es conocida como
“método de árboles cuaternarios” (en tres dimensiones:
árboles octales), debido a la estructura de datos implícita en
la subdivisión sucesiva de cada celda, y ha sido utilizada en
generación de mallas de elementos finitos tanto en dos como
en tres dimensiones.
Triangulo 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.
Diagrama de Voronoi
Es una estructura fundamental dentro de la
Geometría Computacional, que almacena toda
la información referente a la proximidad entre
puntos.
Triangulación Delaunay
• La triangulación Delaunay es un método de
triangulación ampliamente usada en la generación de
mallas no estructuradas. Este es uno de los métodos de
Triangulación más rápidos y relativamente fáciles de
implementar, dando excelentes resultados para la
mayoría de las aplicaciones. Al igual que los diagramas
de Voronoi, este tipo de estructura es usada para
fragmentar el espacio.
• La Triangulación de Delaunay es utilizada para la
generación de mallas, definiendo un método para
conectar un conjunto arbitrario de puntos de manera
que forman un conjunto topológicamente válido de
triángulos que no se interceptan.
Voronoi vs. Delaunay
Una vez conocido el Diagrama de Voronoi, existen una serie de propiedades
que permiten calcular a partir de él la Triangulación de Delaunay de forma
directa e inequívoca y viceversa, pudiendo realizarse este proceso en tiempo
lineal. Habitualmente se resuelve la Triangulación de Delaunay para luego llegar
al Diagrama de Voronoi, aunque en realidad el primero es el dual del segundo.
Para realizar la conversión de Diagrama de Voronoi a Triangulación de
Delaunay, es necesario aplicar las propiedades de ambos diagramas.
La Triangulación de Delaunay es un grafo de líneas rectas dual al Diagrama de
Voronoi. Cada triángulo de la Triangulación se corresponde con un vértice del
diagrama, que además se corresponde con el circuncentro del triángulo. Cada
arista de la triangulación puede calcularse a partir de una arista de Voronoi, ya
que son perpendiculares entre sí y viceversa, ya que, si en cada circuncentro de
cada triángulo de la Triangulación de Delaunay se coloca un vértice entre cada
par de nuevos vértices que estuvieran entre triángulos vecinos, se trazan aristas
coincidentes con la mediatriz, entonces tendríamos el diagrama de Voronoi del
conjunto inicial de puntos.
Característica
Triangulación Delaunay
Podría definirse una triangulación de Delaunay
como aquella que posee el vector de ángulos
mayor de entre todas las posibles triangulaciones,
la palabra vector se refiere para esta propiedad
como los ángulos formados por las aristas de la
triangulación (ordenados de menor a mayor). En
una triangulación de Delaunay serían aquellos
ángulos mayores o iguales que los de cualquier
otra triangulación.
La Triangulación de Delaunay y el Diagrama de Voronoi tienen el
mismo número de aristas y se corresponden entre sí. Cada nodo
de la Triangulación se corresponde con una única región del
diagrama. El contorno de la triangulación es equivalente al
cierre convexo de la nube de punto. No es posible encontrar
ningún punto de la nube en el interior de los triángulos formados
por la triangulación.
Como se puede apreciar en la figura, el Diagrama de Voronoi es
bastante fácil de encontrar a través de la Triangulación de
Delaunay, en tiempo lineal.
Diagrama Dual Voronoi / Delaunay
Algoritmo Flipping
Incremental
Este algoritmo se basa en la comprobación de una de las propiedades de la
triangulación de Delaunay, la propiedad del círculo vacío, la que dice que una
circunferencia circunscrita a un triángulo no contiene en su interior a ningún otro
punto de la nube. Comienza con una triangulación arbitraria y la convierte en
una triangulación de Delaunay por cambio de la diagonal de dos triángulos
vecinos. Estos triángulos comparten una arista llamada ilegal, al no cumplir con la
propiedad anteriormente mencionada, sobre ella se realiza una operación
denominada flip o legalizado de arista o intercambio de arista, la cual consiste
en hacer de esta arista ilegal, una arista legal, es decir que cumpla con la
propiedad de la circunferencia circunscrita.
Algoritmo Flipping
Incremental
Si se observa la figura anterior, en el ejemplo (a), al dibujar el círculo sobre los
vértices de uno de los triángulos, existe un punto interior al círculo y que no
pertenece al triángulo, por lo que en este caso tendríamos una arista ilegal.
Entonces, para corregir este problema bastará con cambiar dicha arista, de
modo que cumpla con la propiedad convirtiéndose en una arista legal, tal como
lo muestra el ejemplo (b) de la figura.
Algoritmo Flipping
Incremental
Este algoritmo se basa en la comprobación de una de las propiedades de la
triangulación de Delaunay, la propiedad del círculo vacío, la que dice que una
circunferencia circunscrita a un triángulo no contiene en su interior a ningún otro
punto de la nube. Comienza con una triangulación arbitraria y la convierte en
una triangulación de Delaunay por cambio de la diagonal de dos triángulos
vecinos. Estos triángulos comparten una arista llamada ilegal, al no cumplir con la
propiedad anteriormente mencionada, sobre ella se realiza una operación
denominada flip o legalizado de arista o intercambio de arista, la cual consiste
en hacer de esta arista ilegal, una arista legal, es decir que cumpla con la
propiedad de la circunferencia circunscrita.
Pasos del algoritmo:
Paso 1:
Sean p-1 p-2 p-3 tres puntos, tales que la nube de puntos P que representan las
antenas de telefonía, está contenida en el triángulo que forman. Inicializamos T
como una triangulación de un único triángulo p-1 p-2 p-3
Pasos del algoritmo:
Paso 2:
Los puntos de la nube P serán insertados en el mismo orden en el que han sido
introducidos por el usuario, como el Triangulo inicial de T engloba toda la nube de
puntos, solo pueden dar dos casos.
Caso 1:
El punto introducido cae dentro de un triangulo ya existente.
En este caso se añaden tres aristas desde pr a los tres vértices
de pi pj pk, partiendo el antiguo triángulo en tres. Solo nos
queda legalizar las nuevas aristas.
LEGALIZA_LADO (pr, pi pj,T)
LEGALIZA_LADO (pr, pj pk,T)
LEGALIZA_LADO (pr, pk pi,T)
Pasos del algoritmo:
Caso 2:
El nuevo punto cae encima de una de las aristas que
forma uno de los lados de un triángulo ya existente.
En este caso dividiremos en dos cada uno de los triángulos
que comparten la arista sobre la que ha caído el punto,
añadiremos las aristas desde pr a pk al tercer vértice pl del
otro triángulo que comparte la arista pi pj. En este caso
como en el anterior tendremos que legalizar las nuevas
aristas creadas,
LEGALIZA_LADO (pr, pi pl,T)
LEGALIZA_LADO (pr, pl pj,T)
LEGALIZA_LADO (pr, pj pk,T)
LEGALIZA_LADO (pr, pk pi,T)
Pasos del algoritmo:
Paso 3:
Cuando no nos queden mas puntos por insertar, Descartaremos p-1, p-2 y p-3 y
todas las aristas que parten de ellos.
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. Se comprueba por las propiedades de las Triangulaciones de Delaunay
anteriormente vista si pi pj es ilegal
3. Si es ilegal
Sea pi pj pk el triángulo adyacente a pr pi pj compartiendo la arista pi pj
4. Se reemplaza pi pj por pr pk
5. LEGALIZA_LADO (pr,pi pk, T)
6. LEGALIZA_LADO (pr,pk pj, T)
Pasos del algoritmo:
Caso 2:
El nuevo punto cae encima de una de las aristas que
forma uno de los lados de un triángulo ya existente.
En este caso dividiremos en dos cada uno de los triángulos
que comparten la arista sobre la que ha caído el punto,
añadiremos las aristas desde pr a pk al tercer vértice pl del
otro triángulo que comparte la arista pi pj. En este caso
como en el anterior tendremos que legalizar las nuevas
aristas creadas,
LEGALIZA_LADO (pr, pi pl,T)
LEGALIZA_LADO (pr, pl pj,T)
LEGALIZA_LADO (pr, pj pk,T)
LEGALIZA_LADO (pr, pk pi,T)
Pasos del algoritmo:
Paso 3:
Cuando no nos queden mas puntos por insertar, Descartaremos p-1, p-2 y p-3 y
todas las aristas que parten de ellos.
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. Se comprueba por las propiedades de las Triangulaciones de Delaunay
anteriormente vista si pi pj es ilegal
3. Si es ilegal
Sea pi pj pk el triángulo adyacente a pr pi pj compartiendo la arista pi pj
4.
Se reemplaza pi pj por pr pk
5.
LEGALIZA_LADO (pr,pi pk, T)
6.
LEGALIZA_LADO (pr,pk pj, T)
Es decir, comprobamos la legalidad de la nueva arista, si es ilegal se hace el flip
correspondiente y se chequea de nuevo la legalidad de las nuevas aristas.
Pasos del algoritmo:
Complejidad del algoritmo:
Se puede obtener basado en los siguientes antecedentes:
- Tomar un punto de la nube aún no triangulada. Los puntos serán elegidos en el mismo orden
en el que han sido introducidos por el usuario, por lo que para una nube de puntos de n
elementos esto demoraría un tiempo O(n).
- Una vez elegido el punto hay que averiguar el triangulo o la arista sobre la que cae el punto
introducido, por lo que habrá que recorrer toda la lista de triángulos existentes. Esto supone un
tiempo de O(n log n).
- Trazar una arista desde el punto a triangular a cada uno de los tres vértices del triángulo que
lo contiene. Trazar una arista requiere un tiempo de O(1), para n puntos el tiempo sería de
O(n).
- Averiguar si las nuevas aristas son legales. Hay que comprobar a la propiedad del círculo
vacío, por lo que el tiempo en realizar esta comprobación para n puntos es de O(n).
- Si alguna de las nuevas aristas es ilegal hay que hacer un flip. Esto requiere borrar la arista
ilegal y se crear una legal, esta operación se puede hacer en un tiempo constante de O(1),
pero quien definirá el tiempo será el número de flips que se deberán realizar. Por ello, aplicar
esta operación a todos los puntos de la nube equivaldría a una complejidad de O(n).
Por lo tanto T(n) = O(n) + O(n log n) + O(n) + O(n) + O(n)
T(n) = O(n log n)
Algoritmo de Fuerza Bruta
Es la forma más fácil de calcular la Triangulación de Delaunay de
una nube de puntos.
Paso 1:
El núcleo del algoritmo, consiste en un bucle que va calculando
todas las posibles triangulaciones, descartando las que no
cumplen los criterios de la triangulación de Delaunay y
quedándose con los que la cumplen.
for (i=0;i<numero_puntos;i++)
for (j=0;j<numero_puntos;j++)
for (z=0;z<numero_puntos;z++)
si triangulo(i,j,z) cumple Delaunay y no repetido
insertar (triangulo(i,j,z)) en lista_triangulos
Algoritmo de Fuerza Bruta
Paso 2:
Se ordenan los triángulos resultantes en el sentido de las agujas del reloj
para facilitar el cálculo de las regiones de Voronoi.
Al terminar tendremos una lista que contendrá todos los triángulos que
componen la triangulación de Delaunay, mediante estos triángulos
calcularemos las áreas de Voronoi.
Su complejidad sería: T(n) = O(n) * O(n) * O(n) * O(n)
T(n) = O(n ^ 4)
Algoritmo de Fuerza Bruta
Mejorado
Este algoritmo es una mejora del anterior usando Computación Científica para la
optimización de los bucles y el filtrado de posibles soluciones.
Paso 1:
Se ordenan los puntos en un array, el criterio de ordenación es de izquierda a
derecha y de arriba a abajo, esta ordenación facilita enormemente el posterior
cálculo de la triangulación.
Algoritmo de Fuerza Bruta
Mejorado
Paso 2:
El núcleo del algoritmo, consiste en un bucle que va calculando todas
las posibles triangulaciones, descartando las que no cumplen los criterios
de la triangulación de Delaunay y quedándose con los que la cumplen.
Al tener los puntos ordenados, el algoritmo calculará de forma más
eficiente las aristas de la Triangulación de Delaunay ya que filtrará
muchas de las repetidas.
for (i=0;i<numero_puntos;i++)
for (j=i;j<numero_puntos;j++)
for (z=j;z<numero_puntos;z++)
si triangulo(i,j,z) cumple Delaunay
insertar (triangulo(i,j,z)) en lista_triangulos
Algoritmo de Fuerza Bruta
Mejorado
Paso 3:
Se ordenan los triángulos resultantes en el sentido de las agujas del reloj
para facilitar el cálculo de las regiones de Voronoi.
Al terminar tendremos una lista que contendrá todos los triángulos que
componen la triangulación de Delaunay, mediante estos triángulos
calcularemos las áreas de Voronoi.
Aristas de Voronoi infinitas
Para resolver esto, se debe calcular los puntos de corte de las
aristas del Diagrama de Voronoi con el área dibujable.
Aristas de Voronoi infinitas
Pasos para el cálculo:
Paso 1:
for (i=0;i<numero_alistas_voronoi;i++)
si la arista(i) se extiende al infinito
nueva_arista = calcular el punto de corte con el área dibujable de la arista(i)
arista(i) = nueva_arista
Al final de este bucle tendremos una lista de las aristas de Voronoi
limitadas dentro del área dibujable.
Cálculo del tamaño área.
El siguiente paso para el cálculo del área de las regiones
de Voronoi, será su triangulación y el posterior cálculo del
área de cada uno de estos triángulos. El cálculo del área
de las regiones de Voronoi cuyos lados son adyacentes a
otra región de Voronoi es relativamente sencillo, solo hay
que generar tantos triángulos como aristas de Voronoi
tenga el área, tomando como uno de los lados la arista de
Voronoi y como vértice el punto al que corresponde esa
área.
Cálculo del tamaño área.
Una vez triangulada, su área será la suma del área de
todos los triángulos que la forman.
Cálculo del tamaño área.
En este punto se encuentra otro problema, como calcular
el área de las regiones que tienen lados que no son
adyacentes con otra región de Voronoi.
Cálculo del tamaño área.
Lo primero que vamos a hacer va a ser asignar las cuatro
esquinas de la zona dibujable, a las regiones de Voronoi
en las que se encuentren, para ello lo más sencillo es
calcular la distancia de los puntos a las esquinas de la
zona dibujable. Las esquinas pertenecerán a la región
cuya distancia al punto al que pertenece sea menor.
Cálculo del tamaño área.
Por lo que la esquina superior izquierda pertenecería a ese
punto.
Cálculo del tamaño área.
Repitiendo el paso para el resto de las esquinas.
Cálculo del tamaño área.
Con esta información el cálculo se resuelve normalmente,
generando tantos triángulos como aristas de Voronoi
tenga el área, tomando como uno de los lados la arista de
Voronoi y como vértice el punto al que corresponde esa
área y añadiendo las esquinas.
Cálculo del tamaño área.
El siguiente paso para el cálculo del área de las regiones
de Voronoi, será su triangulación y el posterior cálculo del
área de cada uno de estos triángulos. El cálculo del área
de las regiones de Voronoi cuyos lados son adyacentes a
otra región de Voronoi es relativamente sencillo, solo hay
que generar tantos triángulos como aristas de Voronoi
tenga el área, tomando como uno de los lados la arista de
Voronoi y como vértice el punto al que corresponde esa
área.
Cálculo del tamaño área.
El siguiente paso para el cálculo del área de las regiones
de Voronoi, será su triangulación y el posterior cálculo del
área de cada uno de estos triángulos. El cálculo del área
de las regiones de Voronoi cuyos lados son adyacentes a
otra región de Voronoi es relativamente sencillo, solo hay
que generar tantos triángulos como aristas de Voronoi
tenga el área, tomando como uno de los lados la arista de
Voronoi y como vértice el punto al que corresponde esa
área.
Descargar

Diapositiva 1 - upcAnalisisAlgoritmos