Finden, in welchen Dreiecken sich Punkte befinden

16

Angenommen , ich habe eine 2D - Gitter , bestehend aus nicht - überlappende Dreiecken , und eine Menge von Punkten { P i } M i = 1N k = 1 T K . Wie lässt sich am besten bestimmen, in welchem ​​Dreieck jeder der Punkte liegt?{Tk}k=1N{pi}i=1Mk=1NTK

In der folgenden Abbildung haben wir zum Beispiel , p 2T 4 , p 3T 2 , daher hätte ich gerne eine Funktion f , die die Liste f ( p 1 , p 2 , p 3 ) = zurückgibt [ 2 , 4 , 2 ] .p1T2p2T4p3T2ff(p1,p2,p3)=[2,4,2]

Bildbeschreibung hier eingeben

Matlab hat die Funktion pointlocation, die das tut, was ich für Delaunay-Netze will, aber es schlägt für allgemeine Netze fehl.

Mein erster (dummer) Gedanke ist, für alle Knoten alle Dreiecke zu durchlaufen, um herauszufinden, in welchem ​​Dreieck p i sich befindet. Dies ist jedoch äußerst ineffizient - Sie müssen möglicherweise jedes Dreieck für jeden Punkt durchlaufen, also es könnte O ( N M ) Arbeit erfordern .pipiO(NM)

piO(aMlog(N))a

  • Es erfordert die Implementierung einer effizienten Suche nach dem nächsten Nachbarn (oder die Suche nach einer Bibliothek, in der diese vorhanden ist), was eine nicht triviale Aufgabe sein kann.
  • Dazu muss eine Liste mit den an jeden Knoten angehängten Dreiecken gespeichert werden, für die mein Code derzeit nicht eingerichtet ist. Derzeit gibt es nur eine Liste mit Knotenkoordinaten und eine Liste mit Elementen.

Insgesamt scheint es unelegant, und ich denke, es sollte einen besseren Weg geben. Dies muss ein Problem sein, das häufig auftritt. Daher habe ich mich gefragt, ob jemand den besten Weg empfehlen kann, um herauszufinden, in welchen Dreiecken sich die Knoten befinden, entweder theoretisch oder in Bezug auf die verfügbaren Bibliotheken.

Vielen Dank!

Nick Alger
quelle

Antworten:

16

Die übliche Randomized-Edge-Hopping-Methode sollte funktionieren. Beginnen Sie grundsätzlich mit einem beliebigen Dreieck des Netzes und bestimmen Sie dann, auf welcher der Kanten der Zielpunkt auf der gegenüberliegenden Seite von liegt. Das heißt, bestimmen Sie, welche der Kanten, wenn sie zu einer Linie verlängert werden, den Punkt vom Inneren des Dreiecks trennen. Wenn es zwei Möglichkeiten gibt, wählen Sie eine zufällig aus und betrachten Sie das Dreieck, das an diese gemeinsame Kante angrenzt, und wiederholen Sie diese. Die Randomisierung sollte diese Methode mit Wahrscheinlichkeit 1 für Delaunay-Triangulationen konvergieren lassen, und ich kann mir keinen Grund vorstellen, warum sie für beliebige Triangulationen nicht funktionieren würde.

O(logN)O(MlogN)M

Edit2 : Wir haben dieses PDF gefunden , das ein solches "Walking" -Schema beschreibt, das garantiert endet, und überprüfen die naiveren Ansätze.

Eine andere Alternative zur Verwendung von Quadtrees ist die Verwendung einer Triangulationshierarchie. Siehe Olivier Devillers. Verbesserte inkrementelle randomisierte Delaunay-Triangulation. In Proc. 14. Jahrestag ACM Sympos. Comput. Geom., Seiten 106-115, 1998. Es funktioniert am besten für Delaunay-Triangulationen, kann aber auch für Nicht-Delaunay-Triangulationen verwendet werden.

Grundsätzlich erfordert das, was Sie tun, um die Ortung von Punkten zu beschleunigen, den Aufbau einer Hilfsdatenstruktur. Bei Quadtrees oder einer anderen räumlichen Unterteilung müssen Sie den Unterteilungsbaum erstellen. Beim Edge-Hopping müssen Sie das Dreieck neben der topologischen Struktur aufbauen. Die Triangulationshierarchie erfordert auch die Erstellung eines Baums gröberer Triangulationen.

