Verwirrt mit Voronoi-Diagramm-Algorithmus (Fortune's Sweepline)

Question

Ich implementiere Voronoi-Diagramm, um den nächsten Ort in einer Karte visuell zu finden. Im Moment möchte ich dies nur mit Integer-Koordinaten (x, y) in einer Leinwand tun.

Problem ist- Ich bin wirklich verwirrt über diesen Algorithmus. Ich lese das Buch Computational Geometry, ein paar mehr Theorie über Fortunes Algorithmus. Und ich bin jetzt wirklich verwirrt. Es erscheint mir sehr komplex, wenn ich codiere.

Bitte beraten Sie mich sehr einfache Implementierung von Voronoi-Diagramm (mit gegebenen Koordinaten). Bitte beraten Sie mich einfach Java oder Python oder Schema-Code vorzugsweise ohne Hash, Multithreading, Delaunay Trainguulation, Phantasie Farben usw.

Ist es nicht möglich, Voronoi-Diagramm mit Fortune-Algorithmus ohne Multithreading oder Hash-Map zu implementieren?

Answer 1

Das Voronoi-Diagramm ist nur ein Diagramm: keine Datenstruktur oder Algorithmus. Ich denke nicht, dass es geeignet ist, den nächsten Punkt in einem Set zu finden. Das Konstruieren des Diagramms würde die asymptotische Komplexität Ihres Problems nicht ändern, obwohl es Ihr Problem komplizierter und weniger speichereffizient machen würde. Es wäre besser, wenn du deine Punkte in einen Quadtree oder Ähnliches steckst. Wenn Sie nach Algorithmen suchen, lautet der Name des Problems, das Sie lösen möchten, "räumliche Indexierung". "Nächster Punkt" ist eines der Probleme, die durch Quadtrees und andere räumliche Indizes gelöst werden.

Answer 2

Es scheint kompliziert, weil es kompliziert ist! Sie benötigen keine Hashtable oder Threads, aber Sie benötigen eine Prioritätswarteschlange (normalerweise als Heap implementiert und in den Java-Standardbibliotheken verfügbar) und eine Baumstruktur, mit der Sie Bereichsabfragen in O ausführen können (log n) (Die in den Standard-Bibliotheken sind nicht wirklich geeignet, weil Sie nicht an ihren Interna kommen können; ich würde empfehlen, eine AA tree zu implementieren). Und der Algorithmus selbst ist immer noch ziemlich haarig.

Können Sie ein externes Programm ausführen? Wenn ja, empfehle ich Ihnen wirklich, das schwere Heben auf QHull zu legen, was bei Voronoi-Diagrammen sehr gut ist. Viel besser als wir beide jemals traurig sein werden.

Answer 3

Ich habe im letzten Jahr ziemlich viele Voronoi-Diagramme gesehen, und ich kann die Verwirrung sicher schätzen. Es gibt einige Implementierungen von Voronoi-Diagramm-Generierungsalgorithmen herum. Siehe this page für ein Paar, und auch here. Wie bereits erwähnt, ist Qhull sicherlich einen Blick wert - MATLAB verwendet es, um Voronoi-Diagramme und Delaunay-Triangulations zu erzeugen.

Answer 4

Hier ist eine weitere Implementierung in Ruby und C, einschließlich Visualisierung:

http://github.com/abscondment/rubyvor/

Answer 5

Offensichtlich Algorithmus der Fortune ist nicht trivial zu implementieren. Vor allem, wenn Sie consider numerical robustness issues Zeitleiste. Sie sagen nicht, welche Programmiersprache Sie verwenden möchten, um es zu implementieren. Falls es C++ ist, können Sie die Arbeit von Andriy Sydorchuk für Boost in frame of GSoC 2010 Projekt finden: Sweepline Algorithm. Andriys Implementierung basiert auf Boost.Polygon Bibliothek. Sowohl die Voronoi-Implementierung als auch das Boost.Polygon basieren auf ganzzahligen Koordinaten, um eine numerische Robustheit zu gewährleisten.

Der BoostCon Videovortrag auf Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane gibt eine sehr gute Erklärung der Idee, Probleme und Fallstricke.

Ziemlich viele Diskussionen zu diesem Voronoi-Projekt. passierte in Boost Mailing Liste in 2010/2011.

Answer 6

I opened a github repository mit einem Hafen von Original-Papier Fortune. Die Implementierung von Fortune war sehr schwierig, hauptsächlich aufgrund der Art und Weise, wie er mit Datenstrukturen umging.

This book erscheint viel modernere

Fortune's original paper erfordert ein paar liest.

Ken Wong's Papier beschreibt den Algorithmus mit wohl mehr Klarheit als Vermögen in dem ursprünglichen Papier

Ken Wong's presentation große Schieber (10, 11) hat, wie man eine Seite und einen Scheitel verarbeiten

gibt eine interactive JavaScript demo ist (Archived version) können Sie sehen, wie Sie den Algorithmus visualisieren können.

A pdf beschreibt auch den Algorithmus.

Steven Fortune's original implementation is on his homepage.

This Stony Brook site Listen mehr Implementierungen

Triangle ist "A Zweidimensionalität Mesh-Generator und Delaunay Triangulator."

Es gibt eine entire book auf Voronoi Diagramme