Berechnung des Voronoi-Diagramms einer Region innerhalb einer Box

8

Ich habe folgendes Problem: Ich habe eine Box voller Punkte mit einer bestimmten unbekannten Verteilung und möchte das Voronoï-Diagramm berechnen. Das Problem ist, dass die Anzahl der Punkte so groß ist, dass dies für die vollständige Verteilung möglicherweise nicht möglich ist.

Daher habe ich geplant, dies nur für eine Region innerhalb der Box zu tun, in der die Anzahl der Punkte nicht so groß war. Dazu muss ich wissen, wie der minimale Bereich berechnet wird, der sich auf das Voronoi-Diagramm eines bestimmten kleineren Bereichs in diesem Feld auswirken kann.

Mit anderen Worten, ich möchte das Voronoï-Diagramm der Punkte innerhalb des kleinen Würfels der folgenden Abbildung berechnen, das zum Voronoï-Diagramm passt, in dem die Punkte der vollständigen Box das kleinstmögliche Voronoï-Diagramm im Speicher speichern.

Erklärung des Problems.

ccorbella
quelle
3
Ich habe Leute gesehen, vor allem in der Astrophysik, die die Vorono-Tessalisierung großer Punktmengen berechnet haben. Siehe die Arbeit von Volker Springel. Zum Beispiel gibt es hier sogar einen Open-Source-Code, github.com/regonzar/paravt, der für Sie nützlich sein kann. Siehe auch arxiv.org/abs/1601.06429
cfdlab
Ich würde immer noch einen Weg brauchen, um dies mit der Strategie des kleinen Würfels zu tun, aber vielen Dank. Ich werde es mir ansehen.
Ccorbella
1
Entschuldigung, ich habe Probleme beim Versuch, diesen Satz zu verstehen. "Ich möchte das Voronoï-Diagramm der Punkte innerhalb des kleinen Würfels der folgenden Abbildung berechnen, das zum Voronoï-Diagramm passt, in dem die Punkte der vollständigen Box das kleinste Voronoï-Diagramm speichern im Speicher möglich. "
Nicoguaro
Entschuldigung, ich wollte nur das Voronoï-Diagramm des kleinen Würfels berechnen, wobei zu berücksichtigen ist, dass dies in dem Bereich derselbe sein sollte, den ich erhalten würde, wenn ich alle Punkte der Box berechnen würde. Dazu erwarte ich mehr Punkte als die in der Box befindlichen (ansonsten glaube ich nicht, dass es zu einem anderen Würfel passt, wenn ich dort dieselbe Strategie verfolge), aber ich möchte so wenig wie möglich speichern Punkte.
Ccorbella
@ccorbella Keine Antwort, aber mit welchem ​​Tool hast du diese schöne Figur bitte zur Verfügung gestellt? Fügen Sie möglicherweise das Tool in einer Beschriftung hinzu.
Jan Hackenberg

Antworten:

2

Um das Voronoi-Diagramm von riesigen (> 100 Millionen) Punktmengen zu berechnen, können Sie den folgenden Algorithmus verwenden:

1) create a kd-tree with all the points
2) for each point p [in parallel optionally]
     N = 10
     while not finished
       compute the N nearest neighbors of the point p
       compute the intersection of the N half-spaces defined by p 
       and the neighbors
       if there is a neighbor further away than 
         twice the radius of the ball centered on p and 
         bounding the intersection, finished = true
       N = N * 1.5
  // when exiting the loop, the computed intersection 
  // corresponds to the Voronoi cell of p, because no other bisector
  // can contribute to the Voronoi cell.

Der Algorithmus wird mit weiteren Details in meinem Artikel erklärt . Es kann trivial parallelisiert werden (fügen Sie einfach "#pragma omp parallel for" vor der Hauptschleife hinzu), da keine Datenabhängigkeit besteht. Es ist in meiner GEOGRAM C ++ - Programmierbibliothek implementiert (zusammen mit einem speichereffizienten Kd-Tree, der auf mehr als 100 Millionen Punkte skaliert). Beachten Sie, dass es in GEOGRAM auch eine parallele Standard-Delaunay / Voronoi-Implementierung gibt, die mit bis zu 100 Millionen Standorten gut funktioniert.

In Bezug auf parallele Umsetzung des klassischen (Boywer-Watson) Algorithmus wird die Geogramm Implementierung dokumentiert hier (siehe auch die dazugehörige c ++ Quelldatei , die umfangreichen Kommentare hat). Ich habe keinen veröffentlichten Artikel darüber, ich werde einen schreiben, wenn es die Zeit erlaubt. Die Hauptidee besteht darin, Spinlocks zu verwenden, die den Tetraedern zugeordnet sind, um sicherzustellen, dass nur ein einzelner Faden ein Tetraeder modifizieren kann.

