Best Performance-Critical-Algorithmus zur Lösung Nearest Neighbor

Question

Wir haben eine Liste von x, y-Paare. Jedes Paar stellt einen Punkt auf einem 2D-Raum. Ich mag den nächsten Punkt aus dieser Liste finden, die zu einem bestimmten Punkt xq, yq. Was ist der beste Leistung kritische Algorithmus für dieses Problem? Lisp Punkte wird sich nicht ändern; das heißt, ich brauche nicht Einfügen und Löschen durchzuführen. Ich möchte nur die nächsten Nachbarn eines Ziel xq, yq Punkt in dieser Reihe zu finden.

Edit 1: Danke an alle! Wie Stephan202 richtig erraten hat, möchte ich dies immer wieder tun; wie eine Funktion. Eine ist die Liste nicht unbedingt sortiert (In der Tat Ich verstehe nicht, wie es mit einem Primärschlüssel von 2 Spalten a und y? Wie eine Tabelle sortiert werden? Wenn das hilft, dann werde ich es sortieren).

I wird die Datenstruktur konstruieren auf der Liste einer Zeit basiert, und dann werde ich verwenden diese Datenstruktur in der Funktion erzeugt wird (falls dieser Vorgang selbst ist relevant).

Danke Jacob; Es scheint, dass KD-Baum-Datenstruktur für sein die Antwort ein guter Kandidat ist (Und ich fühle es ist. Ich werde aktualisieren, wenn ich einige relevante Ergebnisse zu erhalten).

Edit 2: Ich habe festgestellt, dass dieses Problem "nearest neighbour" genannt wird

!

Edit 3: Erster Titel war "Auf der Suche nach einem Algorithmus (für Spatial-Abfragen und Spatial-Indizierung) (Nächster Nachbar)"; Ich habe wählte einen neuen Titel: „Best Performance-Critical-Algorithmus zur Lösung Nearest Neighbor“. Da will ich nicht das Einfügen und Löschen Betrieb auf meinen ersten Daten auszuführen, und ich möchte nur die nächstgelegene von ihnen zu einem neuen Punkt (die nicht eingefügt werden sollen), entschied ich mich zu (derzeit) arbeitet an KD-Bäumen. Vielen Dank an alle!

Answer 1

Wie Stephan202 erwähnt, wenn Sie die engt Spiel für mehr als einen Punkt finden mögen, sollten Sie einen Baum verwendet werden.

würde ich einen KD-Baum empfehlen, deren Umsetzung leicht in mehreren Paketen gefunden werden kann, wie OpenCV 2.0 . Oder Sie könnten ein selbst implementieren!

EDIT: Ich hatte eine Frage zu kd-Baum-Implementierungen gefragt hier -. könnte nützlich sein,

EDIT: KD-Bäume wurden erfolgreich für NN sucht :) weit verbreitet - auch, wenn Sie bereit sind annähernd, zu akzeptieren, können Sie eine href verwenden <= "http: // people.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN“rel = "nofollow noreferrer"> Fast-Bibliothek für Ungefähre Nächste Neigbor (FLANN) . Die FLANN Implementierung ist in OpenCV 2.0 .

Wenn Sie nicht ungefähre Antworten sollten Sie die FLANN Parameter optimieren können, den gesamten Baum zu suchen.

Answer 2

Wenn die Abfrage Punkt (xq, yq) variiert und die Liste nicht, müssen Sie die Voronoidiagramm der Liste von Punkten. Dies gibt Ihnen eine Reihe von Polygonen oder „Zellen“ (von denen einige sind unendlich); jedes Polygon entspricht einen Punkt aus der ursprünglichen Liste, die „Seite“ der Zelle bezeichnet. Jeder Punkt, der vollständig innerhalb eines Polygons liegt näher an der Seite des Polygons als es an den anderen Standorten auf der ursprünglichen Liste. Jeder Punkt auf der Grenze zwischen zwei Polygonen liegt gleich weit entfernt von jedem Standort.

Sobald Sie bekommen so weit, müssen Sie eine einfache Möglichkeit, um herauszufinden, welches Polygon du bist in. Dies wird als die Punktposition Problem .

Eine wirklich, wirklich gutes Buch für diese Art der Sache ist Computational Geometry: Algorithmen und Anwendungen . Sie diskutieren sowohl die Voronoidiagramm Berechnung und die Trapezplatte Methode Punktposition im Detail.

Wenn Sie nicht wollen, den Code selbst zu tun, und Sie sollten nicht, dann versuchen Sie erhalten eine Bibliothek wie CGAL , die meiste Arbeit für Sie tun. Dies gilt wahrscheinlich auf die KD-Baum Antwort als gut, aber ich weiß nicht spezifisch.

Answer 3

Sie benötigen einen räumlichen Index .

Wenn Sie Ihre eigene Rolle, können Sie viel schlimmer als Kommissionierung die R-Baum oder Quad-tree Algorithmen.

Answer 4

Ich würde mit einem Quadtree gehen. Es ist die einfachste räumliche Struktur. In 2 Dimensionen würde empfehlen, ich in der Regel Quadtree statt kd-Baum, weil es einfacher, schneller ist. Sein Nachteil ist, mehr Speicherverbrauch, wenn die Anzahl der Dimensionen hoch ist, aber im Fall von zwei Dimensionen der Unterschied ist nicht signifikant.

Es gibt einen schönen Optimierung Trick, wenn die Koordinaten sind Gleitkomma getippt: In einer Abfrage müssen Sie zuerst die Blattknoten finden, der den Punkt enthält, auf die die meisten in der Nähe von Punkt gefragt. in jeder Iteration der Entscheidung, welche Kind-Knoten Schritt auf - Um dies zu tun, werden Sie in dem Baum von der Wurzel zu dem Blatt gehen. Speichern der Identifikatoren / Adressen der Kind-Knoten in einem 4-sized Array in der Knotenstruktur. Digitalisieren der Punkt in dem Abfrage-Algorithmus koordiniert. Dann werden Sie in der Lage sein, den richtigen Unterknoten finden nur durch die Indizierung die Array von 2 richtigen Bits des digitalisierten Punktkoordinaten. Digitalisieren ist schnell: es mit einem einfachen static_cast implementieren.

Aber zuerst die Quadtree ohne Optimierung implementieren, da es einfach ist, einen Fehler mit den Bit-Operationen zu machen. Auch ohne diese Optimierung, es wird immer noch die schnellste Lösung.

Answer 5

Iteration durch jeden anderen Punkt mit der Abstandsformel den Mindestabstand von Q zu finden (xq, yq).

Sie haben jedoch nicht genügend Informationen für eine leistungskritische Antwort gegeben.

Zum Beispiel, wenn Q ein sehr häufiger Punkt ist, könnte man den Abstand zu Q berechnet werden soll und speichern Sie es mit jedem Punkt.

Zweites Beispiel, wenn Sie eine große Anzahl von Punkten haben, können Sie die Punkte in Abschnitte organisieren und mit Punkten nur im selben Abschnitt und benachbarten Abschnitten auf den Abschnitt enthält, Q beginnen.