Capítulo 3

DIAGRAMAS DE VORONOI

• 3.1. INTRODUCCIÓN

• 3.2. CONCEPTOS TEÓRICOS

• 3.2.1. Observaciones • 3.2.1.1. Observación 1 • 3.2.1.2. Observación 2 • 3.2.1.3. Observación 3 • 3.2.1.4. Observación 4

• 3.3. ALGORITMO DE FORTUNE

• 3.3.1. Introducción • 3.3.2. Visión Gráfica del Algoritmo de Fortune

• 3.3.2.1. Eventos de Punto (Site Events) • 3.3.2.2. Eventos de Círculo (Circle Events)

• 3.3.3. Estrategia del Algoritmo de Fortune • 3.3.3.1. Estructuras de Datos

• 3.3.3.1.1. Estructura DCEL • 3.3.3.1.2. Árbol binario de búsqueda balanceado • 3.3.3.1.3. Cola de eventos

• 3.3.4. El algoritmo de Fortune • 3.3.5. Complejidad del algoritmo

3.1. INTRODUCCIÓN.

Un Diagrama de Voronoi de un conjunto de puntos en el plano, no es más que la subdivisión del mismo en regiones formadas por los lugares más próximos a cada uno de los puntos.

De los Diagramas de Voronoi ya hablaba Descartes cuando afirmaba que el sistema solar estaba formado

por vórtices, pero fueron Dirichlet, Voronoi y Thiessen los que profundizaron en el estudio de estos diagramas.

El siguiente gráfico muestra un diagrama de Voronoi de una nube de puntos:

Son muchas las utilidades de los Diagramas de Voronoi entre las que podemos citar:

• Posicionamiento de torretas en telefonía móvil. La región de Voronoi de cada una de las torretas determinaría qué teléfonos deberían realizar la conexión a través de la misma.

• Control aéreo. El Diagrama de Voronoi de cada centro de control, determinaría la zona de espacio aéreo a controlar por dicha estación.

• Distribución de servicios públicos (hospitales, centros comerciales...). La ubicación de dichos establecimientos "debería ser" (al menos teóricamente) la que tenga la mayor área de región de Voronoi con respecto al resto de establecimientos del mismo tipo, para así aumentar la hipotética clientela. Como comentario a este último caso, podríamos realizar una serie de modificaciones al planteamiento: pensemos en el caso de la ubicación de hospitales. A un determinado enfermo siempre le interesaría acudir al hospital más cercano a su domicilio según la distancia euclídea. Para saber a cual acudir no tendía más que mirar el Diagrama de Voronoi de los puntos que indican la posición de los hospitales y comprobar en que región se encuentra su casa. Ahora bien, también podría ser interesante considerar a ciertos hospitales como más cercanos si tienen, por ejemplo, mejor acceso (autopista...) o si tienen un mayor número de camas. En este caso cada uno de los puntos (hospitales en nuestro caso) puede tener asignado un determinado "peso", con lo que el Diagrama de Voronoi de la nube de hospitales podría cambiar notablemente al llevarse una mayor zona de influencia (cercanía) el hospital con más peso.

Quizá un ejemplo gráfico ilustre mejor esta idea:

El hospital h al tener un peso mayor, arrebata a los puntos más cercanos, zonas que según la distancia euclídea estarían más próximas a ellos. La líneas finas muestran el Diagrama de Voronoi del conjunto de puntos sin peso y la zona más gruesa sería la resultante de asignar un hipotético peso a h.

Variedades sobre los Diagramas de Voronoi aparecen utilizando métricas distintas a la euclídea. No es el objeto de este Trabajo de Fin de Carrera en tratar estos Diagramas, existiendo abundante bibliografía sobre el tema. Nos centraremos pues, en los Diagramas de Voronoi en el plano y utilizaremos la distancia común, la distancia euclídea.

A parte de las mencionadas utilidades de estos diagramas podemos citar: el posicionamiento de brazos robóticos, posicionamiento de torretas de visión de zonas forestales para el control de fuegos...

