Voronoi-Diagramm

Grundidee und Definition

Ein Voronoi-Diagramm, auch Thiessen-Polygone oder Dirichlet-Zerlegung genannt, zerlegt einen Raum anhand einer vorgegebenen Menge von Punkten, den Zentren, in Voronoi-Regionen. Jede Region gehört genau einem Zentrum und enthält alle Raumpunkte, die bezüglich der euklidischen Metrik näher an diesem Zentrum liegen als an jedem anderen Zentrum.

Die Grenzen entstehen dort, wo ein Punkt mehr als ein nächstgelegenes Zentrum besitzt. Im zweidimensionalen Fall kann jede Region als Schnitt mehrerer offener Halbebenen aufgefasst werden. Die Halbebenen werden durch Bisektoren begrenzt, also Geraden, die jeweils zwei Zentren in gleichem Abstand teilen.

Für eine Punktmenge S im ℝ² ist die Voronoi-Region des Punktes p ∈ S formal definiert als: VR(p,S) = ⋂q∈S{p} D(p,q)

Dabei gilt: D(p,q) = {x ∈ ℝ² : |p−x| < |q−x|}

Die Vereinigung aller Regionen ist VR(S) = ⋃p∈S VR(p,S). Das Voronoi-Diagramm ergibt sich als V(S) = ℝ² \ VR(S). Informell bilden also die Grenzen der Regionen das Diagramm. Seine Elemente heißen Voronoi-Kanten und Voronoi-Knoten. Jeder Punkt auf einer Voronoi-Kante hat zu den beiden angrenzenden Zentren denselben Abstand.

Metriken, Dualität und Polygon-Methode

Die Form eines Voronoi-Diagramms hängt von der verwendeten Metrik, also der Definition des Abstands, ab. Für zwei Punkte p = (x₁,y₁) und q = (x₂,y₂) lautet der euklidische Abstand: d(p,q) = ‖q−p‖₂ = √((x₁−x₂)² + (y₁−y₂)²)

Beim Manhattan-Abstand gilt: d(p,q) = ‖q−p‖₁ = |x₁−x₂| + |y₁−y₂|

Als Beispiel kann die Zahl der Kunden eines Ladens geschätzt werden. Unter ansonsten gleichen Bedingungen wird angenommen, dass Kunden den nächstgelegenen Laden wählen. Die Voronoi-Zelle eines Ladens beschreibt dann grob das Gebiet seiner potenziellen Kunden.

Das Voronoi-Diagramm ist dual zur Delaunay-Triangulierung. Für jede Voronoi-Kante werden die beiden zugehörigen Zentren verbunden; die Verbindung steht orthogonal auf der Kante. Auf diese Weise entsteht der duale Graph, aus dem die Delaunay-Triangulierung berechnet und eine entsprechend triangulierte Oberfläche konstruiert werden kann.

Die Polygon-Methode ist ein nichtstatistisches Interpolationsverfahren der Geostatistik zur Darstellung der räumlichen Verteilung georeferenzierter Messdaten. Jeder Messwert wird für das ihn umgebende Thiessen-Polygon homogenisiert: Alle Schätzwerte innerhalb dieses Polygons sind identisch mit dem jeweiligen Messwert. Das Verfahren nimmt an, dass die Ähnlichkeit unbekannter Werte mit einem Messwert mit zunehmender Entfernung abnimmt.

An den Polygongrenzen entstehen jedoch scharfe Wertesprünge; fließende Übergänge können nicht dargestellt werden. Deshalb ist die Methode besonders für diskrete, etwa binäre Daten wie „Schneefall: ja/nein“ geeignet.

Berechnung mit Delaunay-Triangulation

Für den zweidimensionalen Fall kann das Voronoi-Diagramm mithilfe der Delaunay-Triangulation in drei Schritten berechnet werden. Zuerst werden die Punkte (x,y) auf den Paraboloiden z = x² + y² im dreidimensionalen Raum abgebildet, also auf Punkte mit den Koordinaten (x,y,x²+y²). Danach wird die konvexe Hülle dieser abgebildeten Punkte berechnet. Eine konvexe Hülle ist die kleinste konvexe Fläche beziehungsweise Menge, die alle Punkte enthält.

Im zweiten Schritt werden diejenigen Flächen der konvexen Hülle ausgewählt, deren Flächennormale nach unten zeigt, und auf die ursprüngliche Ebene zurückprojiziert. Die dabei entstehenden Dreiecke bilden die Delaunay-Triangulation.

Im dritten Schritt werden die Umkreismittelpunkte benachbarter Delaunay-Dreiecke miteinander verbunden. Diese Verbindungen sind die Kanten der Voronoi-Polygone. In drei Dimensionen werden entsprechend die Kugelmittelpunkte von Delaunay-Tetraedern durch Flächen miteinander verbunden. Die Berechnung mithilfe der Delaunay-Triangulation ist für beliebige Dimensionen möglich.

Algorithmus von Fortune

