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 utilizando el tiempo O ( n log n ) y el 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 plano a medida que avanza el algoritmo. La línea de barrido es una línea recta, que por convención podemos asumir que es vertical y 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 aún no se habrán considerado. La línea de la playa no es una línea recta, sino una curva complicada a tramos a la izquierda de la línea de barrido, compuesta por pedazos de parábolas ; divide la parte 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 progresa 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 a través de unos tres puntos de entrada cuyas parábolas forman segmentos consecutivos de la línea de playa). Cada uno de estos eventos puede ser priorizado por la coordenada x de la línea de barrido en el punto en que ocurre el evento. El algoritmo en sí mismo consiste en eliminar repetidamente el siguiente evento de la cola de prioridad, encontrar los cambios que causa 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 árbol de búsqueda binaria y operaciones de cola de prioridad) el el tiempo total es O ( n log n ).
Pseudocódigo
Descripción de pseudocódigo del algoritmo. [4]
dejar ser la transformación , dónde es la distancia euclidiana entre z y el sitio más cercanodeja que T sea la "línea de playa"dejar ser la región cubierta por el sitio p .dejar ser el rayo limítrofe entre los sitios de p y q .dejar Ser los sitios con la coordenada y mínima, ordenados por la coordenada x crear rayos de límite verticales iniciales mientras que no IsEmpty ( Q ) do p ← DeleteMin ( Q ) caso p de p es un sitio en : encontrar la ocurrencia de una región en T que contiene p , entre corchetes por a la izquierda y a la derecha crear nuevos rayos de contorno y con bases p reemplazar con en T eliminar de Q cualquier intersección entre y inserte en Q cualquier intersección entre y inserte en Q cualquier intersección entre y p es un vértice de Voronoi en : sea p la intersección de a la izquierda y a la derecha dejar ser el vecino izquierdo de y dejar ser el vecino correcto de en T crea un nuevo rayo límite Si , o crear si p es derecho de la más alta de q y s , de lo contrario crear reemplazar con recién creado en T eliminar de Q cualquier intersección entre y eliminar de Q cualquier intersección entre y inserte en Q cualquier intersección entre y inserte en Q cualquier intersección entre y registro p como la cumbre de y y la base de generar los segmentos del límite y endcase end whileemitir los rayos de contorno restantes en T
Sitios y discos ponderados
Como describe Fortune en la ref., [1] se puede usar una versión modificada del algoritmo de 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, centrado en los sitios con un radio igual al peso del sitio.
Se pueden usar sitios ponderados para controlar las áreas de las celdas de Voronoi cuando se usan diagramas de Voronoi para construir mapas de árbol . 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 que es una línea recta.
Referencias
- ↑ a b de Berg, Mark ; van Kreveld, Marc ; Overmars, Mark ; Schwarzkopf, Otfried (2000), Computational Geometry (segunda edición revisada), Springer-Verlag , ISBN 3-540-65620-0 Sección 7.2: Cálculo del diagrama de Voronoi: págs.151–160.
- ^ Austin, David, Diagramas de Voronoi y un día en la playa , columna de características, American Mathematical Society.
- ^ Steven Fortune. 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 ACM SpringerLink
- ^ 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.