BrunoLevy
quelle
Zunächst einmal vielen Dank für Ihre Antwort. Es tut mir leid, Ihnen mitteilen zu müssen, dass Ihr Artikel anscheinend nicht mehr hochgeladen wird (zumindest die Vollversion aus dem von Ihnen verlinkten Web). Können Sie mir auf jeden Fall erklären, wie Sie diesen Voronoi-Diagrammalgorithmus parallel implementieren würden?
Ccorbella
Vielen Dank, dass Sie mich darüber informiert haben. Ich habe den Link repariert (der neue Link enthält das PDF. Klicken Sie auf das PDF-Symbol, um es abzurufen). Ich habe auch eine kurze Erklärung / einen Link zur parallelen Delaunay-Implementierung hinzugefügt.
BrunoLevy
Hinweis: Dies funktioniert gut, vorausgesetzt, die Punkte sind gleichmäßig verteilt (die Leistung kann sinken, wenn die Punktedichte stark variiert).
BrunoLevy
2

Scheint, als würden die Experten Ihre Frage nicht beantworten, also werde ich versuchen, eine Idee zu liefern. Aber bevor ich das tue, empfehle ich dringend, dass Sie in der Literatur nach einigen hoch entwickelten Methoden suchen, die bereits entwickelt wurden. Ohne jedoch zu garantieren, dass dies ein guter, schneller oder effizienter Vorschlag ist, schlage ich die folgende Methodik vor. Denken Sie daran, dass ich möglicherweise einige Fehler gemacht habe, daher kann ich nicht garantieren, dass alles vollständig korrekt ist, aber ich hoffe, dass die Idee der Methode Ihnen einen Ansatz bietet, der Ihnen bei der Lösung Ihres Problems hilft.

Sei die Menge deiner Punkte im ganzen "großen" Würfel. Fix Ihre „kleine“ Würfel C irgendwo in den großen Würfeln und lassen V C die Menge der Punkte, die in enthalten sind , C , dh V C = V C . Anfangs wird V ' C = V C gesetzt .V.C.V.C.C.V.C.=V.C..V.C.'=V.C.

Schritt 1: Erzeugen Sie das Voronoi-Diagramm . Für jeden Punkt bezeichnet v V C mit V o r ( v ) seine Voronoi-Zelle, die ein konvexes Polyeder im Dreiraum ist. Weiterhin bezeichnen mit W ( v ) die Eckpunkte der Voronoi-Zelle, die bei v V C zentriert sind , und mit W ( V C ) = v V V.Ör(V.C.')vV.C.'V.Ör(v)W.(v)vV.C.'die Eckpunkte aller Voronoi-Zellen aus dem Voronoi-DiagrammVor(VC).W.(V.C.')=vV.C.'W.(v)V.Ör(V.C.')

