Voronoi-Diagramme mit Fortunes Algorithmus erzeugen

 (redpenguin101.github.io)
2 Punkte von GN⁺ 2025-02-10 | 1 Kommentare | Auf WhatsApp teilen
  • Fortune’s Algorithm kann Voronoi-Diagramme in O(n log n) erzeugen, ist aber schwer zu implementieren; außer wenn große Diagramme wiederholt erzeugt werden müssen, ist eine O(n²)-Implementierung oder eine Bibliothek oft praktikabler
  • Ein Voronoi-Diagramm teilt die Ebene anhand mehrerer Sites in jeweils nächstgelegene Regionen; die Grenzen werden durch Punkte gebildet, die zu zwei Sites den gleichen Abstand haben
  • Der Algorithmus verwaltet eine von links nach rechts laufende Sweep Line und die aus Parabelbögen bestehende Front Beachline und verarbeitet nur Site Events und Circle Events
  • Ein Site Event fügt einen neuen Bogen ein, teilt einen bestehenden Bogen und erzeugt eine incomplete edge; ein Circle Event entfernt den mittleren Bogen und vervollständigt dabei einen Voronoi-Vertex und Half Edges
  • In einer praktischen Implementierung müssen Event-Queue, Beachline, eine Map für incomplete edges und eine DCEL zusammen verwaltet werden; das Entfernen ungültiger Circle Events und das Aufräumen verbleibender Edges erhöht die Komplexität deutlich

Implementierungskomplexität und Einsatzbereich

  • Fortune’s Algorithm ist ein Algorithmus zur Erzeugung von Voronoi-Diagrammen in O(n log n)
  • Für den praktischen Einsatz ist es oft sinnvoller, zunächst den benötigten Umfang zu prüfen, statt sofort selbst zu implementieren
    • Wenn nicht mehrere große Diagramme pro Sekunde erzeugt werden müssen, kann eine O(n²)-Implementierung die einfachere Wahl sein
    • Eine realistischere Alternative ist die Nutzung einer vorhandenen Bibliothek
  • Das Ergebnis des Algorithmus ist visuell interessant, aber die Implementierung ist anspruchsvoll und oft frustrierend

Grundkonzept des Voronoi-Diagramms

  • Ein Voronoi-Diagramm ist eine Methode, eine Ebene in mehrere Regionen zu unterteilen, und wird häufig für die prozedurale Kartengenerierung verwendet
  • Die als Eingabe gewählten Punkte werden Sites oder Seeds genannt
  • Die zu einer Site gehörende Cell ist die Menge aller Punkte der Ebene, die dieser Site am nächsten liegen
  • Die Grenzen einer Cell bestehen aus Punkten, die zu zwei Sites den gleichen Abstand haben
  • Ein Voronoi-Vertex, an dem sich Zellkanten treffen, ist ein Punkt mit gleichem Abstand zu drei Sites

Sweep Line, Beachline, Event

  • Fortune’s Algorithm verwendet eine vertikale Sweep Line, die sich von links nach rechts bewegt
  • Trifft die Sweep Line auf eine Site, entsteht ein Parabelbogen mit dieser Site als Fokus; je weiter sich die Sweep Line entfernt, desto größer wird der Bogen
  • Der Schnittpunkt zweier Bögen unterschiedlicher Sites hat zu beiden Sites den gleichen Abstand und bildet daher eine Zellgrenze
  • Treffen zwei Grenzen aufeinander, entsteht ein Eckpunkt des Diagramms
  • Die Front der aktiven Bögen wird Beachline genannt
  • Eine reale Implementierung verschiebt die Sweep Line nicht pixelweise, sondern verarbeitet nur berechenbare Sonderpunkte, sogenannte Events
    • Site Event: durch eine bereits bekannte Site-Koordinate definiert; bei der Verarbeitung wird der Beachline ein neuer Bogen hinzugefügt
    • Circle Event: durch drei Bögen der Beachline definiert; bei der Verarbeitung wird ein Bogen entfernt und ein Voronoi-Vertex sowie Half Edges werden erzeugt