Comenzaremos después de esta introducción con los conceptos teóricos de los Diagramas de Voronoi.

3.2. CONCEPTOS TEÓRICOS.

Denotamos la distancia Euclídea entre dos puntos del plano como dist(p,q).siendo:

Sea P = {p1,p2,...,pn} un conjunto de n puntos distintos en el plano. Definimos el diagrama de Voronoi de

P como la subdivisión del plano en n regiones, cada una correspondiente a un punto de P, cumpliendo, que un punto q pertenece a la región correspondiente al punto pisi y solamente si dist(q,pi) < dist(q,pj)

para cada punto pj P, con j distinto de i. Denotamos el diagrama de Voronoi de P como Vor(P). La región

correspondiente al punto pi es llamada V(pi).

Observemos por un momento la estructura de una única región de Voronoi. Para dos puntos p y q en el plano definimos el bisector de p y q como el bisector perpendicular del segmento pq. Este bisector divide el plano en dos semiplanos. Denotamos el semiplano que contiene a p como h(p,q) y al semiplano que contiene a q como h(q,p). Se puede observar que r pertenece a h(p,q) si y solamente si dist(r,p) < dist(r,q). Podemos obtener de aquí las siguientes observaciones:

3.2.1. Observaciones

Veamos algunas observaciones sobre los Diagramas de Voronoi.

3.2.1.1. Observación 1

Esto es, V(pi) es la intersección de n-1 semiplanos y por tanto una región poligonal convexa con como

máximo n-1 vertices y n-1 lados. Es decir, que la región de Voronoi de un determinado punto, consistirá en la intersección de todos los semiplanos h(pi,pj).

Obviamente éste no sería un algoritmo eficiente para el cálculo del Diagrama de Voronoi de la nube de puntos completa ya que habría que repetir el proceso para los n puntos de la nube.

3.2.1.2. Observación 2

Si todos los puntos de P son colineales, entonces Vor(P) (Diagrama de Voronoi de P) estará formada por n-1 lineas paralelas y n regiones.

Se observa claramente en el gráfico anterior.

3.2.1.3. Observación 3

Un Diagrama de Voronoi de una nube de puntos en el plano tiene a lo sumo 2n-5 vértices y 3n-6 lados.

La demostración de ésta y otras propiedades pueden encontrarse en la bibliografía que se lista al final de este trabajo.

3.2.1.4. Observación 4

Para un conjunto de puntos P del plano, un punto q es vértice del Diagrama de Voronoi de P si y solamente si el círculo vacío de mayor tamaño con centro en q contiene tres o más puntos de P sobre su circunferencia.

En el siguiente gráfico se muestra el Diagrama de Voronoi de los puntos p1, p2 y p3, se puede observar

que el punto q es vértice del Diagrama de Voronoi ya que la circunferencia mayor vacía contiene precisamente a los tres puntos.

3.3. ALGORITMO DE FORTUNE

3.3.1. Introducción

Un primer algoritmo para el cálculo del Diagrama de Voronoi en el que podríamos pensar a la vista de lasobservaciones anteriores sería, el de computar las intersecciones comunes de todos los semiplanos h(pi,pj), para cada punto pi, con i distinto de j. Este algoritmo tendría una complejidad O(n log n) por punto, necesitando O(n2 log n) para computar la totalidad del Diagrama.

Existe un algoritmo basado en el barrido plano, conocido como algoritmo de Fortune -debido a su inventor- o de línea de barrido que es capaz de calcular el Diagrama de Voronoi de una nube de puntos enel plano con complejidad O(n log n), que es además complejidad óptima para calcular el diagrama de Voronoi.

Comenzaremos con una visión gráfica inicial del algoritmo para posteriormente profundizar en los conceptos teóricos del mismo.

3.3.2. Visión Gráfica del Algoritmo de Fortune

