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.[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
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[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 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.
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:
oder als Manhattan-Abstand:
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 -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 .[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) 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
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 .[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
- Franz Aurenhammer, Rolf Klein, Der-Tsai Lee: Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company, Singapore 2013, ISBN 9814447633.
- 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.
Weblinks
- Animation für Delaunay-Triangulierung und Voronoi-Diagramm in C#
- Voronoi-Diagramm in LISP, AutoCAD
- Java-Applet für Voronoi-Diagramme
- MathWorld (englisch)
- Weiteres Java-Applet (Memento vom 3. Juli 2017 im Internet Archive)
- Delaunay-Triangulierung und Voronoi-Diagramm in C++
- Implementierung zur Berechnung von Voronoi-Diagramme in Python
- Java-Applet, das die Konstruktion eines Voronoi-Diagramms im Sweep-Line-Verfahren demonstriert (Memento vom 8. Dezember 2012 im Webarchiv archive.today)
- Zelluläre Raumstruktur, mit Hilfe von Voronoi generiert (englisch)
Einzelnachweise
- ↑ Rolf Klein: Algorithmische Geometrie, Springer 2005, ISBN 978-3-540-20956-0
- ↑ 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) [PDF]).
- ↑ G. S. Brown: Point density in stems per acre (= N.Z. For. Res. Notes. Band 38). 1965, S. 11.
- ↑ 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.
- ↑ 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.
- ↑ John Fisher: Visualizing the connection among Convex Hull, Voronoi Diagram and Delaunay Triangulation (PDF; 4,8 MB)
- ↑ Simon Fraser University: Fortune’s Algorithm
- ↑ Matt Brubeck: Fortune's Algorithm in C++
- ↑ Rosetta Code: Voronoi diagram
- ↑ Wojciech Pokojski, Paulina Pokojska, University of Warsaw: Voronoi diagrams – inventor, method, applications
- ↑ 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.
- ↑ 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.
- ↑ a b 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.
- ↑ 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.
Auf dieser Seite verwendete Medien
Autor/Urheber: Balu Ertl, Lizenz: CC BY-SA 1.0
Redrawn by hand based on this file: File:Manhattan Voronoi Diagram.png. This file contains layers and other helpful information for Inkscape editor.
Autor/Urheber: Jahobr, Lizenz: CC0
Voronoi-Diagramm erstellt durch Wachstum mit dem Euklidischer Abstand (bzw. p-Norm mit p=2) aus neun Zentren.
This is a slowed down version of file:Fortunes-algorithm.gif. It was too fast.
Voronoi-Diagramm
Berechnung eines Thiessen-Polygons
Autor/Urheber: Balu Ertl, Lizenz: CC BY-SA 4.0
Redrawn by hand based on this file: File:Euclidean Voronoi Diagram.png. The first revision (62 kb) of this file contains layers and other helpful information for Inkscape editor. The second (latest, 4 kb) revision is optimized for transmitting via network.
Autor/Urheber: Mysid (SVG), Cyp (original), Lizenz: CC BY-SA 3.0
Coloured 2D Voronoi diagram.