Voronoi-Diagramm
# 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.

## Allgemeines

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. 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. :

| Jahr | 1850 | 1908 | 1909 | 1911 | 1927 | 1933 | 1958 | 1965 | 1966 | 1985 |
| - | - | - | - | - | - | - | - | - | - | - |
| Entdecker | Dirichlet | Woronoi | Boldyrew | Alfred H. Thiessen | Paul Niggli | Eugene Paul Wigner und Frederick Seitz | F. C. Frank und J. S. Kasper | G. S. Brown | R. Mead | Louis Hoofd |
| Bereich | Mathematik | Mathematik | Geologie | Meteorologie | Kristallographie | Physik | Physik | Ökologie | Ökologie | Anatomie |
| Name | Dirichlet-Zerlegung | | | Thiessen-Polygone | Wirkungsbereiche | 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 $VR(p,S)$ des Punktes $p\in S$, wobei $S$ eine vorgegebene Menge an Punkten des $\mathbb {R} ^{2}$ ist, gegeben durch

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

wobei $D(p,q)$ als offene Halbebene definiert ist und durch

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

gegeben ist. Sind nun alle Voronoi-Regionen durch

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

gegeben, erhält man das Voronoi-Diagramm durch

    $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 $p\in S$, deren Voronoi-Region neben der Kante liegen, den gleichen Abstand.

## 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

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:

    $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:

    $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

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 $x,y$-Ebene in eine zusätzliche Dimension $z$ auf einen (Hyper-)Paraboloid mit den dreidimensionalen Koordinaten $(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 $P$, Delaunay-Triangulation $DT(P)$, Konvexe Hülle $KH(P)$, Voronoi-Diagramm $V(P)$.

### Algorithmus von Fortune

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 $O(n\cdot \log n)$ und der Speicherbedarf in $O(n)$.

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.

* 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.

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.

### Geisteswissenschaften

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

### 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.“ 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. 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.

