Voronoi-Diagramm

Als Voronoi-Diagramm, auch Thiessen-Polygone oder Dirichlet-Zerlegung, wird eine Zerlegung des Raumes in Regionen bezeichnet, die durch eine vorgegebene Menge an Punkten des Raumes, hier als Zentren bezeichnet, bestimmt werden. Jede Region wird durch genau ein Zentrum bestimmt und umfasst alle Punkte des Raumes, die in Bezug zur euklidischen Metrik näher an dem Zentrum der Region liegen als an jedem anderen Zentrum. Derartige Regionen werden auch als Voronoi-Regionen bezeichnet. Aus allen Punkten, die mehr als ein nächstgelegenes Zentrum besitzen und somit die Grenzen der Regionen bilden, entsteht das Voronoi-Diagramm.

Benannt sind Voronoi-Diagramme nach dem Mathematiker Georgi Feodosjewitsch Woronoi, die alternativen Bezeichnungen leiten sich von Alfred H. Thiessen respektive Peter Gustav Lejeune Dirichlet ab.

Beispiel einer Dirichlet-Zerlegung zu einer vorgegebenen Menge an Punkten

Allgemeines

Das radiale Wachstum aus Startpunkten heraus generiert Voronoi-Regionen. Dies kann beispielsweise Kristall- oder Zellwachstum modellieren.

Voronoi-Diagramme werden in verschiedensten wissenschaftlichen Bereichen wie der Biologie, Chemie, Meteorologie, Kristallographie, Architektur und anderen wissenschaftlichen Disziplinen wie der Algorithmischen Geometrie und der Materialwissenschaft verwendet. Ein Spezialfall des Voronoi-Diagramms im dreidimensionalen Raum ist die Wigner-Seitz-Zelle. Obwohl 1644 schon durch Descartes in seinem Buch Principia Philosophiae erwähnt, erfuhren sie erstmals durch Dirichlet und Voronoi eine genauere mathematische Analyse.^[1] Voronoi-Diagramme können durchaus auch als Zerlegung hochdimensionaler Räume verwendet werden. In der Literatur ist die Definition meist auf den zweidimensionalen reellen Raum beschränkt.

Entdeckungen

Voronoi-Diagramme wurden mehrmals wiederentdeckt.^[2]

Jahr	1850	1908	1909	1911	1927	1933	1958	1965	1966	1985
Entdecker	P. G. L. Dirichlet	G. F. Woronoi	A. K. Boldyrew	A. H. Thiessen	P. Niggli	E. P. Wigner und F. Seitz	F. C. Frank und J. S. Kasper	G. S. Brown[3]	R. Mead[4]	Louis Hoofd
Bereich	Mathematik	Mathematik	Geologie	Meteorologie	Kristallographie	Physik	Physik	Ökologie	Ökologie	Anatomie
Name	Dirichlet-Zerlegung			Thiessen-Polygone	Wirkungsbereiche[5]	Wigner-Seitz-Zellen	Frank-Kasper-Phasen

Definition

Die Thiessen-Polygone oder das Voronoi-Diagramm bestehen aus dem gesamten Raum abzüglich der Voronoi-Regionen, welche in Bezug auf den euklidischen Abstand aus allen Punkten des Raumes entstehen, die näher am korrespondierenden Zentrum liegen als an allen anderen Zentren. Diese können im Zweidimensionalen als Schnitt mehrerer offener Halbebenen betrachtet werden, welche wiederum durch einen Bisektor zwischen je zwei Punkten der Zentren begrenzt werden.

Formal ist eine Voronoi-Region ${\displaystyle VR(p,S)}$ des Punktes ${\displaystyle p\in S}$, wobei ${\displaystyle S}$ eine vorgegebene Menge an Punkten des ${\displaystyle \mathbb {R} ^{2}}$ ist, gegeben durch

${\displaystyle VR(p,S)=\bigcap _{q\in S\setminus \{p\}}D(p,q)}$,

wobei ${\displaystyle D(p,q)}$ als offene Halbebene definiert ist und durch

${\displaystyle D(p,q)=\{x\in \mathbb {R} ^{2}:|p-x|<|q-x|\}}$

gegeben ist. Sind nun alle Voronoi-Regionen durch

${\displaystyle VR(S)=\bigcup _{p\in S}VR(p,S)}$

gegeben, erhält man das Voronoi-Diagramm durch

${\displaystyle V(S)=\mathbb {R} ^{2}\setminus VR(S)}$

Informell bedeutet das, dass genau die Grenzen der Regionen, welche selbst nicht zu diesen dazu gehören, das Diagramm bzw. die Polygone bilden. Die resultierenden Polygone können in Voronoi-Kanten (Kanten des Polygons) und Voronoi-Knoten (Ecken des Polygons) eingeteilt werden. Alle Punkte auf den Voronoi-Kanten haben dabei zu den Punkten ${\displaystyle p\in S}$, deren Voronoi-Region neben der Kante liegen, den gleichen Abstand.

Erstellung des dualen Graphen eines Thiessen-Polygons

Dualität

Das Voronoi-Diagramm verhält sich dual zur Delaunay-Triangulierung und wird zur Konstruktion einer entsprechend triangulierten Oberfläche verwendet.