Grenzen mit Parabeln finden

  • Im Algorithmus werden Parabeln nicht in der üblichen Form y = ax^2 + bx + c behandelt, sondern über die Locus-Definition
  • Eine Parabel wird durch einen Fokuspunkt und eine Direktrix definiert
    • Der Fokuspunkt ist die Site
    • Die Direktrix ist die Sweep Line
  • Der Schnittpunkt zweier Parabeln mit derselben Sweep Line als Direktrix hat zu beiden Sites den gleichen Abstand
  • Daher lässt sich durch das Finden des Schnittpunkts zweier Parabeln die equiedge zwischen zwei Sites bestimmen
  • Verwendet werden Pseudocode zur Berechnung der x-Koordinate einer Parabel sowie ein Beispiel dafür, wie sich der Schnittpunkt zweier Parabeln bei veränderter Position der Sweep Line entlang der Grenze bewegt

Darstellung der Beachline und Verarbeitung von Site Events

  • Jeder Bogen der Beachline kann allein durch die Koordinaten seiner Site dargestellt werden
    • Die Sweep Line gilt für alle Bögen gemeinsam
    • In der Implementierung werden Bögen nicht als eigene Objekte, sondern als 2D-Koordinaten behandelt
  • Die Beachline kann als einfache Reihenfolge von Punkten dargestellt werden
    • Beispiel: [arc1, arc2], [arc1, arc2, arc3]
    • Bögen derselben Site können mehrfach in der Beachline erscheinen
    • Beispiel: [arc1, arc3, arc1, arc2]
  • Tritt ein Site Event auf, wird der Bogen der Beachline gesucht, den eine vom neuen Site-Punkt nach links gezogene Linie zuerst trifft; der neue Bogen teilt dann diesen Bogen
  • Wenn eine neue Site L in einer bestehenden Beachline [.., i, j, k, ..] den Bogen j teilt, entsteht die Struktur [.., i, j, L, j, k, ..]
  • Die Sites werden nach ihrer x-Koordinate sortiert in die Queue eingefügt, und bei jeder Verarbeitung werden Beachline und Event-Kandidaten aktualisiert

Circle Event und Umkreis

  • In einer Beachline mit drei Bögen [.., i, j, k, ..] kann eine Situation entstehen, in der zwei Grenzen zusammentreffen und der mittlere Bogen j verschwindet
  • Dabei existiert ein Umkreis durch die drei Sites, dessen Mittelpunkt zu allen drei Sites den gleichen Abstand hat
  • Der Mittelpunkt dieses Umkreises wird zum Voronoi-Vertex
  • Das Circle Event wird anhand des Circle Point, also des rechten Endpunkts des Kreises, in die Event-Queue eingeordnet
  • Wird vor Erreichen des Circle Point eine neue Site innerhalb des Kreises gefunden, wird das bestehende Circle Event ungültig
    • Die neue Site teilt den mittleren Bogen zuerst, sodass die Kombination der drei Bögen nicht mehr erhalten bleibt
    • Das bisherige Triple i, j, k verschwindet, und neue Tripel wie i, j, L und L, j, k müssen geprüft werden

Incomplete Edge und Half Edge

  • Eine incomplete edge ist eine Linie, bei der ein Endpunkt feststeht, während der andere durch den Schnittpunkt zweier Parabelbögen definiert wird
  • Wenn durch ein Site Event ein neuer Bogen eingefügt wird, entstehen zwei incomplete edges
    • Der feste Punkt ist die Koordinate, an der der neue Bogen auf die bestehende Beachline trifft
    • Wenn der neue Bogen j einen bestehenden Bogen i teilt, entstehen Edges zu den Schnittpunkten [i, j] und [j, i]
  • Wenn bei einem Circle Event zwei incomplete edges zusammenstoßen, wird dieser Kollisionspunkt zum Voronoi-Vertex
  • Die bisherigen incomplete edges werden an diesem Punkt zu Half Edges vervollständigt, und zwischen den nun benachbarten Bögen entsteht eine neue incomplete edge

Nur gegen den Uhrzeigersinn orientierte Kreise werden zu Circle Events

  • Wenn die Beachline [i, j, k, j, i] enthält, können ijk und kji zwar beide einen Kreis bilden, aber nicht beide sind gültige Circle Events
  • Der mittlere Bogen verschwindet nur auf der Seite, auf der die Grenzen tatsächlich konvergieren
  • Im Programm wird die Orientierung von drei Punkten über die Determinante bestimmt
    • Ist die Determinante negativ, liegt eine Orientierung gegen den Uhrzeigersinn vor und es gibt ein Circle Event
    • Ist die Determinante positiv, liegt eine Orientierung im Uhrzeigersinn vor und es gibt kein Circle Event
    • Ist die Determinante 0, liegen die drei Punkte auf einer Geraden und es gibt keinen Kreis