Vamos a realizar una primera justificación gráfica del mecanismo que utiliza el algoritmo de Fortune paragenerar el Diagrama de Voronoi de un conjunto de puntos en el plano.

Partimos de un conjunto S de n puntos en el plano x-y, cumpliéndose de no existen cuatro puntos cocirculares.

Creamos para cada punto un cono opaco, idéntico a todos los demás, creciendo hacia el eje z.

Según esto y observando el gráfico anterior podemos afirmar:

• Dos conos intersectan en una hipérbola que cae en un plano vertical al x-y. • Observando desde arriba (por encima del plano x-y), la intersección entre dos conos es una línea recta. • Esta línea es la mediatriz en dos dimensiones de los dos puntos. • No todos los puntos de esta línea son visibles, ya que pueden ser ocultados por el crecimiento de otros conos.

De todo esto se puede deducir que, proyectando la intersección visible de todos los conos sobre el plano x-y se obtiene el diagrama de Voronoi del conjunto de puntos.

Vemamos ahora el mecanismo de barrido de este algoritmo:

Partimos de un plano de barrido que se mueve de izquierda a derecha sobre el plano x-y con un ángulo de inclinación igual al de los conos, según se muestra en el siguiente gráfico:

El plano de barrido intersecta con el plano x-y en lo que llamamos línea de barrido.

La intersección del plano de barrido con el cono proyectada sobre el plano x-y es una parábola con foco en el punto p (según el gráfico) y directriz la línea de barrido.

Si hacemos ahora hacemos también opaco el plano de barrido podemos observar:

• El plano de barrido oculta los conos que nacen a la derecha de la línea de barrido. • Los conos visibles que todavía no han sido totalmente barridos por el plano de barrido proyectarán sobreel plano x-y un conjunto de parábolas apuntando hacia la izquierda, con ejes paralelos y distintas anchuras.

En el siguiente gráfico podemos observar la proyección en el eje x-y:

La frontera de la unión de todas las parábolas es lo que se denomina frente parabólico o línea de playa.

Podemos observar que hacia la derecha de la línea de barrido el plano de barrido al ser opaco oculta todoslos conos y bloquea su visión desde abajo, en cambio hacia la izquierda el plano de barrido cae por encima de uno o más conos y por tanto no bloquea sus vistas desde abajo.

Si observamos por debajo del plano x-y:

• Cada arco del frente parabólico cae en una región de Voronoi. • Cada punto de corte entre dos arcos consecutivos del frente parabólico cae en uno de los lados del Diagrama de Voronoi.

Podemos afirmar que cada punto de un lado del Diagrama de Voronoi, será un punto de corte entre dos arcos consecutivos del frente parabólico, en algún momento, durante el proceso de barrido.

Es decir, estamos construyendo el Diagrama de Voronoi.

En la evolución del frente parabólico surgen dos tipos de eventos que trataremos a continuación:

• Eventos de Punto (Site Events) • Eventos de Círculo (Circle Events)

3.3.2.1. Eventos de Punto (Site Events)

Cuando la línea de barrido pasa justamente por encima de un punto, una parábola degenerada (ancho 0) seune al frente parabólico, esta parábola parte una arco existente en el frente parabólico en dos. La evolución posterior de esta parábola durante el proceso de barrido dará lugar a un nuevo lado del Diagrama de Voronoi. El siguiente gráfico muestra la evolución en la creación de un lado de Voronoi:

En la figura 1 la línea de barrido no ha llegado al punto, en la 2 justamente está sobre el punto, se crea la parábola degenerada que divide en dos uno de los arcos del frente parabólico y en la figura 3 ha pasado la línea y se observa la evolución del nuevo lado del Diagrama Voronoi.

Llamaremos pues, evento de punto (site event) cuando la línea de barrido pasa justamente por encima de uno de los puntos de la nube. Este es el único modo de añadir un nuevo arco al frente parabólico y provoca la aparición de un nuevo lado del Diagrama de Voronoi.

3.3.2.2. Eventos de Círculo (Circle Events)

