Algoritmo de la fortuna

El algoritmo de Fortune es un algoritmo de línea de barrido para generar un diagrama de Voronoi a partir de un conjunto de puntos en un plano en el tiempo O utilizando la memoria O( n ) [1] [2] . El algoritmo fue publicado originalmente por Stephen Fortune en 1986 en su artículo "The Sweeping Line Algorithm for Voronoi Diagrams" [3] . ${\ estilo de visualización (n \ registro n)}$

Descripción del algoritmo

El algoritmo mantiene una línea recta de barrido y una costa que se mueve a lo largo del plano a medida que se ejecuta el algoritmo. Una línea de barrido es una línea que tradicionalmente podemos considerar como vertical y que se mueve de izquierda a derecha. En cualquier momento de la operación del algoritmo, los puntos del conjunto a la izquierda de la línea de barrido se incluirán en el diagrama de Voronoi, mientras que los puntos a la derecha de la línea de barrido aún no se han resuelto. La línea de costa no es una línea recta, sino compleja, que consta de piezas de parábolas , una curva por partes a la izquierda de la línea de barrido. Separa una porción del plano dentro del cual se puede conocer el diagrama de Voronoi, independientemente de otros puntos a la derecha de la línea de barrido. Para cada punto a la izquierda de la línea de barrido, puede definir una parábola para un punto que sea equidistante tanto de este punto como de la línea de barrido. La línea de costa es el límite de las asociaciones de estas parábolas. A medida que se mueve la parte superior recta de la línea de costa, en la que se cruzan dos parábolas, se dibujan los bordes del diagrama de Voronoi. La línea de costa avanza manteniendo la base de cada parábola exactamente a medio camino entre la posición inicial de la línea de barrido y la nueva posición de la línea de barrido. Matemáticamente, esto significa que cada parábola se forma usando una línea de barrido como directriz , y un punto dado del conjunto sirve como foco.

El algoritmo mantiene una estructura de datos de árbol binario que describe la estructura combinatoria de la línea de costa y una cola de prioridad que enumera posibles eventos futuros que podrían cambiar la estructura de la línea de costa. Estos eventos incluyen agregar otra parábola a la línea de costa (cuando la línea de barrido pasa por otro punto de entrada) y eliminar una curva de la línea de costa (cuando la línea de barrido se vuelve tangente al círculo a través de unos tres puntos de entrada cuyas parábolas forman segmentos de costa sucesivos). Cada uno de estos eventos puede ser priorizado por la coordenada x de la línea de barrido en el punto donde ocurrió el evento. El algoritmo consiste en eliminar secuencialmente un evento de la cola de prioridad, encontrar cambios en los eventos en la línea de costa y actualizar la estructura de datos.

Dado que hay O( n ) eventos para procesar (cada uno asociado con alguna propiedad del diagrama de Voronoi) y O(log n ) tiempo para procesar un evento (que consiste en un número constante de búsquedas de árboles binarios y operaciones de cola de prioridad), el el tiempo total es . $O(n\log n)$

Pseudocódigo

Pseudocódigo del algoritmo [4] .

Que sea una transformación ,

{\ estilo de visualización * (z)}

{\ estilo de visualización * (z) = (z_ {x}, z_ {y} + d (z))}

donde es la distancia euclidiana entre z y el punto más cercano

{\ estilo de visualización d (z)}

Sea T la "línea de costa" Sea el área que cubre el punto p .

R_{p}

Sea el rayo límite entre los puntos p y q .

{\ Displaystyle C_ {pq}}

Sean puntos con la coordenada y mínima, ordenados por la coordenada x , crean rayos límite verticales iniciales hasta que se ejecuta IsEmpty( Q ) si p es un punto en :

{\displaystyle p_{1},p_{2},...,p_{m))

Q\obtiene S-{p_{1},p_{2},...,p_{m))

C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},...C_{p_{m-1},p_ {m}}^{0}

T\obtiene *(R_{p_{1}}),C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2 },p_{3}}^{0},...,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*( R_{p_{m}})

p\obtiene \mathrm {DeleteMin} (Q)

{\ estilo de visualización * (V)}

Encuentre una región en T que contenga p ,

{\ estilo de visualización * (R_ {q})}

delimitado por una curva a la izquierda y una curva a la derecha

{\ Displaystyle C_ {rq}}

{\ Displaystyle C_ {qs}}

cree nuevos rayos de límite y con base p reemplace con en T elimine de Q cualquier intersección entre e inserte cualquier intersección en Q e inserte cualquier intersección en Q y p es un vértice de Voronoi en :

C_{pq}^{-}

{\displaystyle C_{pq}^{+))

{\ estilo de visualización * (R_ {q})}

{\ estilo de visualización *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}

{\ Displaystyle C_ {rq}}

{\ Displaystyle C_ {qs}}

{\ Displaystyle C_ {rq}}

C_{pq}^{-}

{\displaystyle C_{pq}^{+))

{\ Displaystyle C_ {qs}}

{\ estilo de visualización * (V)}

sea p la intersección de izquierda y derecha

{\ Displaystyle C_ {qr}}

{\ Displaystyle C_ {rs}}

sea el vecino izquierdo y

{\ Displaystyle C_ {uq}}

{\ Displaystyle C_ {qr}}

sea el vecino derecho en T cree un nuevo rayo límite si ,

{\ Displaystyle C_ {sv}}

{\ Displaystyle C_ {rs}}

C_{qs}^{0}

q_{y}=s_{y}

o cree si p es el lado derecho del mayor de q y s ,

{\displaystyle C_{qs}^{+))

de lo contrario, cree reemplazar con el recién creado en T elimine cualquier intersección de Q y elimine cualquier intersección de Q e inserte cualquier intersección en Q e inserte cualquier intersección en Q y escriba p como la parte superior e inferior y genere los segmentos de límite y finalice en caso adiós derivar los rayos límite restantes de T

C_{qs}^{-}

C_{qr},*(R_{r}),C_{rs}

{\ Displaystyle C_ {qs}}

{\ Displaystyle C_ {uq}}

{\ Displaystyle C_ {qr}}

{\ Displaystyle C_ {rs}}

{\ Displaystyle C_ {sv}}

{\ Displaystyle C_ {uq}}

{\ Displaystyle C_ {qs}}

{\ Displaystyle C_ {qs}}

{\ Displaystyle C_ {sv}}

{\ Displaystyle C_ {qr}}

{\ Displaystyle C_ {rs}}

{\ Displaystyle C_ {qs}}

{\ Displaystyle C_ {qr}}

{\ Displaystyle C_ {rs}}

Lados y discos lastrados

Como señala Fortune [5] , se puede utilizar una versión modificada del algoritmo de la línea de barrido para construir un diagrama de Voronoi ponderado de forma aditiva en el que la distancia a cada punto se neutraliza por el peso del punto. Esto se puede ver de manera equivalente como un diagrama de Voronoi de un conjunto de discos centrados en los puntos y con un radio igual al peso del punto.

Los puntos ponderados se pueden usar para controlar las áreas de las celdas de Voronoi cuando las parcelas de Voronoi se usan para construir mapas de árboles . En un diagrama de Voronoi con ponderación aditiva, la bisectriz entre puntos es generalmente una hipérbola, en contraste con los diagramas de Voronoi no ponderados y los diagramas de energía de disco

Notas

↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000 , p. 151-160.
↑ Austin - Columna de funciones .
↑ Fortuna, 1986 , p. 313-322.
↑ Wong, Muller .
↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000 , p. 151-160.

Literatura