Erstellung von Voronoi-Diagrammen mit dem Fortune-Algorithmus

Voronoi-Diagramme erzeugen

• Was ist ein Voronoi-Diagramm?

  • Ein Voronoi-Diagramm ist eine Methode, eine Ebene in mehrere Bereiche zu unterteilen, und wird häufig zur prozeduralen Generierung von Karten verwendet.
  • Auf der Ebene werden mehrere Punkte ausgewählt, die als „Sites“ bezeichnet werden, und der jedem Site entsprechende Bereich enthält alle Punkte, die diesem Site am nächsten liegen.
  • Die Grenzen jedes Bereichs bestehen aus Punkten, die zu zwei Sites den gleichen Abstand haben. Punkte mit gleichem Abstand zu drei Sites werden als „Voronoi-Vertices“ bezeichnet.

• Der Fortune-Algorithmus

  • Der Fortune-Algorithmus ist eine Methode zur Erzeugung des Diagramms mit einer Linie, die die Ebene von links nach rechts „abtastet“.
  • Wenn die Sweep-Line auf einen Site trifft, entsteht darum eine „Blase“ (ein parabelförmiger Bogen), die größer wird, je weiter sich die Sweep-Line entfernt.
  • Wenn die Bögen zweier Sites kollidieren, wird ihr Kollisionspunkt zur Zellgrenze.
  • Die Grenzen aller aktiven Blasen werden als „Beachline“ bezeichnet.

• Begriffserklärungen

  • Site: Ein 2D-Punkt, der die Form des Voronoi-Diagramms bestimmt.
  • Sweep-Line: Eine vertikale Linie, die den Bereich durchquert und jedes Ereignis in der Event Queue verarbeitet.
  • Beachline: Eine aus mehreren Bögen bestehende Linie, bei der beim Verarbeiten von Ereignissen Bögen hinzugefügt oder entfernt werden.
  • Schnittpunkt: Der Punkt, an dem sich zwei Bögen der Beachline treffen und der zu den zugehörigen Sites den gleichen Abstand hat.
  • Event Queue: Der Ort, an dem Site- und Circle-Events gespeichert werden; sortiert in aufsteigender Reihenfolge nach der x-Koordinate.
  • Site-Event: Einer der beiden Event-Typen in der Event Queue, definiert durch die Koordinaten des betreffenden Site.
  • Circle-Event: Der andere Event-Typ in der Queue, definiert durch drei Bögen auf dem Umfang eines Kreises.
  • Voronoi-Vertex: Ein Punkt mit gleichem Abstand zu drei Sites; die Ecke einer Zelle.
  • Äquidistanzgrenze: Eine Linie mit gleichem Abstand zu zwei Sites.
  • Unvollständige Grenze: Eine Linie, deren ein Ende ein fester Punkt ist und deren anderes Ende durch den Schnittpunkt der Brennpunkte zweier Parabeln definiert wird.

• Parabel-Tangenten

  • Das Konzept und die Eigenschaften von Parabeln sind für den Algorithmus sehr wichtig.
  • Eine Parabel wird durch einen Brennpunkt und eine Gerade (Direktrix) definiert.
  • Setzt man die Brennpunkte zweier Sites fest und verwendet die Sweep-Line als Direktrix, kann man durch das Finden des Schnittpunkts zweier Parabeln die Grenzlinie bestimmen, die zu beiden Sites den gleichen Abstand hat.

• Zurück zur Beachline

  • Die Beachline ist an einer gegebenen Position der Sweep-Line die „Grenze“ aller Bögen.
  • Jeder Bogen kann durch den Brennpunkt eines Site dargestellt werden.
  • Die Beachline kann als einfache Sequenz von Punkten dargestellt werden.

• Ein neuer Bogen entsteht, wenn die Sweep-Line auf einen neuen Site trifft

  • Die Beachline ist eine Sequenz von Punkten, wobei jeder Punkt einen Site und einen Bogen repräsentiert.
  • Wenn die Sweep-Line auf einen neuen Site trifft, wird ein neuer Bogen erzeugt und in die Sequenz eingefügt.

• Sich schneidende Grenzen und Umkreise

  • Wenn drei Sites auf dem Umfang eines Kreises liegen, hat dessen Mittelpunkt zu allen drei Punkten den gleichen Abstand.
  • Der Mittelpunkt des Umkreises wird zu einem Voronoi-Vertex.

• Unvollständige Grenzen

  • Eine unvollständige Grenze hat an einem Ende einen festen Punkt und am anderen den Schnittpunkt zweier Bögen.
  • Wenn zwei unvollständige Grenzen kollidieren, entsteht ein Voronoi-Vertex, und die unvollständigen Grenzen werden in Halbgrenzen umgewandelt.

• Nur Kreise gegen den Uhrzeigersinn erzeugen Circle-Events

  • Ein Circle-Event wird nur erzeugt, wenn drei Bögen gegen den Uhrzeigersinn gelesen werden.

• Zusammenfassung

  • Wenn eine Menge von Sites gegeben ist, werden alle Site-Punkte als „Site“-Events in die Queue eingefügt und nach dem x-Wert sortiert.
  • Solange die Queue nicht leer ist, wird das nächste Event aus der Queue entnommen und verarbeitet.
  • Handelt es sich um ein Site-Event, wird ein neuer Bogen zur Beachline hinzugefügt und eine unvollständige Grenze erzeugt.
  • Handelt es sich um ein Circle-Event, wird ein Voronoi-Vertex hinzugefügt und ein Bogen aus der Beachline entfernt.