Der Algorithmus von Fortune ist ein Sweep-Line-Algorithmus, der ein Voronoi-Diagramm schrittweise erzeugt. Eine Sweep Line ist eine gedachte, typischerweise vertikale Gerade, die sich von links nach rechts durch die Ebene bewegt. Punkte links der Sweep Line werden bereits verarbeitet, Punkte rechts davon noch nicht.

Zusätzlich verwendet der Algorithmus eine Beach Line. Sie ist keine Gerade, sondern eine stückweise aus Parabelbögen bestehende Kurve links der Sweep Line. Sie trennt den Bereich, in dem das Diagramm bereits bekannt ist, vom noch nicht bestimmten Bereich. Beim Auftreten von Punkt- und Circle-Events werden Parabelbögen eingefügt oder entfernt und Voronoi-Kanten erzeugt beziehungsweise fertiggestellt.

Steven Fortune veröffentlichte den Algorithmus 1986. Seine Laufzeit beträgt O(n · log n), der Speicherbedarf O(n). Der Artikel zeigt außerdem eine C#-Implementierung mit Klassen für Punkte, CircleEvents, Parabelbögen und Voronoi-Kanten. Die Punkte und Ereignisse werden sortiert; CircleEvents werden auf Gültigkeit geprüft, weil sie durch spätere Änderungen der Beach Line verfallen können.

Programmierung durch Pixelzuweisung

Ein im Artikel gezeigtes C++-Programm erzeugt ein zufälliges Voronoi-Diagramm, indem es jedes Pixel eines Bitmaps einzeln dem nächstgelegenen Zentrum zuordnet. Dazu werden zufällige Zentren und zufällige Farben erzeugt. Für jedes Pixel wird zu jedem Zentrum der quadrierte Abstand (x − x₀)² + (y − y₀)² berechnet. Das Zentrum mit dem kleinsten Wert bestimmt die Farbe des Pixels. Anschließend werden die Zentren als schwarze kleine Bereiche eingezeichnet.

Das Programm verwendet ein Bitmap mit der Breite 512 und der Höhe 512 und erzeugt 50 Zentren. Es zeigt das Bild im Konsolenfenster an und speichert es unter dem Dateinamen „VoronoiDiagram.png“. Die Klasse MyBitmap verwaltet dabei die Bitmap, ihre Größe, das Zeichnen einzelner Pixel und das Speichern der Bilddatei.

Anwendungen und Wiederentdeckungen

Voronoi-Diagramme werden unter anderem in Biologie, Chemie, Meteorologie, Kristallographie, Architektur, algorithmischer Geometrie und Materialwissenschaft eingesetzt. Ein Spezialfall im dreidimensionalen Raum ist die Wigner-Seitz-Zelle. Voronoi-Diagramme können auch zur Zerlegung hochdimensionaler Räume verwendet werden; in der Literatur ist die Definition jedoch meist auf den zweidimensionalen reellen Raum beschränkt.

In der Meteorologie dienen sie zur Erstellung von Repräsentativitätskarten, etwa für Niederschlagsgebiete. In sozioökonomischen Untersuchungen werden sie zur Analyse der Erreichbarkeit von Eisenbahnstationen, Haltestellen, Schulen, Krankenhäusern, Geschäften und Grünflächen eingesetzt. Weitere Anwendungen betreffen Transitverkehrszonen und die Abgrenzung von Meereszonen.

Gewichtete Voronoi-Diagramme vergrößern oder verkleinern Voronoi-Zellen abhängig von einem einem Punkt zugeordneten Gewichtungsparameter. Sie werden in dieser Form verwendet, um einen Algorithmus zur Berechnung konvexer Entfernungen in Verkehrsnetzen zu erhalten.

In der klassischen Archäologie und Kunstgeschichte wird die Symmetrie von Statuenköpfen analysiert, um den Typus einer verlorenen Statue zu bestimmen, beispielsweise anhand des 3D-Modells des Kopfes Sabouroff.

In der Fußballanalyse visualisieren Voronoi-Diagramme die Raumkontrolle beider Mannschaften. Die Linien trennen Räume danach, ob sie von Verteidigern oder Angreifern zuerst erreicht werden können. Für eine gute defensive Raumkontrolle sollen in der Nähe des eigenen Tores keine Regionen entstehen, in denen ein Angreifer vor einem Verteidiger den Ball erreichen und eine Torchance erzeugen kann. Abstände liefern dabei nur eine erste Näherung, weil auch Reaktionsgeschwindigkeit, aktuelle Laufrichtung, Geschicklichkeit bei der Balleroberung und der Deckungsschatten berücksichtigt werden müssten.

Das Verfahren wurde mehrfach wiederentdeckt. Im Artikel werden unter anderem P. G. L. Dirichlet (1850, Mathematik, „Dirichlet-Zerlegung“), G. Woronoi (1908, Mathematik), A. H. Thiessen (1911, Meteorologie, „Thiessen-Polygone“), E. P. Wigner und F. Seitz (1933, Physik, „Wigner-Seitz-Zellen“) sowie weitere Entdeckungen in Geologie, Kristallographie, Physik, Ökologie und Anatomie aufgeführt.