Gesamtablauf des Algorithmus

  • Die Eingabe-Sites werden nach der x-Koordinate sortiert und als Site Events in die Queue eingefügt
  • Bis die Queue leer ist, wird jeweils das nächste Event entnommen und verarbeitet
  • Verarbeitung eines Site Events:
    • Unter den noch ausstehenden Circle Events werden die entfernt, bei denen die neue Site in den Kreis fällt
    • Der Bogen der Beachline, den die neue Site teilen wird, wird gesucht
    • Der neue Bogen wird eingefügt und teilt den bestehenden Bogen
    • Zwei incomplete edges werden hinzugefügt
    • Es wird geprüft, ob neu entstandene Tripel Circle Events erzeugen können
  • Verarbeitung eines Circle Events:
    • Der Mittelpunkt des Umkreises wird als Voronoi-Vertex hinzugefügt
    • Der mittlere Bogen wird aus der Beachline entfernt
    • Zukünftige Circle Events, die durch das Entfernen dieses Bogens ungültig werden, werden gelöscht
    • Die Tripel der neu benachbarten Bögen werden geprüft und gegebenenfalls als Circle Events hinzugefügt
  • Wenn die Queue leer ist, werden die verbleibenden incomplete edges bis zum Rand des Diagramms verlängert, und an deren Schnittpunkten mit dem Rand werden Voronoi-Vertices erzeugt

Datenstrukturen der Odin-Implementierung

  • Die Beispielimplementierung ist in Odin geschrieben, einer alternativen Sprache zu C
  • Der vollständige Code befindet sich im Repository RedPenguin101/voronoi
  • Grundlegende Typen:
    • V2: ein 2D-Punkt in der Form [2]int
    • PointPair: ein Paar aus zwei V2
    • Event: die Struktur {site: bool, a, b, c: V2}
  • Die Bedeutung von Event hängt vom Typ ab
    • Bei einem Site Event ist a die Koordinate der Site, b und c werden nicht verwendet
    • Bei einem Circle Event sind a, b und c die drei Bögen der Beachline, die das Event erzeugen
  • Die Struktur Fortune verwaltet den folgenden Zustand
    • beachline: Array von V2
    • queue: Array von Event
    • incomplete_edges: Map PointPair -> V2
    • vd: eine DCEL zum Speichern des Voronoi-Diagramms

In der Implementierung ausgelassene oder vereinfachte Teile

  • Die Beachline wird als Vektor dargestellt, für höhere Effizienz wäre jedoch ein Binärbaum besser geeignet
  • Auch die Event-Queue ist konzeptionell eine Priority Queue, in der Beispielimplementierung wird sie jedoch per sortierter Einfügung in ein Array verwaltet
  • Die Ungültigmachung von Circle Events erfolgt durch Iteration über zukünftige Events; es gibt ein TODO für eine schnellere Methode
  • clean_beachline_edges ist ein Verfahren, das an beiden Enden der Beachline unnötige Bögen abschneidet
  • Die Implementierung enthält Sonderbehandlungen für Sites mit gleicher x-Koordinate, für Fälle, in denen Circle Point und Site zusammenfallen, sowie für Kollisionen von Referenzpunkten
  • Der letzte Schritt, bei dem nach leerer Queue verbleibende incomplete edges, Half Edges ohne Twin und Vertices bereinigt werden, wird nur als einfache mathematische Verarbeitung behandelt

