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]
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 podemos suponer por convención 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 playa no es una línea recta, sino una curva complicada, por partes , a la izquierda de la línea de barrido, compuesta por partes 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 mitad de camino entre los puntos barridos inicialmente 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 binario de búsqueda que describe la estructura combinatoria de la línea de playa y una cola de prioridad que enumera los 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 priorizarse por la coordenada x de la línea de barrido en el punto en el que ocurre el evento. El algoritmo en sí consiste entonces en eliminar repetidamente el próximo evento de la cola de prioridad, encontrar los cambios que el evento causa 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 compuesto por un número constante de operaciones de árbol de búsqueda binaria y cola de prioridad), el tiempo total es O( n log n ).
Descripción del algoritmo en pseudocódigo . [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 la 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á con este algoritmo crear rayos límite verticales iniciales mientras no IsEmpty( Q ) haga p ← DeleteMin( Q ) caso p de p es un sitio en : Encuentra la ocurrencia de una región en T que contenga p , entre corchetes a la izquierda y a la derecha crea nuevos rayos límite y con bases p reemplaza con en T elimina de Q cualquier intersección entre y inserta en Q cualquier intersección entre e inserta 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 sea el vecino izquierdo de y sea el vecino derecho de en T si , crea un nuevo rayo límite de lo contrario si p está a la derecha del mayor de q y s , crea de lo contrario crea endif reemplaza con recién creado en T elimina de Q cualquier intersección entre y elimina de Q cualquier intersección entre e inserta en Q cualquier intersección entre e inserta en Q cualquier intersección entre y registra p como la cumbre de y y la base de genera los segmentos límite y endcase endwhile generar los rayos de contorno restantes en T
Como Fortune describe en la referencia [1], se puede utilizar una versión modificada del algoritmo de línea de barrido para construir un diagrama de Voronoi con ponderación aditiva, en el que la distancia a cada sitio se compensa con el peso del sitio; esto se puede ver 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 una complejidad temporal donde n es el número de sitios según la referencia [1] .
Los sitios ponderados se pueden utilizar para controlar las áreas de las celdas de Voronoi cuando se utilizan diagramas de Voronoi para construir mapas de árboles . En un diagrama de Voronoi con ponderación aditiva, la bisectriz entre los 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.
