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.mini|Beispiel einer Dirichlet-Zerlegung zu einer vorgegebenen Menge an Punkten
miniatur|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.Rolf Klein: Algorithmische Geometrie, Springer 2005, ISBN 978-3-540-20956-0 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 P. G. L. Dirichlet G. F. WoronoiA. K. Boldyrew A. H. Thiessen P. Niggli E. P. Wigner und F. 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 des Punktes , wobei eine vorgegebene Menge an Punkten des ist, gegeben durch
,
wobei als offene Halbebene definiert ist und durch
gegeben ist. Sind nun alle Voronoi-Regionen durch
gegeben, erhält man das Voronoi-Diagramm durch
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 , deren Voronoi-Region neben der Kante liegen, den gleichen Abstand.
mini|200px|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, 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 mini|Voronoi-Diagramm mit euklidischem Abstand mini|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:
oder als Manhattan-Abstand:
Die entsprechenden Voronoi-Diagramme sehen für verschiedene Metriken unterschiedlich aus.
Algorithmus mini|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 -Ebene in eine zusätzliche Dimension auf einen (Hyper-)Paraboloid mit den dreidimensionalen Koordinaten 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 , Delaunay-Triangulation , Konvexe Hülle , Voronoi-Diagramm .John Fisher: Visualizing the connection among Convex Hull, Voronoi Diagram and Delaunay Triangulation (PDF; 4,8 MB)
1: Initialisiere leere Mengen P', DT(P) und V(P) 2: 3: //Berechnung der konvexen Hülle 4: Für alle p = (px, py) 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 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 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 mini|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 und der Speicherbedarf in .Simon Fraser University: Fortune’s Algorithm
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.Matt Brubeck: Fortune's Algorithm in C++ 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) {