Voronoi-Diagramme mit einer DCEL speichern

  • Voronoi-Diagramme werden üblicherweise in einer Doubly Connected Edge List (DCEL) gespeichert
  • Eine DCEL ist eine Datenstruktur, die ein aus Vertices und Edges bestehendes Cell-Complex so darstellt, dass es sich leicht bearbeiten lässt
  • Die Darstellung ist kantenzentriert, speichert aber auch Informationen zu Vertices und Faces
  • Eine normale Edge ist ungerichtet, in einer DCEL wird jede Edge jedoch als zwei entgegengesetzte Half Edges gespeichert
  • In einem Voronoi-Diagramm sind die in der DCEL gespeicherten Vertices keine Sites, sondern Voronoi-Vertices
  • Das Ziel einer Edge E erhält man über E.twin.origin, und das rechte Face über E.twin.left

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-02-10
Hacker-News-Kommentare

  • Ich habe früher eine Implementierung in ClojureScript gebaut, die den Ablauf des Fortune-Algorithmus animiert zeigt: https://voronoi.ajwerner.net/#/app-diagrams
    Ein wirklich schöner Algorithmus
    Allerdings mochte ich den Fortune-Algorithmus nach diesem Projekt etwas weniger, weil seine numerische Stabilität bei Gleitkommazahlen nicht gut ist
    Wenn Punkte kollinear sind oder nach Gleitkomma-Maßstäben fast kollinear liegen, kann er kaputtgehen
    Wenn ich mich richtig erinnere, ist delaunator in dieser Hinsicht besser: https://github.com/mapbox/delaunator

    • Die Animation ist die beste, die ich bisher gesehen habe
      Auf der Referenzseite sehe ich einen Link zur „old“-Implementierung; ich frage mich, ob es eine Chance gibt, dass auch die aktuelle Animationsversion als Open Source veröffentlicht wird

  • Vor ein paar Jahren habe ich so eine 3D-Visualisierung erstellt: https://x.com/KangarooPhysics/status/1253336959755251716

  • Es gibt eine JavaScript-Implementierung von Raymond Hill, bekannt durch uBlock Origin: https://github.com/gorhill/Javascript-Voronoi
    Ich habe hier ein wenig daran herumgebastelt, damit sie sich bewegt: https://animations.adgent.com/voronoi.html

    • Diese Animation erinnert an den Stil von A Scanner Darkly (2006)
      Ich frage mich, ob man ein Video als Eingabe nehmen und es in einen Algorithmus stecken könnte, der es auf Voronoi-Art darstellt
      An dem Punkt wäre es streng genommen vielleicht kein Voronoi-Diagramm mehr, aber es sähe ziemlich cool aus

  • D3.js hat eine neue Implementierung: https://github.com/d3/d3-delaunay
    Weiter unten auf dieser Seite gibt es eine Erklärung des verwendeten Sweep-Algorithmus sowie eine Liste von Implementierungen in anderen Sprachen als JavaScript
    Das bisherige d3-voronoi ist zur Abschaffung vorgesehen, ist aber hier zu finden: https://github.com/d3/d3-voronoi

  • Wenn einen die Kanten nicht interessieren und man nur jeden Punkt in einer anderen Farbe einfärben möchte, kann man eine Variante von Flood Fill verwenden, die bei den Seed-Punkten startet
    Man legt ein Pixel nur dann auf den Stack, wenn die Distanz dieser Farbe kürzer ist als die der bereits auf dieses Pixel gemalten Farbe

    • Man kann eine 3D-Szene aus verschiedenfarbigen geraden Kreiskegeln bauen, deren Spitzen an den jeweiligen Punkten der 2D-Ebene liegen, und die Achse senkrecht zur Ebene ausrichten
      Rendert man von oberhalb der Spitzen mit einer orthografischen 2D-Projektion, bewahrt der z-Buffer das Pixel der nächstgelegenen Spitze
      Das ließe sich sicher auch per Shader machen, aber eine klassische 3D-Kegel-Demo ist sehr leicht zu verstehen und umzusetzen

  • Interessant, dass D3 vom Fortune-Algorithmus zu https://mapbox.github.io/delaunator/ gewechselt ist
    Der Grund lautet, dass es beim Erstellen von Delaunay-Triangulationen oder Voronoi-Diagrammen 5- bis 10-mal schneller als d3-voronoi ist, numerisch robuster, Canvas-Rendering eingebaut hat und Traversierung des Delaunay-Graphen sowie mehrere Verbesserungen bietet

    • Wenn D3 delaunator für solche Effekte als die beste Wahl ansieht, bleibt mir jetzt als Ausrede, es nicht in meine Canvas-Bibliothek aufzunehmen, nur noch mein natürliches Aufschieben
      Der Code, der derzeit die Kacheln berechnet, ist schmerzhaft naiv
      Neue Diskussion: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

  • Dieser Beitrag hat mich dazu gebracht nachzusehen, wo Steve heutzutage ist
    Ich kannte ihn vor Jahrzehnten

  • Ein verwandter lesenswerter Beitrag: https://news.ycombinator.com/item?id=37998923 – Voronoi-Diagramme und Delaunay-Triangulationen in O(n log n) mit dem Fortune-Algorithmus erstellen (2020)
    Im früheren Beitrag und in der Diskussion gibt es auch kurze Zusammenfassungen anderer Algorithmen
    Persönlich gefällt mir immer noch der Jump Flooding Algorithm am besten: https://en.wikipedia.org/wiki/Jump_flooding_algorithm