El algoritmo de la fortuna

Algoritmo de generación de diagramas de Voronoi

Animación del algoritmo de Fortune.

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 usando tiempo O ( n  log  n ) y espacio O( n ). ^{[1] [2]} Fue publicado originalmente por Steven Fortune en 1986 en su artículo "Un algoritmo de línea de barrido para diagramas de Voronoi". ^[3]

Descripción del algoritmo

El algoritmo mantiene tanto una línea de barrido como una línea de playa , que se mueven a través del avión a medida que avanza el algoritmo. La línea de barrido es una línea recta, que por convención podemos suponer que es vertical y que se mueve de izquierda a derecha a través del plano. En cualquier momento durante el algoritmo, los puntos de entrada a la izquierda de la línea de barrido se habrán incorporado al diagrama de Voronoi, mientras que los puntos a la derecha de la línea de barrido no se habrán considerado todavía. La línea de playa no es una línea recta, sino una complicada curva a trozos a la izquierda de la línea de barrido, compuesta de trozos de parábolas ; divide la porción del plano dentro de la cual se puede conocer el diagrama de Voronoi, independientemente de qué otros puntos puedan estar a la derecha de la línea de barrido, del resto del plano. Para cada punto a la izquierda de la línea de barrido, se puede definir una parábola de puntos equidistantes de ese punto y de la línea de barrido; la línea de playa es el límite de la unión de estas parábolas. A medida que avanza la línea de barrido, los vértices de la línea de playa, en la que se cruzan dos parábolas, trazan los bordes del diagrama de Voronoi. La línea de playa avanza manteniendo cada base de parábola exactamente a medio camino entre los puntos inicialmente barridos con 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 utilizando la línea de barrido como directriz y el punto de entrada como foco.

El algoritmo mantiene como estructuras de datos un árbol de búsqueda binario que describe la estructura combinatoria de la línea de playa y una cola de prioridad que enumera posibles eventos futuros que podrían cambiar la estructura de la línea de playa. Estos eventos incluyen la adición de otra parábola a la línea de playa (cuando la línea de barrido cruza otro punto de entrada) y la eliminación de una curva de la línea de playa (cuando la línea de barrido se vuelve tangente a un círculo que pasa por unos tres puntos de entrada cuyas parábolas forman segmentos consecutivos de la línea de playa). Cada uno de estos eventos puede tener prioridad según la coordenada x de la línea de barrido en el punto en que ocurre el evento. El algoritmo en sí consiste entonces en eliminar repetidamente el siguiente evento de la cola de prioridad, encontrar los cambios que provoca el evento en la línea de playa y actualizar las estructuras de datos.

Como hay O( n ) eventos para procesar (cada uno asociado con alguna característica del diagrama de Voronoi) y O(log n ) tiempo para procesar un evento (cada uno de los cuales consta de un número constante de operaciones de árbol de búsqueda binaria y cola de prioridad), el el tiempo total es O ( n log n ).

Pseudocódigo

Descripción en pseudocódigo del algoritmo. ^[4]

