taramath
ComputationalGeometry.voronoi
zur Berechnung des Voronoi-Diagramms
.convex_hull .delaunay .voronoi .random_points .is_distinct .make_distinct
Beschreibung
Die Funktion besitzt folgende Argumente:
A Matrix (Liste von Punkten in der Ebene)
Es wird das Voronoi-Diagramm von berechnet. Genauer wird zunächst die Delaunay-Triangulierung von berechnet und davon der duale Graph bestimmt, welcher dem Voronoi-Diagramm entspricht. Es wird vorausgesetzt, dass die Punkte paarweise verschieden sind.
Zurückgegeben wird das Voronoi-Diagramm als Graph, d.h. als Liste von Punkten sowie als Liste der Indize der zugehörigen Kanten. Zudem werden auch die Indize der Voronoi-Zelle (d.h. das Thiessen-Polygon) ausgegeben. Zur genauen Verwendung sei auf die folgenden Beispiele verwiesen.
Beispiel 1
Im folgenden Beispiel werden zunächst 48 Punkte zufällig im Quadrat verteilt. Anschließend wird das zugehörige Voronoi-Diagramm berechnet und dieses graphisch dargestellt.
Es sei bemerkt, dass nur die beschränkten Voronoi-Zellen dargestellt werden, da sich nur diese direkt aus dem dualen Graphen ergeben. Alle unbeschränkten Voronoi-Zellen lassen sich bestimmen, indem geeignete Mittelsenkrechte gebildet werden. Vorschau aktualisieren
Beispiel 2
Im folgenden Beispiel werden zunächst 48 Punkte zufällig im Quadrat verteilt. Anschließend wird das zugehörige Voronoi-Diagramm berechnet und es wird die Voronoi-Zelle (d.h. das Thiessen-Polygon) zum Index graphisch dargestellt. Vorschau aktualisieren