Introducción
Aplicaciones
Primer Algoritmo
Segundo Algoritmo - Algoritmo de Fortune
Diagrama de Voronoi
Jose Luis Bravo Trinidad
1 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Aplicaciones Definición
Primer Algoritmo Propiedades geométricas
Segundo Algoritmo - Algoritmo de Fortune
Índice
1 Introducción Descripción
Definición Implementación
Propiedades geométricas Eficiencia
2 Aplicaciones 4 Segundo Algoritmo -
Análisis de recursos Algoritmo de Fortune
Triangulaciones Descripción
Robótica eventos
Diseño Algoritmo
3 Primer Algoritmo Eficiencia
2 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Aplicaciones Definición
Primer Algoritmo Propiedades geométricas
Segundo Algoritmo - Algoritmo de Fortune
Definición
Dado un conjunto de puntos
{p1 , . . . , pn } en el plano,
denominaremos diagrama de
Voronoi a la subdivisión del
plano en subregiones tales que
la región i es el conjunto de
puntos más cercanos a pi que a
cualquiera de los pj , j 6= i.
3 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Aplicaciones Definición
Primer Algoritmo Propiedades geométricas
Segundo Algoritmo - Algoritmo de Fortune
Propiedades
El conjunto de puntos equidistantes de dos dados es una lı́nea
recta
El conjunto de puntos equidistantes de tres o más dados es un
punto (si existe)
Las componentes conexas del complementario del conjunto de
puntos que equidistan de dos o más pi son las regiones
buscadas.
4 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Aplicaciones Definición
Primer Algoritmo Propiedades geométricas
Segundo Algoritmo - Algoritmo de Fortune
Regiones
Fijado un punto pi , consideremos para cada pj , j 6= i las recta rj
formada por los puntos que equidistan de pi y pj .
La recta rj divide al plano en dos semiplanos, en uno de los cuales
está pi , al que llamaremos πj .
5 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Aplicaciones Definición
Primer Algoritmo Propiedades geométricas
Segundo Algoritmo - Algoritmo de Fortune
Regiones
La región del diagrama de Voronoi que contiene a pi puede
obtenerse como la intersección de todos los semiplanos πj .
\
Vi = πj
Como los semiplanos son convexos y la intersección de convexos es
convexa, entonces cada región del diagrama de Voronoi es convexa.
6 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Índice
1 Introducción Descripción
Definición Implementación
Propiedades geométricas Eficiencia
2 Aplicaciones 4 Segundo Algoritmo -
Análisis de recursos Algoritmo de Fortune
Triangulaciones Descripción
Robótica eventos
Diseño Algoritmo
3 Primer Algoritmo Eficiencia
7 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Áreas de influencia
Supongamos que tenemos un conjunto de recursos geográficos en
un área (hospitales, colegios, antenas, servidores, etc). Podemos
modelar la población que usará cada uno de esos recursos
mediante un diagrama de Voronoi, asumiendo que el acceso se
hará preferentemente al recurso más cercano y que la distancia
euclidea aproxima bien al coste de desplazamiento.
8 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Localizaciones
Un problema relacionado con el anterior es, dada una serie de
recursos, planificar dónde deberı́a colocarse el siguiente.
Si queremos que diste lo más posible de los existentes (o que el
área cubierta sea máxima) entonces los vértices del diagrama de
Voronoi son los puntos óptimos.
9 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Thiessen neighbors
Una manera de definir los vecinos de un punto dado, es considerar
las regiones adyacentes a la región en la que se encuentra el punto.
10 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Interpolación natural
Dado un conjunto de datos obtenidos en ciertas localizaciones, se
asigna a cada punto un valor en función del área que ocuparı́a su
región (de Voronoi) sobre las regiones determinadas en el conjunto
de puntos donde hay datos.
11 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Triangulaciones
Supongamos que tenemos una superficie dada por una serie de
puntos y sus alturas. Uno de los modos de reconstruir la superficie
es hacer una triangulación. De todas las posibles, la triangulación
de Delaunay es la que tiene los ángulos menos agudos, por lo que
es la que se utiliza para el modelado.
12 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Caminos sin obstáculos
Supongamos que tenemos una región con obstáculos. Si
calculamos su diagrama de Voronoi (se puede hacer también
cuando sustituimos los puntos por cualquier otra figura
geométrica), las aristas del diagrama serán los caminos que pasan
más lejos de los obstáculos.
13 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Análisis de recursos
Aplicaciones Triangulaciones
Primer Algoritmo Robótica
Segundo Algoritmo - Algoritmo de Fortune Diseño
Voronoi en la naturaleza/diseño
Los diagramas de Voronoi están presentes en multitud de
fenómenos naturales cuando muchas cosas crecen en un mismo
espacio (cristales, células, etc).
También el diseño actual lo toma como elemento de creación (ver
más en, por ejemplo, theverymany.net).
14 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Descripción
Aplicaciones
Implementación
Primer Algoritmo
Eficiencia
Segundo Algoritmo - Algoritmo de Fortune
Índice
1 Introducción Descripción
Definición Implementación
Propiedades geométricas Eficiencia
2 Aplicaciones 4 Segundo Algoritmo -
Análisis de recursos Algoritmo de Fortune
Triangulaciones Descripción
Robótica eventos
Diseño Algoritmo
3 Primer Algoritmo Eficiencia
15 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Descripción
Aplicaciones
Implementación
Primer Algoritmo
Eficiencia
Segundo Algoritmo - Algoritmo de Fortune
Descripción
Por simplificar, tanto en este algoritmo como en el siguiente nos
centraremos sólo en calcular los vértices del diagrama de Voronoi,
aunque se pueden completar para calcular el grafo completo.
La manera más simple de calcular los vértices es:
Considerar todas las combinaciones de tres vértices posibles.
Para cada tres vértices, calcular el centro de la única
circunferencia que pasa por ellos.
Comprobar que dicha circunferencia no contiene a ningún otro
vértice.
Para no repetir combinaciones de tres vértices, podemos suponer
que están ordenados, es decir, son pi , pj , pk con i < j < k.
16 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Descripción
Aplicaciones
Implementación
Primer Algoritmo
Eficiencia
Segundo Algoritmo - Algoritmo de Fortune
Implementación
Podemos generar todas sus combinaciones del siguiente modo:
1 Recorremos todas las posibilidades para el pi con un bucle (i
tendrá que ir desde 1 hasta n − 2.
2 Dentro del bucle anterior, recorremos todas las posibilidades
para pj (j tendrá que ir desde i + 1 -j es mayor que i- hasta
n − 1).
3 Dentro del bucle anterior, recorremos pk (k desde j + 1 hasta
n).
Dentro de todos esos bucles, tenemos que calcular el circuncentro.
Se puede buscar la fórmula o calcular la intersección de las dos
mediatrices: entre pi y pj y entre pj y pk . Dentro del mismo bucle,
habrá que recorrer todos los puntos para ver si algún otro punto
queda dentro.
17 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción
Descripción
Aplicaciones
Implementación
Primer Algoritmo
Eficiencia
Segundo Algoritmo - Algoritmo de Fortune
Eficiencia
Como tenemos cuatro bucles anidados y cada uno recorre
aproximadamente n valores, tendremos que el algoritmo tarda un
tiempo del orden de n4 .
18 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Índice
1 Introducción Descripción
Definición Implementación
Propiedades geométricas Eficiencia
2 Aplicaciones 4 Segundo Algoritmo -
Análisis de recursos Algoritmo de Fortune
Triangulaciones Descripción
Robótica eventos
Diseño Algoritmo
3 Primer Algoritmo Eficiencia
19 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Beach line
El algoritmo de Fortune es una equidistan de la “sweep line” y
variación de los algoritmos tipo algún pi por encima de la
“sweep line” aplicado al cálculo “sweep line”.
del diagrama de Voronoi.
El problema al barrer el plano
con una lı́nea es que la parte del
diagrama que cae por encima de
la lı́nea puede modificarse por
puntos que están debajo.
Para evitar este problema se
construye la “beach line”, el
conjunto de puntos que
20 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Estructura de la “beach line”
Para cada punto pi por encima Por tanto, estará formada por
de la “sweep line”, el conjunto arcos de parábola.
de puntos que equidistan de pi y
de la “sweep line” es una
parábola. Si construimos todas
las parábolas correspondientes a
puntos pi por encima de la
“sweep line” y tomamo el
ı́nfimo de la coordenada y ,
obtendremos la “beach line”.
21 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Estructura de la “beach line”
Cada dos arcos de parábola se
cortan en un punto que
equidista de dos pi (y de la
“sweep line”), luego será parte
de una arista del diagrama de
Voronoi.
Los vértices del diagrama se
corresponden con puntos donde
coinciden las distancias de tres
puntos. Cuando la “beach line”
llegua a un punto de este tipo,
lo que ocurre es que un arco de
parábola desaparece.
22 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Eventos
Igual que en el algoritmo de intersección de segmentos, no
guardaremos la “beach line” sino que sólo miraremos cuando
cambia su topologı́a (cuándo aparece o desaparece un arco de
parábola).
A los puntos en los que cambia la topologı́a los denominaremos
eventos. Los eventos se guardarán en una lista de eventos,
ordenada por la coordenada y de la posición de la “sweep line” que
hace que ocurra el evento.
Existen únicamente dos tipos de eventos: la aparición de un nuevo
arco o la desaparición de un arco.
23 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Aparición de arcos
Un nuevo arco únicamente puede aparecer cuando un nuevo vértice
toca la “sweep line”. Cada arco lo marcaremos con el ı́ndice del
vértice que lo ha generado.
24 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Desaparición de arcos
Como vimos anteriormente, un arco sólo desaparece en los vértices
del diagrama de Voronoi. Es decir, en un punto q que equidista de
tres pi cuyos arcos son consecutivos en la “beach line”.
25 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Descripción global
El esquema del algoritmo de Fortune es similar al de los algoritmos
de “sweep line”:
Generamos una lista con todos los eventos que se conocen en
el instante inicial. En este caso todos los puntos pi . Se
ordenan según la ordenada y .
Se genera una estructura para guardar la “beach line”. En
este caso generaremos una matriz, aunque la estructura más
eficiente es un árbol de búsqueda binario.
Se elige el primer evento de la lista. Se elimina de la lista y se
procesa.
Repetimos el paso anterior hasta que no queden eventos.
26 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Manejo de eventos
Para terminar el algoritmo anterior sólo nos falta decidir cómo se
procesa cada uno de los eventos.
Evento de creación: Se coloca un nuevo arco en la “beach line”.
Para ello miramos qué arco cae en la vertical del punto que provocó
el evento. Se marca el arco con el ı́ndice del punto que lo crea.
Se miran las dos nuevas ternas que se han generado en la “beach
line” para ver si se produce algún evento circular (es decir, se
calcula el centro de la circunferencia que pasa por los tres puntos).
En dicho caso se almacena el evento.
Para los eventos circulares, hay que almacenar a qué altura de la
“sweep line” se producirán. La altura es la coordenada y del centro
de la circunverencia menos su radio.
27 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Manejo de eventos
Evento circular. Se elimina el arco correspondiente. Se comprueba
si las nuevas ternas de puntos de la “beach line” producen algún
evento circular.
Se elimina cualquier evento circula que estuviese en alguna de las
aristas que se han cortado (y en la dirección adecuada).
Se añade el punto de intersección al diagrama de Voronoi.
28 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
Introducción Descripción
Aplicaciones eventos
Primer Algoritmo Algoritmo
Segundo Algoritmo - Algoritmo de Fortune Eficiencia
Eficiencia
El número de eventos es proporcional al número de puntos, n, (se
puede probar que el número de intersecciones del diagrama es
proporcional a n). En cada evento el coste de procesarlo (si se
emplea un árbol de búsqueda binario) es log(n), dando un tiempo
total de n log(n).
29 / 29
Jose Luis Bravo Trinidad Diagrama de Voronoi
