1 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Diagrama de Voronoi
Jose Luis Bravo Trinidad
Jose Luis Bravo Trinidad Diagrama de Voronoi
2 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DefinicionPropiedades geometricas
Indice
1 IntroduccionDefinicionPropiedades geometricas
2 AplicacionesAnalisis de recursosTriangulacionesRoboticaDiseno
3 Primer Algoritmo
DescripcionImplementacionEficiencia
4 Segundo Algoritmo -Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Jose Luis Bravo Trinidad Diagrama de Voronoi
3 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DefinicionPropiedades geometricas
Definicion
Dado un conjunto de puntos{p1, . . . , pn} en el plano,denominaremos diagrama deVoronoi a la subdivision delplano en subregiones tales quela region i es el conjunto depuntos mas cercanos a pi que acualquiera de los pj , j 6= i .
Jose Luis Bravo Trinidad Diagrama de Voronoi
4 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DefinicionPropiedades geometricas
Propiedades
El conjunto de puntos equidistantes de dos dados es una lınearecta
El conjunto de puntos equidistantes de tres o mas dados es unpunto (si existe)
Las componentes conexas del complementario del conjunto depuntos que equidistan de dos o mas pi son las regionesbuscadas.
Jose Luis Bravo Trinidad Diagrama de Voronoi
5 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DefinicionPropiedades geometricas
Regiones
Fijado un punto pi , consideremos para cada pj , j 6= i las recta rjformada por los puntos que equidistan de pi y pj .La recta rj divide al plano en dos semiplanos, en uno de los cualesesta pi , al que llamaremos πj .
Jose Luis Bravo Trinidad Diagrama de Voronoi
6 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DefinicionPropiedades geometricas
Regiones
La region del diagrama de Voronoi que contiene a pi puedeobtenerse como la interseccion de todos los semiplanos πj .
Vi =⋂πj
Como los semiplanos son convexos y la interseccion de convexos esconvexa, entonces cada region del diagrama de Voronoi es convexa.
Jose Luis Bravo Trinidad Diagrama de Voronoi
7 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Indice
1 IntroduccionDefinicionPropiedades geometricas
2 AplicacionesAnalisis de recursosTriangulacionesRoboticaDiseno
3 Primer Algoritmo
DescripcionImplementacionEficiencia
4 Segundo Algoritmo -Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Jose Luis Bravo Trinidad Diagrama de Voronoi
8 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Areas de influencia
Supongamos que tenemos un conjunto de recursos geograficos enun area (hospitales, colegios, antenas, servidores, etc). Podemosmodelar la poblacion que usara cada uno de esos recursosmediante un diagrama de Voronoi, asumiendo que el acceso sehara preferentemente al recurso mas cercano y que la distanciaeuclidea aproxima bien al coste de desplazamiento.
Jose Luis Bravo Trinidad Diagrama de Voronoi
9 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Localizaciones
Un problema relacionado con el anterior es, dada una serie derecursos, planificar donde deberıa colocarse el siguiente.Si queremos que diste lo mas posible de los existentes (o que elarea cubierta sea maxima) entonces los vertices del diagrama deVoronoi son los puntos optimos.
Jose Luis Bravo Trinidad Diagrama de Voronoi
10 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Thiessen neighbors
Una manera de definir los vecinos de un punto dado, es considerarlas regiones adyacentes a la region en la que se encuentra el punto.
Jose Luis Bravo Trinidad Diagrama de Voronoi
11 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Interpolacion natural
Dado un conjunto de datos obtenidos en ciertas localizaciones, seasigna a cada punto un valor en funcion del area que ocuparıa suregion (de Voronoi) sobre las regiones determinadas en el conjuntode puntos donde hay datos.
Jose Luis Bravo Trinidad Diagrama de Voronoi
12 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Triangulaciones
Supongamos que tenemos una superficie dada por una serie depuntos y sus alturas. Uno de los modos de reconstruir la superficiees hacer una triangulacion. De todas las posibles, la triangulacionde Delaunay es la que tiene los angulos menos agudos, por lo quees la que se utiliza para el modelado.
Jose Luis Bravo Trinidad Diagrama de Voronoi
13 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Caminos sin obstaculos
Supongamos que tenemos una region con obstaculos. Sicalculamos su diagrama de Voronoi (se puede hacer tambiencuando sustituimos los puntos por cualquier otra figurageometrica), las aristas del diagrama seran los caminos que pasanmas lejos de los obstaculos.
Jose Luis Bravo Trinidad Diagrama de Voronoi
14 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
Analisis de recursosTriangulacionesRoboticaDiseno
Voronoi en la naturaleza/diseno
Los diagramas de Voronoi estan presentes en multitud defenomenos naturales cuando muchas cosas crecen en un mismoespacio (cristales, celulas, etc).Tambien el diseno actual lo toma como elemento de creacion (vermas en, por ejemplo, theverymany.net).
Jose Luis Bravo Trinidad Diagrama de Voronoi
15 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcionImplementacionEficiencia
Indice
1 IntroduccionDefinicionPropiedades geometricas
2 AplicacionesAnalisis de recursosTriangulacionesRoboticaDiseno
3 Primer Algoritmo
DescripcionImplementacionEficiencia
4 Segundo Algoritmo -Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Jose Luis Bravo Trinidad Diagrama de Voronoi
16 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcionImplementacionEficiencia
Descripcion
Por simplificar, tanto en este algoritmo como en el siguiente noscentraremos solo en calcular los vertices del diagrama de Voronoi,aunque se pueden completar para calcular el grafo completo.La manera mas simple de calcular los vertices es:
Considerar todas las combinaciones de tres vertices posibles.
Para cada tres vertices, calcular el centro de la unicacircunferencia que pasa por ellos.
Comprobar que dicha circunferencia no contiene a ningun otrovertice.
Para no repetir combinaciones de tres vertices, podemos suponerque estan ordenados, es decir, son pi , pj , pk con i < j < k .
Jose Luis Bravo Trinidad Diagrama de Voronoi
17 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcionImplementacionEficiencia
Implementacion
Podemos generar todas sus combinaciones del siguiente modo:
1 Recorremos todas las posibilidades para el pi con un bucle (itendra que ir desde 1 hasta n − 2.
2 Dentro del bucle anterior, recorremos todas las posibilidadespara pj (j tendra que ir desde i + 1 -j es mayor que i- hastan − 1).
3 Dentro del bucle anterior, recorremos pk (k desde j + 1 hastan).
Dentro de todos esos bucles, tenemos que calcular el circuncentro.Se puede buscar la formula o calcular la interseccion de las dosmediatrices: entre pi y pj y entre pj y pk . Dentro del mismo bucle,habra que recorrer todos los puntos para ver si algun otro puntoqueda dentro.
Jose Luis Bravo Trinidad Diagrama de Voronoi
18 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcionImplementacionEficiencia
Eficiencia
Como tenemos cuatro bucles anidados y cada uno recorreaproximadamente n valores, tendremos que el algoritmo tarda untiempo del orden de n4.
Jose Luis Bravo Trinidad Diagrama de Voronoi
19 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Indice
1 IntroduccionDefinicionPropiedades geometricas
2 AplicacionesAnalisis de recursosTriangulacionesRoboticaDiseno
3 Primer Algoritmo
DescripcionImplementacionEficiencia
4 Segundo Algoritmo -Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Jose Luis Bravo Trinidad Diagrama de Voronoi
20 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Beach line
El algoritmo de Fortune es unavariacion de los algoritmos tipo“sweep line” aplicado al calculodel diagrama de Voronoi.El problema al barrer el planocon una lınea es que la parte deldiagrama que cae por encima dela lınea puede modificarse porpuntos que estan debajo.Para evitar este problema seconstruye la “beach line”, elconjunto de puntos que
equidistan de la “sweep line” yalgun pi por encima de la“sweep line”.
Jose Luis Bravo Trinidad Diagrama de Voronoi
21 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Estructura de la “beach line”
Para cada punto pi por encimade la “sweep line”, el conjuntode puntos que equidistan de pi yde la “sweep line” es unaparabola. Si construimos todaslas parabolas correspondientes apuntos pi por encima de la“sweep line” y tomamo elınfimo de la coordenada y ,obtendremos la “beach line”.
Por tanto, estara formada porarcos de parabola.
Jose Luis Bravo Trinidad Diagrama de Voronoi
22 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Estructura de la “beach line”
Cada dos arcos de parabola secortan en un punto queequidista de dos pi (y de la“sweep line”), luego sera partede una arista del diagrama deVoronoi.Los vertices del diagrama secorresponden con puntos dondecoinciden las distancias de trespuntos. Cuando la “beach line”llegua a un punto de este tipo,lo que ocurre es que un arco deparabola desaparece.
Jose Luis Bravo Trinidad Diagrama de Voronoi
23 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Eventos
Igual que en el algoritmo de interseccion de segmentos, noguardaremos la “beach line” sino que solo miraremos cuandocambia su topologıa (cuando aparece o desaparece un arco deparabola).A los puntos en los que cambia la topologıa los denominaremoseventos. Los eventos se guardaran en una lista de eventos,ordenada por la coordenada y de la posicion de la “sweep line” quehace que ocurra el evento.Existen unicamente dos tipos de eventos: la aparicion de un nuevoarco o la desaparicion de un arco.
Jose Luis Bravo Trinidad Diagrama de Voronoi
24 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Aparicion de arcos
Un nuevo arco unicamente puede aparecer cuando un nuevo verticetoca la “sweep line”. Cada arco lo marcaremos con el ındice delvertice que lo ha generado.
Jose Luis Bravo Trinidad Diagrama de Voronoi
25 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Desaparicion de arcos
Como vimos anteriormente, un arco solo desaparece en los verticesdel diagrama de Voronoi. Es decir, en un punto q que equidista detres pi cuyos arcos son consecutivos en la “beach line”.
Jose Luis Bravo Trinidad Diagrama de Voronoi
26 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Descripcion global
El esquema del algoritmo de Fortune es similar al de los algoritmosde “sweep line”:
Generamos una lista con todos los eventos que se conocen enel instante inicial. En este caso todos los puntos pi . Seordenan segun la ordenada y .
Se genera una estructura para guardar la “beach line”. Eneste caso generaremos una matriz, aunque la estructura maseficiente es un arbol de busqueda binario.
Se elige el primer evento de la lista. Se elimina de la lista y seprocesa.
Repetimos el paso anterior hasta que no queden eventos.
Jose Luis Bravo Trinidad Diagrama de Voronoi
27 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Manejo de eventos
Para terminar el algoritmo anterior solo nos falta decidir como seprocesa cada uno de los eventos.Evento de creacion: Se coloca un nuevo arco en la “beach line”.Para ello miramos que arco cae en la vertical del punto que provocoel 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 “beachline” para ver si se produce algun evento circular (es decir, secalcula 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 que altura de la“sweep line” se produciran. La altura es la coordenada y del centrode la circunverencia menos su radio.
Jose Luis Bravo Trinidad Diagrama de Voronoi
28 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Manejo de eventos
Evento circular. Se elimina el arco correspondiente. Se compruebasi las nuevas ternas de puntos de la “beach line” producen algunevento circular.Se elimina cualquier evento circula que estuviese en alguna de lasaristas que se han cortado (y en la direccion adecuada).Se anade el punto de interseccion al diagrama de Voronoi.
Jose Luis Bravo Trinidad Diagrama de Voronoi
29 / 29
IntroduccionAplicaciones
Primer AlgoritmoSegundo Algoritmo - Algoritmo de Fortune
DescripcioneventosAlgoritmoEficiencia
Eficiencia
El numero de eventos es proporcional al numero de puntos, n, (sepuede probar que el numero de intersecciones del diagrama esproporcional a n). En cada evento el coste de procesarlo (si seemplea un arbol de busqueda binario) es log(n), dando un tiempototal de n log(n).
Jose Luis Bravo Trinidad Diagrama de Voronoi