Generando Diagramas de Voronoi con el Algoritmo de Fortune: Un Dolor de Cabeza O(n log n)

Este artículo se adentra en las complejidades de generar diagramas de Voronoi utilizando el Algoritmo de Fortune en tiempo O(n log n). El autor admite que la implementación fue mucho más desafiante de lo anticipado y recomienda usar un enfoque O(n²) más simple o una biblioteca, a menos que necesite procesar muchos diagramas grandes por segundo. El artículo explica a fondo los diagramas de Voronoi, los principios del Algoritmo de Fortune (incluyendo línea de barrido, línea de playa, cola de eventos, parábolas, etc.) y las estructuras de datos y el manejo de eventos del algoritmo, como eventos de sitio, eventos de círculo, aristas incompletas, medias aristas, etc. A pesar de su complejidad, el algoritmo produce diagramas de Voronoi visualmente impresionantes.