Wie leite ich ein Voronoidiagramm seines Punkt gesetzt und seine Delaunay-Triangulation gegeben?

StackOverflow https://stackoverflow.com/questions/85275

Frage

Ich arbeite an einem Spiel, in dem ich eine zufällige Karte von Provinzen (a la Risiko oder Diplomatie) erstellen. Um diese Karte zu erstellen, ich bin zu erzeugen zunächst eine Reihe von semi-zufälligen Punkten, dann die Delaunay Triangulation dieser Punkte herauszufinden.

Wenn das getan ist, suche ich jetzt eine Voronoidiagramm der Punkte zu erstellen, die als Ausgangspunkt für die Provinz Grenzen zu dienen. Meine Daten an diesem Punkt (kein Wortspiel beabsichtigt) besteht aus der Original-Serie von Punkten und einer Sammlung der Delaunay Dreiecke.

Ich habe eine Reihe von Möglichkeiten gesehen diese im Web zu tun, aber die meisten von ihnen sind mit dem Verlauf des Delaunay abgeleitet wurde gebunden. Ich würde gerne etwas finden, das nicht auf die Delaunay integriert werden muss, kann aber allein die Daten anhand von der Arbeit. Gelingt das nicht, ich bin auf der Suche nach etwas verständlich zu einem relativen Geometrie Neuling, als um einen optimale Geschwindigkeit entgegengesetzt. Dank!

War es hilfreich?

Lösung

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

  • So sind die Ränder des Voronoidiagramm entlang der senkrechten Halbierenden der Kanten der Delaunay-Triangulation, so diese Zeilen berechnen.
  • Dann berechnet die Eckpunkte des Voronoidiagramm durch die Kreuzungen benachbarter Kanten zu finden.
  • Schließlich sind die Kanten dann die Teilmengen der Zeilen, die Sie berechnet, die zwischen den entsprechenden Eckpunkten liegen.

Beachten Sie, dass der genaue Code auf der internen Darstellung ab, die Sie für die beiden Diagramme verwenden.

Andere Tipps

Wenn die optimale Geschwindigkeit keine Überlegung ist, wird der folgende Pseudo-Code ein Voronoi-Diagramm auf die harte Art und Weise erzeugen: 

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

Angenommen, Sie eine ‚Punkt‘ Klasse oder Struktur haben, wenn man ihnen zufällige Farben zuweisen, dann werden Sie die vertrauten voronoi Muster sehen, wenn Sie die Ausgabe angezeigt werden soll.

Nach dem Versuch, dieses Thema als Quelle zu verwenden, um Antworten auf meine ähnliche Frage, ich fand, dass Fortune-Algorithmus - wahrscheinlich, weil es die beliebteste ist und daher die meisten dokumentiert -. War am einfachsten zu verstehen

Wikipedia-Artikel zum Fortune-Algorithmus Quellcode in C frisch Links hält, C # und Javascript. Alle von ihnen waren erstklassig und kam mit schönen Beispielen.

Ich bin mir ziemlich sicher, dass 'Dreieck' http: //www.cs .cmu.edu / ~ Beben / triangle.html können die voronoi erzeugen

Jeder Ihrer Delaunay Dreiecke enthält einen einzigen Punkt des Voronoidiagramm.

Sie können diesen Punkt berechnen, indem der Schnittpunkt der drei Mittellote für jedes Dreieck .

Ihr Voronoidiagramm wird diese Menge von Punkten verbinden, die jeweils mit seinem nächsten drei Nachbarn. (Jeder Nachbar teilt sich eine Seite des Delaunay Dreieck)

Wie planen Sie die Grenzfälle bei der Annäherung an?

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top