Los diagramas de Voronoi son uno de esos conceptos matemáticos que podemos encontrar implementados en cualquier parte de la naturaleza. Y su modelización permite resolver problemas a primera vista muy complejos.
Los diagramas de Voronoi son una de las estructuras fundamentales dentro de la Geometría Computacional, y se utilizan para representar gráficamente toda la información referente a la proximidad entre puntos en el espacio bidimensional.
Son numerosísimas sus aplicaciones.
Imaginad, por ejemplo, que queréis diseñar un sistema basado en inteligencia artificial que permita asesorar a entrenadores de fútbol. Los diagramas de Voronoi permitirían, por ejemplo, modelizar el área de influencia de cada equipo dentro del campo en función de la posición de cada jugador.
Suponemos dado un conjunto finito de puntos en el plano P = {p1,…,pn} (con n>=2) y a cada pj le asociamos aquellos puntos del plano que están más cerca o igual suya que de cualquier otro de los pi con i distinto de j. Estas áreas podrían colorearse para que se distinguieran mejor unas de otras, y quedarían así:
Como véis, todos los puntos del plano (campo de fútbol) quedan asociados a algún pi (que representan a uno de los 22 jugadores que están en el campo), formándose conjuntos que recubren a éste.
Las fronteras de cada región no son más que los puntos que distan lo mismo entre dos puntos concretos y conforman regiones que no son más que conjuntos de puntos dentro del plano. Todo punto del plano pertenece a alguno de estos conjuntos y además dichos conjuntos son mutuamente excluyentes salvo en la frontera entre dos regiones.
Una vez entendido el concepto, ahora trataremos de crear un método de cálculo para un diagrama de Voronoi. Básicamente construir el diagrama de Voronoi consiste en trazar la bisectriz entre puntos adyacentes para ir construyendo las fronteras de cada región. Vamos a denotar como h(pi,pj) al semiplano que contiene a pi de entre los dos generados por la bisectriz entre pi y pj. De este modo, los puntos del plano que pertenecen a h(pi,pj) son en realidad aquellos que están más próximos a pi que a pj. Es decir, la intersección de los semiplanos h(p1,pj) es Vor(p1).
Dado que Vor(p1i) es la intersección entre dos planos convexos, siempre será un plano convexo. A partir de aquí, vamos a ver una serie de propiedades que serán útiles a la hora de idear un algorito:
- Lo primero es tener claro que una de las rectas del diagrama puede ser infinita. Una región de Voronoi es no acotada si y sólo si su generador se encuentra en la frontera de la envolvente convexa del plano.
- Los bordes de las regiones de Voronoi son partes de bisectrices entre dos generadores, y los vértices son intersecciones entre dos de esas bisectrices.
- No todas las bisectrices definen un borde, ni todas las intersecciones son vértices. Todo depende de la disposición de los puntos.
- Concepto de círculo máximo vacío : Este problema nos dice lo siguiente.
Dados n puntos en un espacio métrico, se pide encontrar el círculo de mayor radio cuyo centro esté en el interior del cierre convexo de los puntos y que no contenga ninguno en su interior
Este es el típico problema que puede solucionarse de forma sencilla mediante la construcción del diagrama de Voronoi. En este caso, la solución siempre tendrá su centro en uno de los vértices del diagrama, o bien en alguna de las intersecciones de las aristas del diagrama con el cierre convexo del conjunto. Quedáos con este concepto de cara a diseñar el algoritmo.
De momento, vamos a entender las siguientes propiedades relacionadas con el máximo círculo vacío:
Un punto q es vérticie de Vor(P) si y sólo si el círculo máximo vacío centrado en q contiene tres o (en el caso de tratarse de un diagrama degenerado) más generadores en su frontera.
La bisectriz entre dos generadores define un borde de Vor(P) si y sólo si existe un punto q sobre dicha bisectriz tal que el círculo máximo vacío centrado en q contiene solamente a estos dos generadores en su frontera.
Con estos conceptos básicos, diseñemos un algoritmo
En principio podemos barajar estas 4 estrategias para resolver un diagrama de Voronoi, sin embargo sólo una ganará a las demás por ser más eficiente y fácil de implementar:
Método 1: calcular la intersección entre semiplanos.
Podemos tratar de construir cada región de Voronoi por separado mediante la intersección de n-1 semiplanos. Construir n semiplanos nos da una complejidad de O(n · log n). Y tendríamos que hacer esto para cada generador, de modo que la complejidad final sería de O(n² log n).
Método 2: un algoritmo incremental.
Vamos construyendo el diagrama de forma incremental, punto a punto, teniendo presente que si en un momento dado ya lo tenemos calculado para k puntos, el siguiente paso es calcularlo para k+1 puntos.
Consta de los siguientes pasos:
Paso 1: Se elige un punto. Si el nuevo punto está dentro del cierre, no hay nada que hacer. En otro caso, se borran todos los bordes del polígono que se ven desde el punto.
Paso 2: Se añaden dos líneas para conectar el nuevo punto al resto del antiguo cierre.
Paso 3: Se repite de nuevo desde el paso primero con el objetivo de que los puntos que estén fuera del cierre convexo actual, hasta que todos los vértices estén dentro.
Este algoritmo es relativamente sencillo de implementar y su complejidad es O(n²)
Método 3: divide y vencerás.
Este método reduce la complejidad del anterior a O(n · log n). Se trata de “afinar” más, resolviendo un problema a partir de la soluciones de subproblemas más pequeños del mismo tipo.
Paso 1. División: plantear el problema de forma que pueda
ser descompuesto en k subproblemas más pequeños del mismo tipo.
Paso 2. En segundo lugar han de resolverse independientemente todos los subproblemas de forma recursiva, hasta que sean elementales. En el diagrama siguiente muestro como dos diagramas de Voronoi resultantes de dividir el plano entre un lado derecho y otro izquierda, dan lugar a un Voronoi “conjunto”. la forma de fusionar ambos diagramas es calcular la cadena divisoria entre ambos.
El problema de este algoritmo es que, a pesar de que es bastante eficiente, también es muy complejo de implementar.
Método 4: el algoritmo de Fortune
En 1985 Fortune inventó un original algoritmo de barrido plano que resulta tan simple como el algoritmo incremental antes descrito, pero en tiempo O(n log n).
Fortune hizo la inteligente observación de que podía calcularse el diagrama de Voronoi mediante barrido del plano construyendo una versión distorsionada de éste pero que es topológicamente equivalente.
Esta versión distorsionada del diagrama se basa en una transformación que modifica la forma en que las distancias son calculadas en el plano. De esta forma, los segmentos se convierten en unos arcos parabólicos.
El diagrama resultante tiene la misma estructura topológica que el diagrama de Voronoi, pero sus aristas son arcos parabólicos, en vez de segmentos de línea recta.
El método de barrido es la forma más rápida y simple de realizar la pseudotriangulación de una nube de puntos en el plano.
El algoritmo implica la preordenación de los puntos según la dirección definida por una recta de barrido escogida. Sobre esta recta se levanta una perpendicular que va barriendo los puntos e indica el próximo a incluir en la pseudo-triangulación actual, así:
El psoeudocódigo para este algoritmo sería el siguiente:
Deja un comentario