Schritt 2: Färben Sie alle Punkte von und alle Voronoi-Eckpunkte W ( V ' C ) weiß.V.C.'W.(V.C.')

Schritt 3: Zeichnen Sie für jeden Voronoi-Scheitelpunkt die bei w zentrierte Delaunay-Kugel, dh die Kugel mit dem Mittelpunkt w und dem Radius, dem Abstand zwischen w und einem der Punkte von V C, dessen Voronoi-Zelle w hat als Scheitelpunkt (egal welcher Punkt, es gibt mehrere, aber das Ergebnis ist immer das gleiche).wW.(V.C.')wwwV.C.'w

Fall 3.1. Wenn die Delaunay-Kugel von im Würfel C enthalten ist , färben Sie w schwarz.wC.w

Fall 3.2. Wenn die Delaunay-Kugel nicht im Würfel enthalten ist, aber keinen Punkt von V in ihrem (offenen) Inneren enthält, färben Sie den Punkt w schwarz.C.V.w

Fall 3.3. Wenn die Delaunay-Kugel von Punkte von V in ihrem (offenen) Inneren enthält, (1) addiere die Punkte von V, die im Inneren der Kugel enthalten sind, zur Menge V ' C und (2) halte die Farbe des Punktes w weiß . wV.V.V.C.'w

Schritt 4: Überprüfen Sie für jeden Punkt , ob alle Voronoi-Eckpunkte W ( v ) seiner Vornoi-Zelle schwarz sind. Wenn nicht alle schwarz sind, behalten Sie die Farbe v weiß bei. Wenn sie schwarz sind, färben Sie v schwarz.vV.C.'W.(v)vv

Schritt 5: Überprüfen Sie, ob alle Punkte des Originalsatzes schwarz sind.V.C.

Fall 5.1. Wenn sie alle schwarz sind, ist das auf den Würfel C beschränkte Voronoi-Diagramm der lokale Teil des auf C beschränkten globalen Voronoi-Diagramms V o r ( V ) . Ende.V.Ör(V.C.')C.V.Ör(V.)C.

Fall 5.2. Wenn es in weiße Eckpunkte gibt , kehren Sie zu Schritt 1 zurück. In Schritt 1 werden beim Erzeugen des neuen Voronoi-Diagramms V o r ( V ' C ) die Voronoi-Zellen um schwarze Punkte von V ' C gleich gehalten. Hält alle schwarzen Voronoi-Eckpunkte von W ( V C ) fern und ändert sich nur in Bezug auf die weißen. V.C.V.Ör(V.C.')V.C.'W.(V.C.')

Ich hoffe das hilft.

Zukunftsforscher
quelle
1

Der einfachste Weg, dies zu tun, besteht darin, Ihre Iner-Box mit einer größeren Box zu umgeben, die mindestens alle nächsten Nachbarn der Punkte in Ihrer inneren Box enthält. Beachten Sie, dass ein Problem auftritt, wenn sich das innere Feld nahe am Rand des umfassenden Datenfelds befindet: Sie haben keine externen Punkte.

Die Berechnung einer Voronoi / Delaunay-Tessellation kann subtiler sein, als Sie vielleicht denken. Eine der Fragen ist, wie genau entschieden werden kann, ob sich ein Punkt auf der einen oder anderen Seite einer Tessellationsebene / -linie befindet.

Unter http://www.cgal.org/ finden Sie hierfür die sehr vollständige "CGAL" C ++ - Bibliothek . Meine Kollegen und ich haben dies in mehreren veröffentlichten Artikeln zur Astrophysik verwendet: Es scheint absolut solide zu sein, um alle potenziellen Fallstricke bei der Erstellung dieser Tessellationen anzugehen.

JonesTheAstronomer
quelle
Ich danke Ihnen sehr für Ihre Antwort. Dann sollte meine Frage umgeschrieben werden, wenn Sie dies wünschen: "Wie finde ich die nächsten Nachbarpunkte derjenigen, die sich innerhalb des Würfels befinden und die geringste Anzahl von Berechnungen durchführen?". Mein Problem war im Grunde das. Kennen Sie einen Weg, dies zu tun?
Ccorbella
Wie entscheidet man, wie groß der Umkarton sein soll? Wenn es nicht groß genug ist, wird das vollständige Diagramm möglicherweise nicht auf die ursprüngliche kleine Box beschränkt. Ich denke, die richtige Entscheidung, ob ein Scheitelpunkt einer Voronoi-Zelle aus dem lokalen Diagramm ein Scheitelpunkt des globalen Diagramms ist, dh ein Scheitelpunkt, der durch eine zukünftige Neuberechnung des lokalen Voronoi-Diagramms nicht verändert wird, basiert darauf, ob das Innere der entsprechenden Delaunay-Kugel enthält Punkte aus der Gesamtmenge der Punkte oder nicht. Dies ist genau die Definition einer Delaynay-Zelle, die zu einer Voronoi-Zelle dual ist.
Futurologist
@ConradCorbellaBagot Für die Berechnung der nächsten Nachbarn in einem großen n-dim-Datensatz existiert ein sehr effizienter Algorithmus . Vielleicht möchten Sie angeben, woran Sie wirklich interessiert sind.
Bort
Die Voronoi / Delaunay-Tessellationen sind sowohl für eine unendliche Punktmenge als auch für eine Punktmenge, die begrenzt ist, gut definiert, jedoch nicht für eine Teilmenge von Punkten einer größeren Menge. Für solche Teilmengen müssen Sie eine willkürliche Kompromissentscheidung treffen. In der Kosmologie, in der wir eine endliche Box in einem ansonsten unendlichen Universum haben, wählen wir periodische Randbedingungen. Bei der Bildanalyse eines Teils eines Bildes "kleide" ich die Grenze mit den ersten Nachbarn der Punkte, die die Grenze definieren (es sind Komplikationen zu berücksichtigen). Ich finde, dass es relativ wenig Gewinn bringt, zum nächsten Nachbarn zu gehen.
JonesTheAstronomer
Einige davon finden Sie ausführlich in adsabs.harvard.edu/abs/2011MNRAS.416.2494P, das sowohl aus dem Journal als auch aus arXiv kostenlos heruntergeladen werden kann. Es wird auch die nichtlineare Kriging-Rekonstruktion eines Dichtefeldes unter Verwendung dieser Tessellationen diskutiert. Die Datenquelle hier ist astronomisch, aber die Diskussion ist ziemlich allgemein (für dreidimensionale Datensätze).
JonesTheAstronomer
1

Ich verstehe Ihre Frage wie folgt: Ich möchte ein Voronoi-Diagramm für eine Teilmenge von Punkten so zeichnen, dass es dem entspricht, das bei Betrachtung der vollständigen Menge von Punkten erhalten wird. Voronoi-Diagramme werden gezeichnet, indem zuerst benachbarte Punkte verbunden werden und dann eine Ebene senkrecht zur Linie am Mittelpunkt gezeichnet wird. Sie tun dies für alle nächsten Nachbarn und haben ein Voronoi-Diagramm in der Nähe eines Punktes. Tun Sie dies für alle Punkte und Sie haben ein Voronoi-Diagramm für alle Punkte. Sie sehen, Voronoi-Diagramme werden lokal definiert. Es gibt keinen Effekt für den zweitnächsten Nachbarn oder den drittnächsten Nachbarn. Nur erster nächster Nachbarschaftseffekt. Alles, was Sie tun müssen, um ein Voronoi-Diagramm mit einer Teilmenge von Punkten zu erhalten, ist, die Punkte in der interessierenden Teilregion zu identifizieren und sie mit allen ihren nächsten Nachbarn zu verbinden. und zeichnen Sie eine Ebene, die durch Mittelpunkte dieses Liniensegments und senkrecht zum Liniensegment verläuft. Dieses Diagramm ist für eine lokale Region gleich, unabhängig davon, ob Sie eine Unterregion oder eine vollständige Region betrachten.

Kaustubh Kaluskar
quelle
Zwei Fragen. Zuallererst sollte "Es gibt einen Effekt für den zweitnächsten Nachbarn oder den drittnächsten Nachbarn" "Es gibt nicht ..." sein, oder?
Ccorbella
Ja. Vielen Dank für den Hinweis. Ich werde die Antwort aktualisieren. Was ist die zweite Frage?
Kaustubh Kaluskar
Entschuldigung, ich habe den Kommentar xDD bearbeitet. Und der andere, ich weiß, dass Voronoi-Diagramme lokal definiert sind (unter anderen Bedingungen hätte meine Frage keine Antwort). Meine Frage sollte umgeschrieben werden, wenn Sie dies wünschen: "Wie finde ich die nächsten Nachbarpunkte derjenigen, die sich innerhalb des Würfels befinden und die geringste Anzahl von Berechnungen durchführen?". Kennen Sie einen Weg, dies zu tun? Trotzdem vielen Dank für Ihre Zeit.
Ccorbella
1
Ich benutze die Knnsearch-Funktion in MATLAB. Mein typischer Datensatz ist ungefähr 1,5 Millionen Punkte und ich mache es auf meinem Laptop. Auf der Mathworks-Website: 'IDX = knnsearch (X, Y) findet den nächsten Nachbarn in X für jeden Punkt in Y. IDX ist ein Spaltenvektor mit meinen Zeilen. Jede Zeile in IDX enthält den Index des nächsten Nachbarn in X für die entsprechende Zeile in Y. ' Hier wäre X Ihr vollständiger Datensatz und Y sind Punkte innerhalb des Würfels.
Kaustubh Kaluskar
Zunächst einmal nochmals vielen Dank. Ich werde es hart versuchen. Ich bin mir nicht sicher, ob ich einen Algorithmus als kd-Baum in einer so großen Anzahl von Punkten ausführen kann, wie es heißt: "Für große Dimensionen (20 ist bereits groß) erwarten Sie dies nicht Laufen Sie deutlich schneller als Brute Force.
Hochdimensionale
-2

Ich empfehle Ihnen einen visuellen und intuitiven Ansatz mit Grasshopper für Rhinoceros3D. Obwohl Rhinoceros ein kommerzielles CAD-Paket und Grasshopper ein Plugin dafür ist, können Sie Plugins ohne Einschränkungen kostenlos ausführen und Ihre Experimente durchführen (nicht lizenziertes Rhino3D beschränkt nur das Speichern von Rhino-Dateien). Grasshopper enthält eine große Anzahl mathematischer Funktionen, die in einer Leinwand verwendet werden, und 3D-Voronoi-Diagramme sind eine davon. Ein Voronoi-Würfel, der mit Grasshopper3D in Rhino3D erstellt wurde

Rabindranath Andujar
quelle
2
Der Link ist interessant, aber dies beantwortet die Frage nicht.
BrunoLevy
Das habe ich nicht verlangt, aber ich danke Ihnen für das Tool.
Ccorbella