Veamos ahora que ocurre cuando una arco va decreciendo en el frente parabólico hasta convertirse en un punto y desaparecer de dicho frente.

Veámoslo con un gráfico:

En la figura 1 se observa que A1, A2 y A3 son tres arcos consecutivos del frente parabólico correspondientes a los puntos p1, p2 y p3 respectivamente. El arco A2 se va estrechando debido al crecimiento de A1 y A2. En la figura 2 se observa justo el momento en el que el arco A2 abandona el frente parabólico formando un punto de corte entre A1 y A3 que hemos llamado u, u es equidistante de p1, p2 y p3, es decir, es el centro de la circunferencia que pasa por p1, p2 y p3. Al mismo tiempo esta circunferencia es tangente a la línea de barrido en un punto que hemos llamado w, justamente este punto es lo que llamaremos evento de círculo (circle event). Cuando la línea de barrido está sobre este punto (w)se está generando un vértice del Diagrama de Voronoi y a partir de este momento comienza a crecer a partir de él un nuevo lado del Diagrama de Voronoi, tal y como se puede apreciar en la figura 3.

Un circle event es la única forma de que un arco abandone el frente parabólico.

La cuestión ahora es: después de esta primera aproximación gráfica, ¿qué estructuras de datos optimas debo utilizar? y ¿qué partes del frente parabólico debo guardar durante el proceso de barrido para conseguir finalmente el Diagrama de Voronoi de la nube de puntos inicial?. Para ello comenzaremos, ahora sí, con los conceptos teóricos necesarios para contestar a estas preguntas.

3.3.3. Estrategia del Algoritmo de Fortune

La estrategia de este algoritmo consiste, como hemos comentado anteriormente, en realizar un barrido con una línea recta desde arriba a abajo del plano (cambiamos el orden del barrido con respecto a la visión gráfica, sin que ello influya en los razonamientos). Mientras la línea se va moviendo, la información no cambia, excepto en ciertos puntos llamados puntos evento, que también fueron comentados en el apartado anterior.

El algoritmo pretende mantener la parte del diagrama de Voronoi por encima de la línea de barrido que nose ve afectada por puntos situados por debajo de dicha línea.

Denotamos l a la línea de barrido y l+ al semiplano por encima de l. Es claro que la distancia de un punto q perteneciente a l+ a cualquier lugar por debajo de l es mayor que la distancia de q a l, esto significa que los puntos más cercanos a q no pueden estar por debajo de l si q es al menos tan cercano a algún pi

perteneciente a l+ como q lo es a l. Los puntos que son mas cercanos a algún punto pi perteneciente a l+

que a l están limitados por una parábola, por lo tanto el lugar de los puntos que son mas cercanos a algún punto por encima de l que a l mismo está limitado por arcos parabólicos. A la secuencia de estos arcos parabólicos es lo que llamaremos línea de playa o frente parabólico.

Otra forma de visualizar la línea de playa sería: cada punto pi define una parábola completa Bi, la línea de

playa sería la función que para cada coordenada x pasa por el punto más bajo de todas las parábolas.

Se puede observar que cada línea vertical intersecta exactamente en un único punto del frente parabólico y que los puntos de corte entre arcos consecutivos del frente parabólico caen encima de los lados del Diagrama de Voronoi.

En lugar de mantener la intersección de VOR(P) con l, mantendremos la línea de playa cuando la línea de barrido se va desplazando hacia abajo.

También comentamos en la visión gráfica del algoritmo que cuando la línea de barrido pase exactamente por encima de uno de los puntos, una parábola de ancho 0 se unirá al frente parabólico y a medida que la línea de barrido siga avanzando, un lado del Diagrama de Voronoi irá creciendo. Este punto es lo que denominamos Site Event.

La única forma de que aparezca un nuevo arco en el frente parabólico es a través de un Site Event.

Si denotamos ly a la coordenada y de la línea de barrido, la ecuación de la parábola Bj para el punto

pj=(pj,x,p,jy) será:

