Wie leite ich ein Voronoi-Diagramm anhand seiner Punktmenge und seiner Delaunay-Triangulation ab?

Question

Ich arbeite an einem Spiel, wo ich eine zufällige Karte von Provinzen (a la Risk oder Diplomatie) erstellen. Um diese Karte zu erstellen, erzeuge ich zuerst eine Reihe von halb-zufälligen Punkten, um dann die Delaunay-Triangulationen dieser Punkte zu berechnen.

Nachdem ich damit fertig bin, suche ich nun ein Voronoi-Diagramm der Punkte, die als Ausgangspunkt für die Provinzgrenzen dienen sollen. Meine Daten zu diesem Zeitpunkt (kein Wortspiel beabsichtigt) besteht aus der ursprünglichen Reihe von Punkten und einer Sammlung der Delaunay-Dreiecke.

Ich habe eine Reihe von Möglichkeiten gesehen, dies im Internet zu tun, aber die meisten von ihnen sind mit dem Delaunay verbunden. Ich würde gerne etwas finden, das nicht in den Delaunay integriert werden muss, sondern allein anhand der Daten arbeiten kann. Wenn ich das nicht schaffe, suche ich nach etwas, das für einen Neuling der relativen Geometrie verständlich ist, im Gegensatz zur optimalen Geschwindigkeit. Vielen Dank!

Answer 1

Das Voronoi-Diagramm nur das duale Graph der Delaunay-Triangulation ist.

Also sind die Kanten des Voronoi-Diagramms entlang der Mittelsenkrechten der Kanten der Delaunay-Triangulation, also berechnen Sie diese Linien.

Berechnen Sie dann die Scheitelpunkte des Voronoi-Diagramms, indem Sie die Überschneidungen benachbarter Kanten ermitteln.

Schließlich sind die Kanten dann die Teilmengen der Linien, die Sie berechnet haben, die zwischen den entsprechenden Eckpunkten liegen.

Beachten Sie, dass der genaue Code von der internen Darstellung abhängt, die Sie für die beiden Diagramme verwenden.

Answer 2

Ich bin mir ziemlich sicher, dass ‚Dreieck‘ http://www.cs.cmu.edu/~quake/triangle.html die voronoi erzeugen kann

Answer 3

Nun, der Grund, warum die Dinge zusammenhängen, ist, weil die Delaunay-Triangulation und das Voronoi-Diagramm Dualstrukturen sind. Das heißt, es ist ein Kinderspiel, von Voronoi nach Delaunay und umgekehrt zu gehen.

Das bedeutet, wenn Sie ein Voronoi-Diagramm haben, müssen Sie nur die Punkte verbinden, die eine Kante teilen, und Sie haben die Delaunay-Triangulation (und umgekehrt).

Answer 4

Wenn optimale Geschwindigkeit keine Überlegung ist, wird der folgende Pseudo-Code erzeugen ein Voronoi den harten Weg Diagramm:

for yloop = 0 to height-1 
    for xloop = 0 to width-1 

    // Generate maximal value 
    closest_distance = width * height 

    for point = 0 to number_of_points-1 
     // calls function to calc distance 
     point_distance = distance(point, xloop, yloop) 

     if point_distance < closest_distance 
     closest_point = point 
     end if 
    next 

    // place result in array of point types 
    points[xloop, yloop] = point 

    next 
next 

Vorausgesetzt, dass Sie einen ‚Punkt‘ Klasse oder Struktur haben, wenn man sie zufällige Farben zuweisen, dann sehen Sie das vertraute Voronoi-Muster, wenn Sie die Ausgabe anzeigen.

Answer 5

Jedes Ihrer Delaunay-Dreiecke enthält einen einzelnen Punkt des Voronoi-Diagramms.

Sie können diesen Punkt berechnen, indem Sie für jedes Dreieck den Schnittpunkt der drei perpendicular bisectors finden.

Ihr Voronoi-Diagramm verbindet diese Punkte mit jeweils den nächsten drei Nachbarn. (jeder Nachbar teilt eine Seite des Delaunay-Dreiecks)

Wie planen Sie, sich den Randfällen zu nähern?

Answer 6

Nachdem ich versucht habe, diesen Thread als Quelle für Antworten auf meine eigene ähnliche Frage zu verwenden, fand ich, dass Fortunes Algorithmus - wahrscheinlich, weil er am populärsten ist - am einfachsten zu verstehen war.

The Wikipedia article on Fortune's algorithm enthält neue Links zum Quellcode in C, C# und Javascript. Alle von ihnen waren erstklassig und kamen mit schönen Beispielen.