Um die Delaunay-Triangulierung zu berechnen, wird der entsprechende duale Graph zum Voronoi-Diagramm gebildet. Dies geschieht, indem die Zentren der Polygone derart miteinander verbunden werden, so dass zu jeder Voronoi-Kante eine orthogonale Linie eingezeichnet wird, die die entsprechenden zwei Zentren miteinander verbindet (siehe Abbildung).

Polygon-Methode

Thiessen-Polygone werden unter anderem bei der kartographischen Darstellung von Messwerten eingesetzt. Die Polygon-Methode ist ein nichtstatistisches (d. h. vergleichsweise einfaches) Interpolationsverfahren der Geostatistik zur einfachen Darstellung der räumlichen Verteilung georeferenzierter Messdaten.

Als Grundannahme gilt, dass die Ähnlichkeit des unbekannten Wertes eines Punktes in der Fläche zum bekannten Messwert mit der Entfernung von diesem abnimmt, die Daten also umso unähnlicher sind, je weiter sie auseinanderliegen. Dieser Zusammenhang wird bei der Polygon-Methode dadurch zum Ausdruck gebracht, dass jeder Messwert für ein ihn umgebendes Thiessen-Polygon homogenisiert wird, also alle Schätzwerte innerhalb dieses Polygons identisch zum jeweiligen Messwert sind.

Das Verfahren bildet insofern eine schlechte Näherung an die beobachtbare Realität, da an den Polygongrenzen scharfe Wertesprünge auftreten. Fließende Übergänge zwischen zwei Messwerten können mit dieser Methode also nicht dargestellt werden. Durch diesen Umstand ist die Polygon-Methode wiederum gut geeignet zur flächigen Verteilung von diskreten Daten, etwa binären (z. B. Messwert: „Schneefall: ja/nein“).

Metriken

Voronoi-Diagramm mit euklidischem Abstand

Voronoi-Diagramm mit Manhattan-Abstand

Angenommen, es soll die Anzahl der Kunden eines bestimmten Ladens in einer Stadt geschätzt werden. Bei ansonsten gleichen Bedingungen (Preis, Produkte, Qualität usw.) ist davon auszugehen, dass Kunden in den nächstgelegenen Laden, also den Laden mit dem kleinsten Abstand, gehen. In diesem Fall kann die Voronoi-Zelle eines bestimmten Ladens verwendet werden, um eine grobe Schätzung der Anzahl potenzieller Kunden abzugeben, die diesen Laden besuchen. Die Läden der Stadt werden als Punkte des Voronoi-Diagramms modelliert. Für die meisten Städte kann der Abstand zwischen Punkten als euklidischer Abstand gemessen werden:

${\displaystyle d(p,q)=\|q-p\|_{2}=d\left(\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right)\right)={\sqrt {\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}}}}$

oder als Manhattan-Abstand:

${\displaystyle d(p,q)=\|q-p\|_{1}=d\left(\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right)\right)=|x_{1}-x_{2}|+|y_{1}-y_{2}|}$

Die entsprechenden Voronoi-Diagramme sehen für verschiedene Metriken unterschiedlich aus.

Algorithmus

Eingefärbtes Voronoi-Diagramm mit zufällig verteilten Punkten in der Ebene

Die Berechnung eines Voronoi-Diagramms mithilfe der Delaunay-Triangulation ist für beliebige Dimensionen möglich. Im Folgenden wird ein Algorithmus für den zweidimensionalen Fall beschrieben, der sich analog auf höhere Dimensionen erweitern lässt. Die Berechnung erfolgt in drei Schritten. Zunächst werden alle gegebenen Punkte in der ${\displaystyle x,y}$-Ebene in eine zusätzliche Dimension ${\displaystyle z}$ auf einen (Hyper-)Paraboloid mit den dreidimensionalen Koordinaten ${\displaystyle (x,y,x^{2}+y^{2})}$ projiziert. Von den so gewonnenen Punkten wird die konvexe Hülle berechnet. In einem zweiten Schritt werden alle Flächen der konvexen Hülle, deren Flächennormale nach unten zeigt, wieder auf die ursprüngliche Ebene zurückprojiziert. Die so gewonnenen Regionen sind die Dreiecke der Delaunay-Triangulation. In einem letzten Schritt werden die Umkreismittelpunkte aller Dreiecke zwischen angrenzenden Dreiecken verbunden, was die gesuchten Kanten der Voronoi-Polygone ergibt.

In drei Dimensionen sind entsprechend die Kugelmittelpunkte durch Ecken der Delaunay-Tetraeder mit Flächen zu verbinden.

Pseudocode

