Erzeugung von Voronoi-Diagrammen mit dem Algorithmus von Fortune: Ein O(n log n)-Kopfschmerz

Dieser Artikel taucht tief in die Komplexitäten der Erzeugung von Voronoi-Diagrammen mit dem Algorithmus von Fortune in O(n log n) Zeit ein. Der Autor gibt zu, dass die Implementierung weitaus schwieriger war als erwartet, und empfiehlt, einen einfacheren O(n²)-Ansatz oder eine Bibliothek zu verwenden, es sei denn, Sie müssen viele große Diagramme pro Sekunde verarbeiten. Der Artikel erklärt gründlich Voronoi-Diagramme, die Prinzipien des Algorithmus von Fortune (einschließlich Sweep-Line, Beach-Line, Ereigniswarteschlange, Parabeln usw.) und die Datenstrukturen und die Ereignisverarbeitung des Algorithmus, wie z. B. Site-Events, Circle-Events, unvollständige Kanten, Halb-Kanten usw. Trotz seiner Komplexität erzeugt der Algorithmus visuell beeindruckende Voronoi-Diagramme.