Victor Liu
quelle
Victor - kennen Sie Open-Source-Code, der den Edge-Hopping-Ansatz implementiert? Es sieht so aus, als wäre es eine sehr gute Lösung für meinen Fall. (Partikelverfolgungsmodell, angetrieben von aktuellen Feldern in einem normalen Gitter)
Chris Barker
Ich habe Code dafür und kann ihn Ihnen senden. Es ist in C / C ++. Ich hatte noch keine Zeit, es aufzuräumen und auf Github zu posten. Ich musste dies mindestens zweimal in meinem Leben schreiben, einmal mit einer Halbkantendatenstruktur, wieder mit einem Vierkant, aber es kann leicht verwendet werden, wenn diese nicht verfügbar sind und Sie selbst eine topologische Struktur erstellen müssen. Schauen Sie auf meiner Profilseite nach meiner Website, auf der Sie Kontaktinformationen finden. Wir können dies weiter offline diskutieren.
Victor Liu
Ich bin kurz davor, dies in Matlab mithilfe der Hilbert-Kurvenreihenfolge und des randomisierten Triangle Walks zu implementieren. Es ist Forschungscode: nicht optimiert, nicht dokumentiert usw., aber immer noch ziemlich schnell - ich kann Ihnen den Code geben, wenn Sie interessiert sind.
Nick Alger
2
About: "" Edge-Hopping sollte O (logN) sein. "" Das sehe ich nicht. Im pathologischen Fall eines großen langen Dreiecksstreifens (wie bei einem schmalen Kanal nur bei einem breiten Dreieck) müsste im schlimmsten Fall von einem Dreieck zum nächsten bis zum Ende gesprungen werden. Im Durchschnitt auf halbem Weg. Wenn Sie also die Anzahl der Dreiecke verdoppeln, wäre dies O (N). Im normaleren Fall einer quadratischen Anordnung von Dreiecken würde ich O (sqrt (N)) erwarten. Oder vermisse ich etwas? -Chris
Chris Barker
@Chris - Willkommen bei scicomp! Als Teil von scicomps Haushaltsführung habe ich Ihre Antworten und das folgende Gespräch als Kommentare zu Victors Antwort übernommen. Wir freuen uns auf Ihre Teilnahme an der Site.
Aron Ahmadia
8

Ich bin nicht überzeugt, dass Ihre Lösung tatsächlich richtig ist. Betrachten Sie die Situation, in der Sie diese Knoten haben:

  • A: (-3, 1)
  • B: (0, 2)
  • C: (3, 1)
  • D: (0, -5)

Es gibt Dreiecke ABC und ACD. Jetzt ist B der nächstgelegene Punkt zum Ursprung, aber der Ursprung liegt im Dreieck ACD, das kein B enthält.

O(NM)

Ich würde die Möglichkeit in Betracht ziehen, einen Quadtree zu bauen , der die Dreiecke selbst enthält. Das heißt, Sie haben einen quaternären Baum, der in jedem Knoten (der einem Begrenzungsrahmen entspricht) gespeichert ist:

  • Die Koordinaten, an denen die Box geteilt wird, oder alternativ die Begrenzungsrahmen der vier Teilbäume.
  • Zeiger auf die Teilbäume;
  • Die Menge der Dreiecke, die vollständig in den Begrenzungsrahmen dieses Rechtecks ​​fallen, jedoch nicht vollständig in einen der vier Teilbäume. Mit anderen Worten, die Dreiecke, die sich mit einem der beiden unterteilten Liniensegmente des Quadtrees schneiden.

nnlognO(NM)

Erik P.
quelle
Hmm du hast recht. Auf der anderen Seite, wenn die Triangulation Delaunay wäre, würde der nächste Nachbar funktionieren. Es ist zu restriktiv für das, was ich versuche, aber im Delaunay-Fall betrachten wir das duale Voronoi-Diagramm - die Voronoi-Zellen sind die Menge von Punkten, die einem Knoten am nächsten liegen, und die Kanten der Delaunay-Dreiecke treffen alle auf die Kanten der Voronoi Zellen im rechten Winkel, daher muss sich jeder Punkt in einem Dreieck befinden, das mit dem nächstgelegenen Knoten verbunden ist. Ich frage mich, ob Matlabs PointLocation-Funktion so funktioniert.
Nick Alger