Sea la transformación , donde es la distancia euclidiana entre z y el sitio más cercano. Sea T la "línea de playa", sea la región cubierta por el sitio p . sea ​​el rayo límite entre los sitios p y q . Sea un conjunto de sitios en los que se aplicará este algoritmo. sean los sitios extraídos de S con una coordenada y mínima , ordenados por la coordenada x , sea DeleteMin( X ) el acto de eliminar el sitio más bajo y más a la izquierda de X (ordenar por y a menos que sean idénticos, en cuyo caso ordenar por x) sea V el mapa de Voronoi de S que se construirá mediante este algoritmo y cree rayos límite verticales iniciales ${\displaystyle \scriptstyle *(z)}$ ${\displaystyle \scriptstyle *(z)=(z_{x},z_{y}+d(z))}$  ${\displaystyle \scriptstyle d(z)}$   ${\displaystyle \scriptstyle R_{p}}$  ${\displaystyle \scriptstyle C_{pq}}$  ${\displaystyle \scriptstyle S}$  ${\displaystyle \scriptstyle p_{1},p_{2},...,p_{m}}$  ${\displaystyle Q\gets {p_{1},p_{2},\dots ,p_{m},S}}$ ${\displaystyle \scriptstyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},\dots ,C_{p_{m-1},p_{m}}^{0}}$ ${\displaystyle T\gets *(R_{p_{1}}),C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2},p_{3}}^{0},\dots ,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$mientras que no IsEmpty( Q ) do  p ← DeleteMin( Q ) caso  p  de  p es un sitio en : ${\displaystyle \scriptstyle *(V)}$ encontrar la aparición de una región en T que contiene p , ${\displaystyle \scriptstyle *(R_{q})}$ entre corchetes a la izquierda y a la derecha crear nuevos rayos límite y con bases p reemplazar con en T eliminar de Q cualquier intersección entre e insertar en Q cualquier intersección entre e insertar en Q cualquier intersección entre y p es un vértice de Voronoi en : let p sea la intersección de a la izquierda y a la derecha sea el vecino izquierdo de y sea el vecino derecho de en T si , cree un nuevo rayo límite ; de ​​lo contrario, si p está a la derecha del mayor de q y s , cree , de lo contrario , cree endif reemplazar con recién creado en T eliminar de Q cualquier intersección entre y eliminar de Q cualquier intersección entre e insertar en Q cualquier intersección entre e insertar en Q cualquier intersección entre y registrar p como la cumbre de y y la base de salida los segmentos de límite y final del caso final ${\displaystyle \scriptstyle C_{rq}}$ ${\displaystyle \scriptstyle C_{qs}}$ ${\displaystyle \scriptstyle C_{pq}^{-}}$ ${\displaystyle \scriptstyle C_{pq}^{+}}$ ${\displaystyle \scriptstyle *(R_{q})}$ ${\displaystyle \scriptstyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$   ${\displaystyle \scriptstyle C_{rq}}$ ${\displaystyle \scriptstyle C_{qs}}$   ${\displaystyle \scriptstyle C_{rq}}$ ${\displaystyle \scriptstyle C_{pq}^{-}}$   ${\displaystyle \scriptstyle C_{pq}^{+}}$ ${\displaystyle \scriptstyle C_{qs}}$  ${\displaystyle \scriptstyle *(V)}$  ${\displaystyle \scriptstyle C_{qr}}$ ${\displaystyle \scriptstyle C_{rs}}$  ${\displaystyle \scriptstyle C_{uq}}$ ${\displaystyle \scriptstyle C_{qr}}$  ${\displaystyle \scriptstyle C_{sv}}$ ${\displaystyle \scriptstyle C_{rs}}$   ${\displaystyle \scriptstyle q_{y}=s_{y}}$ ${\displaystyle \scriptstyle C_{qs}^{0}}$    ${\displaystyle \scriptstyle C_{qs}^{+}}$    ${\displaystyle \scriptstyle C_{qs}^{-}}$  ${\displaystyle \scriptstyle C_{qr},*(R_{r}),C_{rs}}$ ${\displaystyle \scriptstyle C_{qs}}$   ${\displaystyle \scriptstyle C_{uq}}$ ${\displaystyle \scriptstyle C_{qr}}$   ${\displaystyle \scriptstyle C_{rs}}$ ${\displaystyle \scriptstyle C_{sv}}$   ${\displaystyle \scriptstyle C_{uq}}$ ${\displaystyle \scriptstyle C_{qs}}$   ${\displaystyle \scriptstyle C_{qs}}$ ${\displaystyle \scriptstyle C_{sv}}$ ${\displaystyle \scriptstyle C_{qr}}$ ${\displaystyle \scriptstyle C_{rs}}$ ${\displaystyle \scriptstyle C_{qs}}$ ${\displaystyle \scriptstyle C_{qr}}$ ${\displaystyle \scriptstyle C_{rs}}$ generar los rayos límite restantes en T

Sitios y discos ponderados

Sitios ponderados aditivamente

Como describe Fortune en la referencia, ^[1] se puede utilizar una versión modificada del algoritmo de la línea de barrido para construir un diagrama de Voronoi ponderado aditivamente, en el que la distancia a cada sitio se compensa con el peso del sitio; Esto puede verse de manera equivalente como un diagrama de Voronoi de un conjunto de discos, centrados en los sitios con un radio igual al peso del sitio. Se descubre que el algoritmo tiene complejidad temporal, siendo n el número de sitios según la ref. ^[1] ${\displaystyle O(n\log(n))}$

Se pueden usar sitios ponderados para controlar las áreas de las celdas de Voronoi cuando se usan diagramas de Voronoi para construir mapas de árboles . En un diagrama de Voronoi ponderado aditivamente, la bisectriz entre sitios es en general una hipérbola, en contraste con los diagramas de Voronoi no ponderados y los diagramas de potencia de discos para los cuales es una línea recta.

Referencias

1. de Berg, Marcos ; van Kreveld, Marc ; Overmars, Marcos ; Schwarzkopf, Otfried (2000), Geometría computacional (segunda edición revisada), Springer-Verlag , ISBN 3-540-65620-0Sección 7.2: Calcular el diagrama de Voronoi: páginas 151-160.
2. Austin, David, Diagramas de Voronoi y un día en la playa, columna destacada, Sociedad Matemática Estadounidense.
3. Steven Fortuna. Un algoritmo de línea de barrido para diagramas de Voronoi. Actas del segundo simposio anual sobre geometría computacional . Yorktown Heights, Nueva York, Estados Unidos, págs. 313–322. 1986. ISBN 0-89791-194-6 . Biblioteca digital ACMSpringerLink 
4. Kenny Wong, Hausi A. Müller , Una implementación eficiente del algoritmo de barrido plano de Fortune para diagramas de Voronoi , CiteSeerX 10.1.1.83.5571 .

enlaces externos

• Implementación de C de Steven Fortune
• Algoritmo Voronoi de Fortune implementado en C++
• Algoritmo de Fortune implementado en JavaScript
• Visualización del algoritmo de Fortune