Bezeichnungen: Punkte ${\displaystyle P}$, Delaunay-Triangulation ${\displaystyle DT(P)}$, Konvexe Hülle ${\displaystyle KH(P)}$, Voronoi-Diagramm ${\displaystyle V(P)}$.^[6]

 1: Initialisiere leere Mengen P', DT(P) und V(P)
 2:
 3: //Berechnung der konvexen Hülle
 4: Für alle p = (px, py) ${\displaystyle \in }$ P:
 5:    Füge p' = (px, py, px2 + py2) zu P' hinzu
 6: Berechne KH(P') //Mit geeignetem Algorithmus
 7:
 8: //Berechnung der Delaunay-Triangulation
 9: Für alle Seiten s ${\displaystyle \in }$ KH(P'):
10:    Falls Normalenvektor von s nach unten zeigt:
11:       Für alle Kanten k von s:
12:          Setze z-Wert von jedem Knoten ${\displaystyle \in }$ k auf 0
13:          Erstelle neue Kante k' = k
14:          Füge k' zu DT(P) hinzu
15:
16: //Berechnung der Voronoi-Zellen
17: Für alle Dreiecke d in DT(P):
18:    Für alle an d angrenzenden Dreiecke d':
19:       Erstelle Kante m durch Verbindung der Umkreismittelpunkte von d und d'
20:       Füge m zu V(P) hinzu

Algorithmus von Fortune

Der Algorithmus von Fortune ist ein Sweep-Line-Algorithmus, der schrittweise ein Voronoi-Diagramm erzeugt. Die bereits ermittelten Voronoi-Kanten sind jeweils blau, die Sweep Line ist rot und die Beach Line ist schwarz dargestellt.

Der Algorithmus von Fortune ist ein Sweep-Line-Algorithmus, der schrittweise ein Voronoi-Diagramm erzeugt, indem eine sogenannte Sweep Line in einer Richtung durch die Ebene geschoben wird. Die Sweep Line ist eine Gerade, von der man annehmen kann, dass sie vertikal ist und sich von links nach rechts in der Ebene bewegt. Zu jedem Zeitpunkt werden die eingegebenen Punkte links der Sweep Line in das Voronoi-Diagramm eingebaut, während die Punkte rechts der Sweep Line noch nicht berücksichtigt wurden. Außerdem verwendet der Algorithmus von Fortune eine sogenannte Beach Line. Die Beach Line ist keine gerade Linie, sondern eine komplizierte stückweise Kurve links der Sweep Line, die aus Parabelbögen besteht. Die Beach Line teilt den Abschnitt der Ebene, in dem das Voronoi-Diagramm bekannt ist, vom Rest der Ebene, unabhängig von den Punkten rechts der Sweep Linie.

Der Algorithmus wurde 1986 von Steven Fortune veröffentlicht. Die Laufzeit des Algorithmus liegt in ${\displaystyle O(n\cdot \log n)}$ und der Speicherbedarf in ${\displaystyle O(n)}$.^[7]

Das folgende Programm in der Programmiersprache C# zeigt eine Implementierung des Algorithmus von Fortune. Das Voronoi-Diagramm wird auf dem Hauptfenster gezeichnet. Das Programm verwendet mehrere Klassen. Die Methoden für den eigentlichen Algorithmus werden in der Klasse Fortune deklariert.^[8]

Code-Schnipsel

using System; using System.Collections.Generic; using System.Drawing; using System.Windows.Forms; // Diese Klasse implementiert eine Vergleichsmethode für das Sortieren der Punkte class PointComparer : Comparer<PointF> { // Vergleichsmethode, die die Punkte von links nach rechts und bei Gleichheit von oben nach unten sortiert public override int Compare(PointF point1, PointF point2) { int result = point1.X.CompareTo(point2.X); if (result == 0) { return point1.Y.CompareTo(point2.Y); } return result; } } // Diese Klasse implementiert eine Vergleichsmethode für das Sortieren der CircleEvents class EventComparer : Comparer<CircleEvent> { // Vergleichsmethode, die die CircleEvents public override int Compare(CircleEvent event1, CircleEvent event2) { return event1.x.CompareTo(event2.x); } } // Klasse für die CircleEvents class CircleEvent { public double x; // x-Koordinate der Sweep Line public PointF point; // Das Zentrum, das der Brennpunkt der Parabel ist public ParabolaArc arc; // Parabelbogen public bool isValid; // Gibt an, ob das CircleEvent aktuell ist // Konstruktor für die Initialisierung der Attribute public CircleEvent(double _x, PointF _point, ParabolaArc _arc) { x = _x; point = _point; arc = _arc; isValid = true; } }; // Klasse für die Parabelbögen class ParabolaArc { public PointF point; // Das Zentrum, das der Brennpunkt der Parabel ist public ParabolaArc previousArc, nextArc; // Benachbarte Parabelbögen public CircleEvent circleEvent; // Zugeordnetes CircleEvent public VoronoiEdge edge1, edge2; // Benachbarte Voronoi-Kanten // Konstruktor für die Initialisierung der Attribute public ParabolaArc(PointF _point, ParabolaArc arc1, ParabolaArc arc2) { { point = _point; previousArc = arc1; nextArc = arc2; circleEvent = null; edge1 = null; edge2 = null; } } } // Klasse für die Voronoi-Kanten class VoronoiEdge { public PointF point1, point2; // Endpunkte der Kante public bool isFinished; // Gibt an, ob die Kante fertiggestellt wurde public static List<VoronoiEdge> edges = new List<VoronoiEdge>(); // Liste der Kanten // Konstruktor für die Initialisierung der Attribute public VoronoiEdge(PointF point) { point1 = point; // Setzt den ersten Endpunkt point2.X = 0; point2.Y = 0; isFinished = false; edges.Add(this); // Fügt die Kante der Liste hinzu } // Diese Methode stellt die Kante fertig public void Finish(PointF point) { if (!isFinished) { point2 = point; // Setzt den zweiten Endpunkt isFinished = true; } } } // Klasse, die die Methoden für den Algorithmus von Fortune deklariert class Fortune { public ParabolaArc root = null; public List<PointF> points = new List<PointF>(); // Liste der Punkte public List<CircleEvent> circleEvents = new List<CircleEvent>(); // Liste der CircleEvents // Verarbeitet den verbleibenden Punkt (rechts der Sweep Line), der ganz links liegt public void ProcessPoint(double x) { PointF point = points[0]; points.RemoveAt(0); // Entfernt den ersten Punkt aus der Liste AddNewArc(point, x); // Fügt der Beach Line einen Parabelbogen hinzu } // Diese Methode verarbeitet das CircleEvent mit der kleinsten x-Koordinate public void ProcessCircleEvent() { CircleEvent circleEvent = circleEvents[0]; circleEvents.RemoveAt(0); // Entfernt das erste CircleEvent aus der Liste if (circleEvent.isValid) // Wenn das CircleEvent aktuell ist { VoronoiEdge edge = new VoronoiEdge(circleEvent.point); // Erzeugt eine neue Kante // Entfernt den zugehörigen Parabelbogen ParabolaArc arc = circleEvent.arc; if (arc.previousArc != null) { arc.previousArc.nextArc = arc.nextArc; arc.previousArc.edge2 = edge; } if (arc.nextArc != null) { arc.nextArc.previousArc = arc.previousArc; arc.nextArc.edge1 = edge; } // Stellt die benachbarten Kanten des Parabelbogens fertig if (arc.edge1 != null) { arc.edge1.Finish(circleEvent.point); } if (arc.edge2 != null) { arc.edge2.Finish(circleEvent.point); } // Prüft die CircleEvents auf beiden Seiten des Parabelbogens if (arc.previousArc != null) { CheckCircleEvent(arc.previousArc, circleEvent.x); } if (arc.nextArc != null) { CheckCircleEvent(arc.nextArc, circleEvent.x); } } } // Diese Methode fügt einen neuen Parabelbogen mit dem gegebenen Brennpunkt hinzu public void AddNewArc(PointF point, double x) { if (root == null) { root = new ParabolaArc(point, null, null); return; } // Bestimmt den aktuellen Parabelbogen mit der y-Koordinate des Punkts point ParabolaArc arc; for (arc = root; arc != null; arc = arc.nextArc) // Diese for-Schleife durchläuft die Parabelbögen { PointF intersection1 = new PointF(0, 0), intersection2 = new PointF(0, 0); if (GetIntersection(point, arc, ref intersection1)) // Wenn die neue Parabel den Parabelbogen schneidet { // Dupliziert gegebenenfalls den Parabelbogen if (arc.nextArc != null && !GetIntersection(point, arc.nextArc, ref intersection2)) { arc.nextArc.previousArc = new ParabolaArc(arc.point, arc, arc.nextArc); arc.nextArc = arc.nextArc.previousArc; } else { arc.nextArc = new ParabolaArc(arc.point, arc, null); } arc.nextArc.edge2 = arc.edge2; // Fügt einen neuen Parabelbogen zwischen den Parabelbögen arc und arc.nextArc ein. arc.nextArc.previousArc = new ParabolaArc(point, arc, arc.nextArc); arc.nextArc = arc.nextArc.previousArc; arc = arc.nextArc; // Verbindet 2 neue Kanten mit den Endpunkten des Parabelbogens arc.previousArc.edge2 = arc.edge1 = new VoronoiEdge(intersection1); arc.nextArc.edge1 = arc.edge2 = new VoronoiEdge(intersection1); // Prüft die benachbarten CircleEvents des Parabelbogens CheckCircleEvent(arc, point.X); CheckCircleEvent(arc.previousArc, point.X); CheckCircleEvent(arc.nextArc, point.X); return; } } // Spezialfall: Wenn der Parabelbogen keinen anderen schneidet, wird er der doppelt verketteten Liste hinzugefügt for (arc = root; arc.nextArc != null; arc = arc.nextArc); // Bestimmt den letzten Parabelbogen arc.nextArc = new ParabolaArc(point, arc, null); // Fügt eine Kante zwischen den Parabelbögen ein PointF start = new PointF(0, 0); start.X = (float)x; start.Y = (arc.nextArc.point.Y + arc.point.Y) / 2; arc.edge2 = arc.nextArc.edge1 = new VoronoiEdge(start); } // Diese Methode erzeugt wenn nötig ein neues CircleEvent für den gegebenen Parabelbogen public void CheckCircleEvent(ParabolaArc arc, double _x) { // Setzt das bisherige CircleEvent auf nicht aktuell if (arc.circleEvent != null && arc.circleEvent.x != _x) { arc.circleEvent.isValid = false; } arc.circleEvent = null; if (arc.previousArc == null || arc.nextArc == null) { return; } double x = 0; PointF point = new PointF(0, 0); if (GetRightmostCirclePoint(arc.previousArc.point, arc.point, arc.nextArc.point, ref x, ref point) && x > _x) { arc.circleEvent = new CircleEvent(x, point, arc); // Erzeugt ein neues CircleEvent circleEvents.Add(arc.circleEvent); circleEvents.Sort(new EventComparer()); // Sortiert die Liste } } // Diese Methode bestimmt die x-Koordinate des Kreises durch die 3 Punkte, der ganz rechts liegt und prüft, ob die 3 Punkte auf einer Geraden liegen public bool GetRightmostCirclePoint(PointF point1, PointF point2, PointF point3, ref double x, ref PointF point) { // Prüft, dass die 3 Punkt im Uhrzeigersinn orientiert sind if ((point2.X - point1.X) * (point3.Y - point1.Y) > (point3.X - point1.X) * (point2.Y - point1.Y)) { return false; } double x1 = point2.X - point1.X; double y1 = point2.Y - point1.Y; double a = 2 * (x1 * (point3.Y - point2.Y) - y1 * (point3.X - point2.X)); if (a == 0) { return false; // Wenn die 3 Punkte auf einer Geraden liegen, wird false zurückgegeben } double x2 = point3.X - point1.X; double y2 = point3.Y - point1.Y; double a1 = x1 * (point1.X + point2.X) + y1 * (point1.Y + point2.Y); double a2 = x2 * (point1.X + point3.X) + y2 * (point1.Y + point3.Y); // Berechnet den Mittelpunkt des Kreises durch die 3 Punkte point.X = (float)((y2 * a1 - y1 * a2) / a); point.Y = (float)((x1 * a2 - x2 * a1) / a); x = point.X + Math.Sqrt(Math.Pow(point1.X - point.X, 2) + Math.Pow(point1.Y - point.Y, 2)); // x-Koordinate des Mittelpunkts plus Radius return true; } // Diese Methode bestimmt gegebenenfalls den Schnittpunkt zwischen der Parabel mit dem gegebenen Brennpunkt und dem Parabelbogen und prüft, ob er existiert public bool GetIntersection(PointF point, ParabolaArc arc, ref PointF intersection) { if (arc.point.X == point.X) { return false; // Wenn die Brennpunkte übereinstimmen, wird false zurückgegeben } double y1 = 0, y2 = 0; if (arc.previousArc != null) { y1 = GetParabolasIntersection(arc.previousArc.point, arc.point, point.X).Y; // Berechnet die y-Koordinate des Schnittpunkts zwischen dem aktuellen und dem vorherigen Parabelbogen } if (arc.nextArc != null) { y2 = GetParabolasIntersection(arc.point, arc.nextArc.point, point.X).Y; // Berechnet die y-Koordinate des Schnittpunkts zwischen dem aktuellen und dem nächsten Parabelbogen } // Berechnet die Koordinaten des Schnittpunkts, falls vorhanden if ((arc.previousArc == null || y1 <= point.Y) && (arc.nextArc == null || point.Y <= y2)) { intersection.Y = point.Y; intersection.X = (arc.point.X * arc.point.X + (arc.point.Y - intersection.Y) * (arc.point.Y - intersection.Y) - point.X * point.X) / (2 * arc.point.X - 2 * point.X); return true; } return false; } // Diese Methode bestimmt den Schnittpunkt zwischen den Parabeln mit den gegebenen Brennpunkten für die Sweep Line mit der gegebenen x-Koordinate public PointF GetParabolasIntersection(PointF point1, PointF point2, double x) { PointF intersection = new PointF(0, 0), point = point1; // Spezialfälle if (point1.X == point2.X) { intersection.Y = (point1.Y + point2.Y) / 2; } else if (point2.X == x) { intersection.Y = point2.Y; } else if (point1.X == x) { intersection.Y = point1.Y; point = point2; } else // Standardfall { // Verwendet die Lösungsformel für quadratische Gleichungen, um die y-Koordinate des Schnittpunkts zu berechnen double x1 = 2 * (point1.X - x); double x2 = 2 * (point2.X - x); double a = 1 / x1 - 1 / x2; double b = -2 * (point1.Y / x1 - point2.Y / x2); double c = (point1.Y * point1.Y + point1.X * point1.X - x * x) / x1 - (point2.Y * point2.Y + point2.X * point2.X - x * x) / x2; intersection.Y = (float)((-b - Math.Sqrt(b * b - 4 * a * c)) / (2 * a)); } // Setzt die y-Koordinate in die Parabelgleichung ein, um die x-Koordinate zu berechnen intersection.X = (float)((point.X * point.X + (point.Y - intersection.Y) * (point.Y - intersection.Y) - x * x) / (2 * point.X - 2 * x)); return intersection; } // Diese Methode stellt die benachbarten Kanten der Parabelbögen fertig public void FinishEdges(double x1, double y1, double x2, double y2) { // Verschiebt die Sweep Line, sodass keine Parabel die Zeichenfläche schneiden kann double x = x2 + (x2 - x1) + (y2 - y1); // Verlängert jede benachbarte Kante bis zum Schnittpunkt der neuen Parabeln for (ParabolaArc arc = root; arc.nextArc != null; arc = arc.nextArc) { if (arc.edge2 != null) { arc.edge2.Finish(GetParabolasIntersection(arc.point, arc.nextArc.point, 2 * x)); } } } } // Klasse für das Hauptfenster public partial class MainForm : Form { private Graphics graphics; private List<PointF> points = new List<PointF>(); // Liste der Punkte private double x1, y1, x2, y2; public MainForm() { x1 = 0; y1 = 0; x2 = 800; y2 = 800; // Setzt die Koordinaten der Eckpunkte der quadratischen Zeichenfläche Random random = new Random(); // Initialisiert den Zufallsgenerator int numberOfPoints = 10; for (int i = 0; i < numberOfPoints; i++) // Diese for-Schleife erzeugt 10 zufällige Punkte innerhalb der quadratischen Zeichenfläche { PointF point = new PointF(); point.X = (float)(random.NextDouble() * (x2 - x1) + x1); point.Y = (float)(random.NextDouble() * (y2 - y1) + y1); points.Add(point); // Fügt den Punkt der Liste hinzu } points.Sort(new PointComparer()); // Sortiert die Punkte Fortune fortune = new Fortune(); // Erzeugt ein Objekt der Klasse Fortune fortune.points.AddRange(points); // Fügt die Punkte der Liste hinzu // Diese for-Schleife verarbeitet bei jedem Durchlauf das Element mit der kleinsten x-Koordinate while (fortune.points.Count != 0) // Solange die Liste der Punkte nicht leer ist { if (fortune.circleEvents.Count != 0 && fortune.circleEvents[0].x <= fortune.points[0].X) { fortune.ProcessCircleEvent(); // Aufruf der Methode, verarbeitet das CircleEvent } else { fortune.ProcessPoint(x1); // Aufruf der Methode, verarbeitet den Punkt } } // Nachdem alle Punkte verarbeitet wurden, werden die verbleibenden circleEvents verarbeitet. while (fortune.circleEvents.Count != 0) // Solange die Liste der CircleEvents nicht leer ist { fortune.ProcessCircleEvent(); } fortune.FinishEdges(x1, y1, x2, y2); // Aufruf der Methode, stellt die benachbarten Kanten der Parabelbögen fertig InitializeComponent(); Text = "Voronoi-Diagramm"; Width = 800; Height = 800; graphics = CreateGraphics(); // Erzeugt ein Grafikobjekt für das Zeichnen auf dem Hauptfenster. Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters. } // Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird. private void OnPaint(object sender, PaintEventArgs e) { for (int i = 0; i < points.Count; i++) { graphics.FillRectangle(new SolidBrush(Color.FromArgb(0, 0, 0)), points[i].X - 1, points[i].Y - 1, 2, 2); // Zeichnet die Voronoi-Zentrums } for (int i = 0; i < VoronoiEdge.edges.Count; i++) { graphics.DrawLine(new Pen(Color.FromArgb(0, 0, 255)), VoronoiEdge.edges[i].point1, VoronoiEdge.edges[i].point2); // Zeichnet die Voronoi-Kanten } } }

Programmierung

Das folgende Programm in der Programmiersprache C++ erzeugt ein zufälliges Voronoi-Diagramm, indem alle Pixel einzeln gesetzt werden, zeigt es auf dem Konsolenfenster an und speichert es in einer Bilddatei.^[9]

#include <windows.h>
#include <vector>
using namespace std;

class Voronoi
{
private:
    vector<Point> points_;
    vector<DWORD> colors_;
    MyBitmap* bitmap_;

public:
    // Diese Funktion erzeugt ein Bitmap der Klasse MyBitmap, das ein Voronoi-Diagramm enthält
    void Create(MyBitmap* bitmap, int count)
    {
        bitmap_ = bitmap;
        for (int i = 0; i < count; i++) // Diese for-Schleife erzeugt zufällige Punkte (Zentren)
        {
            points_.push_back({ rand() % (bitmap_->width() - 20) + 10, rand() % (bitmap_->height() - 20) + 10 });
        }
        for (size_t i = 0; i < points_.size(); i++) // Diese for-Schleife erzeugt zufällige Farben für die Voronoi-Regionen
        {
            colors_.push_back(RGB(rand() % 200 + 50, rand() % 200 + 55, rand() % 200 + 50));
        }
        int width = bitmap_->width();
        int height = bitmap_->height();
        // Die folgenden zwei verschachtelten for-Schleifen durchlaufen alle Pixel des Bitmaps
        for (int i = 0; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                int index = -1;
                int minimumDistance = INT_MAX;
                // Die folgende for-Schleife durchläuft alle Zentren des Voronoi-Diagramms und bestimmt das Zentrum, das den kleinsten Abstand zum aktuellen Pixel mit den Koordinaten (i, j) hat
                for (size_t k = 0; k < points_.size(); k++)
                {
                    const Point& point = points_[k];
                    int x = i - point.x;
                    int y = j - point.y;
                    int distance = x * x + y * y;
                    if (distance < minimumDistance) // Wenn der aktuelle Abstand kleiner als der bisher kleinste Abstand ist
                    {
                        minimumDistance = distance; // Aktualisiert den kleinsten Abstand
                        index = k; // Aktualisiert den Index für das Zentrum
                    }
                }
                SetPixel(bitmap_->hdc(), i, j, colors_[index]); // Setzt das aktuelle Pixel auf die Farbe mit dem Index
            }
        }
        // Die folgende for-Schleife durchläuft alle Zentren des Voronoi-Diagramms und zeichnet sie in das Bitmap
        for (Point point : points_)
        {
            for (int i = -1; i <= 1; i++)
            {
                for (int j = -1; j <= 1; j++)
                {
                    SetPixel(bitmap_->hdc(), point.x + i, point.y + j, 0);
                }
            }
        }
    }
};

// Hauptfunktion die das Programm ausführt
int main()
{
    ShowWindow(GetConsoleWindow(), SW_MAXIMIZE);
    MyBitmap bitmap;
    bitmap.Create(512, 512); // Erzeugt ein Bitmap mit der angegebenen Breite und Höhe
    Voronoi voronoi;
    voronoi.Create(&bitmap, 50); // Aufruf der Funktion, erzeugt das Voronoi-Diagramm
    BitBlt(GetDC(GetConsoleWindow()), 20, 20, 512, 512, bitmap.hdc(), 0, 0, SRCCOPY); // Zeigt das Bitmap auf dem Konsolenfenster an
    bitmap.SaveBitmap("VoronoiDiagram.png"); // Speichert das erzeugte Bitmap als Bilddatei mit dem angegebenen Dateinamen
}

Das Programm verwendet die Klasse MyBitmap, die wie folgt deklariert ist:

Code-Schnipsel

#include <windows.h> #include <vector> using namespace std; struct Point { int x, y; }; class MyBitmap { private: HBITMAP bitmap_; HDC dc_; HPEN pen_; int width_, height_; public: HDC hdc() { return dc_; } int width() { return width_; } int height() { return height_; } bool Create(int weight, int height) { BITMAPINFO bitmapInfo; ZeroMemory(&bitmapInfo, sizeof(bitmapInfo)); bitmapInfo.bmiHeader.biSize = sizeof(bitmapInfo.bmiHeader); bitmapInfo.bmiHeader.biBitCount = sizeof(DWORD) * 8; bitmapInfo.bmiHeader.biCompression = BI_RGB; bitmapInfo.bmiHeader.biPlanes = 1; bitmapInfo.bmiHeader.biWidth = weight; bitmapInfo.bmiHeader.biHeight = -height; void* bits_ptr = nullptr; HDC dc = GetDC(GetConsoleWindow()); bitmap_ = CreateDIBSection(dc, &bitmapInfo, DIB_RGB_COLORS, &bits_ptr, nullptr, 0); if (!bitmap_) { return false; } dc_ = CreateCompatibleDC(dc); SelectObject(dc_, bitmap_); ReleaseDC(GetConsoleWindow(), dc); width_ = weight; height_ = height; return true; } void SetPenColor(DWORD color) { if (pen_) { DeleteObject(pen_); } pen_ = CreatePen(PS_SOLID, 1, color); SelectObject(dc_, pen_); } bool SaveBitmap(const char* path) { HANDLE file = CreateFile((LPCWSTR)path, GENERIC_WRITE, 0, nullptr, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, nullptr); if (file == INVALID_HANDLE_VALUE) { return false; } BITMAPFILEHEADER fileheader; BITMAPINFO infoheader; BITMAP bitmap; GetObject(bitmap_, sizeof(bitmap), &bitmap); DWORD* dwp_bits = new DWORD[bitmap.bmWidth * bitmap.bmHeight]; ZeroMemory(dwp_bits, bitmap.bmWidth * bitmap.bmHeight * sizeof(DWORD)); ZeroMemory(&infoheader, sizeof(BITMAPINFO)); ZeroMemory(&fileheader, sizeof(BITMAPFILEHEADER)); infoheader.bmiHeader.biBitCount = sizeof(DWORD) * 8; infoheader.bmiHeader.biCompression = BI_RGB; infoheader.bmiHeader.biPlanes = 1; infoheader.bmiHeader.biSize = sizeof(infoheader.bmiHeader); infoheader.bmiHeader.biHeight = bitmap.bmHeight; infoheader.bmiHeader.biWidth = bitmap.bmWidth; infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof(DWORD); fileheader.bfType = 0x4D42; fileheader.bfOffBits = sizeof(infoheader.bmiHeader) + sizeof(BITMAPFILEHEADER); fileheader.bfSize = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage; GetDIBits(dc_, bitmap_, 0, height_, (LPVOID)dwp_bits, &infoheader, DIB_RGB_COLORS); DWORD wb; WriteFile(file, &fileheader, sizeof(BITMAPFILEHEADER), &wb, nullptr); WriteFile(file, &infoheader.bmiHeader, sizeof(infoheader.bmiHeader), &wb, nullptr); WriteFile(file, dwp_bits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, nullptr); CloseHandle(file); return true; } };

Anwendungen

Voronoi-Diagramme dienen zum Erstellen von Karten der Repräsentativität von Punkten in der Meteorologie, z. B. von Niederschlagsgebieten. Voronoi-Diagramme werden auch in der Erforschung sozioökonomischer Phänomene eingesetzt. Polygone in ihrer klassischen Form wurden verwendet, um den Transportzugang von Eisenbahnstationen und anderen Transporthaltestellen, Schulen, Krankenhäusern zu ermitteln. Die Polygon-Methode wurde verwendet, um räumliche Muster der Vertriebs- und Zugänglichkeit von Läden zu analysieren, um den Zugang zu Grünflächen in Großstädten und die Beziehung zwischen der Gemeinschaft und dem nächstgelegenen Dienstanbieter zu ermitteln.

In der Forschung wurden Voronoi-Polygone verwendet, um die Zone des Transittransports zu bestimmen, und zur Abgrenzung von Meereszonen. Das sogenannte Verfahren der gewichteten Voronoi-Diagramme ist eine Modifikation von Voronoi-Diagrammen. Es besteht in der Vergrößerung oder Verkleinerung der Voronoi-Zellen um einen Punkt in Abhängigkeit von dem Gewichtungsparameter, das einem solchen Punkt zugeordnet ist. Das Verfahren wird in dieser Form verwendet, um den Algorithmus zur Berechnung konvexer Entfernungen in Verkehrsnetzen zu erhalten.^[10]

Geisteswissenschaften

In der klassischen Archäologie bzw. Kunstgeschichte wird die Symmetrie von Statuenköpfen analysiert, um den Typus der verlorenen Statue zu bestimmen, so z. B. am 3D-Modell des Kopfes Sabouroff.^[11][12]

Fußball

In der Analyse von Fußballspielen und taktischem Verhalten der Spieler werden Voronoi-Diagramme verwendet, um die Raumkontrolle beider Mannschaften zu visualisieren: „Die einzelnen Linien trennen die Räume ab, welche die Verteidiger und welche die Angreifer zuerst erreichen können. So zeigt sich, welche Räume die angreifende Mannschaft kontrolliert und welche Räume die verteidigende Mannschaft kontrolliert.“^[13] Eine gute Raumkontrolle der verteidigenden Mannschaft zeichnet sich dadurch aus, dass sie der angreifenden Mannschaft keine Regionen in Nähe des eigenen Tores ermöglicht, in denen ein Angreifer vor einem Verteidiger in Ballbesitz kommen und somit eine Torchance kreieren könnte.^[14] Die reine Betrachtung der Abstände führt dabei jedoch nur zu einer ersten Näherung, da in der Praxis des Spiels auch Aspekte wie Reaktionsgeschwindigkeit, aktuelle Laufrichtung, Geschicklichkeit bei der Balleroberung etc. in Betracht gezogen werden müssten. Das Gleiche gilt für den Deckungsschatten eines Spielers, in den der Ball in der Regel nicht direkt gespielt werden kann.^[13]

Literatur

• Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu (Hrsg.): Spatial Tessallations: Concepts and Applications of Voronoi Diagrams. 2. Auflage. John Wiley & Sons, 2000, ISBN 978-0-471-98635-5.
• Franz Aurenhammer, Rolf Klein, Der-Tsai Lee: Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company, Singapore 2013, ISBN 9814447633.

Weblinks

Commons: Voronoi diagrams – Sammlung von Bildern, Videos und Audiodateien

• MathWorld (englisch)
• Implementierung zur Berechnung von Voronoi-Diagramme in Python
• Java-Applet für Voronoi-Diagramme
• Weiteres Java-Applet (Memento vom 3. Juli 2017 im Internet Archive)
• Zelluläre Raumstruktur, mit Hilfe von Voronoi generiert (englisch)
• Java-Applet, das die Konstruktion eines Voronoi-Diagramms im Sweep-Line-Verfahren demonstriert (Memento vom 8. Dezember 2012 im Webarchiv archive.today)
• Delaunay-Triangulierung und Voronoi-Diagramm in C++
• Animation für Delaunay-Triangulierung und Voronoi-Diagramm in C#
• Voronoi-Diagramm in LISP, AutoCAD

Einzelnachweise

1. Rolf Klein: Algorithmische Geometrie, Springer 2005, ISBN 978-3-540-20956-0
2. Thomas M. Liebling: Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twin. In: Documenta Mathematica. Extra Volume ISMP, 2012, S. 419–431 (math.uiuc.edu (Memento vom 9. August 2017 im Internet Archive)Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt. [PDF]).
3. G. S. Brown: Point density in stems per acre (= N.Z. For. Res. Notes. Band 38). 1965, S. 11.
4. R. Mead: A Relationship between Individual Plant-spacing and Yield. In: Annals of Botany. Band 30, Nr. 2, April 1966, S. 301–309, doi:10.1093/oxfordjournals.aob.a084076.
5. Paul Niggli: XXIV. Die topologische Strukturanalyse. I. In: Zeitschrift für Kristallographie. Band 65, Nr. 1-6, 1927, S. 391–415, doi:10.1524/zkri.1927.65.1.391.
6. John Fisher: Visualizing the connection among Convex Hull, Voronoi Diagram and Delaunay Triangulation (PDF; 4,8 MB)
7. Simon Fraser University: Fortune’s Algorithm
8. Matt Brubeck: Fortune's Algorithm in C++
9. Rosetta Code: Voronoi diagram
10. Wojciech Pokojski, Paulina Pokojska, University of Warsaw: Voronoi diagrams – inventor, method, applications
11. Tonio Hölscher, Susanne Krömker und Hubert Mara: Der Kopf Sabouroff in Berlin: Zwischen archäologischer Beobachtung und geometrischer Vermessung. In: Benaki-Museum (Hrsg.): Gedenkschrift für Georgios Despinis. Athen, Griechenland 2020.
12. Voronoi Cells & Geodesic Distances - Sabouroff head auf YouTube. Analyse mit dem GigaMesh Software Framework wie in Hölscher et al. beschrieben, cf. doi:10.11588/heidok.00027985.
13. Tobias Escher: Der Schlüssel zum Spiel: Wie moderner Fußball funktioniert. 2. Auflage. Rowohlt Verlag, Hamburg 2020, ISBN 978-3-499-00198-7, S. 29–31.
14. Als Beispiel findet sich unter https://medium.com/football-crunching/using-voronoi-diagrams-in-football-ca730ea81c05 eine Analyse des fünften Tores aus dem WM-Halbfinale Brasilien-Deutschland (1:7) von 2014 mit Hilfe von Voronoi-Diagrammen.

Normdaten (Sachbegriff): GND: 4226013-9 (lobid, OGND) | LCCN: sh88006450