También vimos en la visión gráfica del algoritmo, que la única forma de que un arco abandone el frente

parabólico es la aparición de un Circle Event, que formaría un vértice del Diagrama de Voronoi y a partir de ese momento un nuevo lado del Diagrama de Voronoi comenzaría a crecer.

Mientras que todos los Site Events son conocidos al comienzo del barrido, durante el mismo, aparecerán nuevos Circle Events y otros serán eliminados al no poderse producir en la posición actual de la línea de barrido.

La idea es, mantener el frente parabólico en los puntos evento, actualizado estructuras óptimas para el manejo de dichos eventos.

Veamos las estructuras de datos que nos pueden ser útiles.

3.3.3.1. Estructuras de Datos

Para mantener los cambios del frente parabólico según va moviéndose la línea de barrido necesitaremos las siguientes estructuras de datos estándar:

• Una estructura para almacenar el Diagrama de Voronoi en construcción (DCEL)

• Una estructura del estado de la línea de playa (Árbol binario de búsqueda equilibrado).

• Una cola de eventos (Cola con prioridades)

3.3.3.1.1. Estructura DCEL

DCEL son las siglas inglesas de lista de lados doblemente enlazados, ésta será la estructura de datos que utilizaremos para almacenar la parte del Diagrama de Voronoi que vamos generando.

La estructura DCEL, está formada por tres colecciones de registros:

• Lista de vértices: Un registro para un vértice v, almacena las coordenadas de v y un puntero a un lado arbitrario con origen en v.

• Lista de caras: Un registro para una cara c, almacena un puntero a un lado exterior a la cara y otro a uno interior. Podemos ver, que es necesario aplicar una determinada orientación a los lados, ya que hablamos de medios-lados orientados, de esta forma un lado podría considerarse interno a una cara si está orientado en sentido contrario a las agujas del reloj con respecto a la cara.

• Lista de lados: Un registro para un lado l, almacenara un puntero al vértice origen, un puntero a su lado en sentido contrario, un puntero a la cara en la que se encuentra, un puntero al lado siguiente y otro al anterior, todos ellos en el sentido contrario a las agujas del reloj (por ejemplo).

Además, estas estructuras pueden almacenar otras informaciones no necesariamente topológicas, como colores...

3.3.3.1.2. Árbol binario de búsqueda balanceado

Ésta será la estructura que utilizaremos para almacenar el estado de la línea de playa según va avanzando la línea de barrido y se van tratando los eventos.

Las hojas en este árbol corresponden a los arcos del frente parabólico de manera ordenada (la hoja más a la izquierda representa el arco más a la izquierda).

Cada hoja tiene un puntero al punto que define esa parábola y los nodos internos representan los puntos de corte entre arcos consecutivos del frente parabólico.

Cada hoja mantiene un puntero al nodo de la cola de eventos que representa el Circle Event que hará que este arco desaparezca del frente parabólico.

Además en cada nodo interno se almacena otro puntero al lado de Voronoi que está generando el punto decorte que representa.

3.3.3.1.3. Cola de eventos

En ella guardaremos los eventos, añadiremos nuevos y eliminaremos los que ya no se puedan ejecutar, debido a que puede que ya sean obsoletos.

Se implementa como una cola de prioridades, donde la prioridad de un evento queda determinada por su coordenada y. Para un Site Event se almacena su propia coordenada y, en cambio en un Circle Event se almacenará el punto más bajo del círculo. En el caso de un Circle Event, además se almacenará un puntero a la hoja del árbol binario que representa al arco que desaparecerá del frente parabólico en este evento.

3.3.4. El algoritmo de Fortune

Tenemos ya todas las herramientas necesarias para atacar el algoritmo completamente. Veamos el algoritmo en pseudocódigo:

DIAGRAMA_VORONOI (P)

Entrada: P := {p1,...,pn} un conjunto de n puntos en el plano.

Salida: El Diagrama de Voronoi Vor(P) dentro de un rectángulo en una estructura DCEL.

1. Inicializar la cola de eventos Q con todos los Site Events.

2. mientras Q no esté vacio

3. hacer Considerar el evento con mayor coordenada y de Q.

4. si el evento es un Site Event del punto pi

5. entonces TRATAR_SITE_EVENT (pi)

6. en caso contrario TRATAR_CIRCLE_EVENT(pl), donde pl es el punto más bajo

del círculo que causa el evento.

7. Eliminar el evento de Q.

8. Los nodos internos presentes todavía en T (Árbol binario) pertenecen a los

medios-lados infinitos del Diagrama de Voronoi. Calcular un rectángulo que

contenga todos los vértices del Diagrama de Voronoi en su interior,uniéndole

los medios-lados infinitos, modificando la estructura DCEL apropiadamente.

Nos han surgido dos nuevos procedimientos:

• TRATAR_SITE_EVENT (pi)

• TRATAR_CIRCLE_EVENT(pl)

Veámoslos detenidamente:

TRATAR_SITE_EVENT (pi)

• Buscar en T (Árbol de búsqueda) el arco a que cae verticalmente sobre pi, y borrar todos los

Circle Events que involucran a a de la cola Q.

• Reemplazar la hoja de T que representa a a por un subárbol con tres hojas. En la hoja central almacenaremos el nuevo punto pi y en las otras dos hojas almacenaremos el pj que originalmente

estaba almacenado con a. Almacenamos las tuplas <pj,pi> y <pi,pj> que representan los nuevos

puntos de corte de los dos nuevos nodos internos. Realizar operaciones de rebalanceado de T si es necesario.

• Crear nuevos registros en la estructura del Diagrama de Voronoi (DCEL) para los dos nuevos medios-lados.

• Chequear las tripletas de arcos consecutivos que involucren uno de los tres nuevos arcos. Insertar el correspondiente Circle Event solamente si el círculo intersecta la línea de barrido y el Circle Event no estaba ya en Q.

TRATAR_CIRCLE_EVENT(pl)

• Buscar en T (Árbol de búsqueda) el arco a que cae verticalmente sobre pl, que es el va a

desaparecer, y borrar todos los Circle Events que involucran a a de la cola Q.

• Borrar la hoja que representa a a de T. Actualizar las tuplas que representan los puntos de corte en los nodos internos. Realizar operaciones de rebalanceado de T si es necesario.

• Añadir el centro del círculo que causa el evento como un registro vértice en la estructura del Diagrama de Voronoi (DCEL) y crear dos nuevos medios-lados correspondientes al nuevo punto de corte del Diagrama de Voronoi. Colocar los punteros entre ellos adecuadamente.

• Chequear las nuevas tripletas de arcos consecutivos que surgen debido a la desaparición del arco a. Insertar el correspondiente Circle Event en Q solamente si el círculo intersecta la línea de barrido y el Circle Event no estaba ya en Q.

3.3.5. Complejidad del algoritmo

El algoritmo de Fortune corre con una complejidad O(n log n) y usa O(n) almacenamiento. Veámoslo más detenidamente:

Las operaciones primitivas sobre el árbol de búsqueda T y la cola de eventos Q, tales como, insertar o borrar un elemento toman O(log n) tiempo cada una. Las operaciones primitivas en las estructura DCEL toman tiempo constante. Para tratar un evento, realizamos un número constante de dichas operaciones primitivas, por tanto gastamos O(log n) tiempo en procesar un evento. Obviamente tenemos n Site Events.En cuanto a los Circle Events observamos que cada uno que es procesado define un vértice del Diagrama de Voronoi y que las falsas alarmas son borradas de Q antes de ser procesadas. Estás falsas alarmas son creadas y borradas mientras se procesa un evento real, empleando un tiempo despreciable con respecto al tiempo de proceso del evento. De esta forma el número máximo de Circle Events a procesar es de 2n-5.

De todas estas apreciaciones es sencillo deducir la complejidad anteriormente afirmada.