2017-09-02 1 views
1

Ich bin auf einem Algorithmus arbeiten, die immer wieder den (euklidischen) Abstand zum k-ten nächsten Punkt von einem gegebenen Abfragepunkt alle aus einem Vektor von Punkten genommen werden muss. Außerdem muss ich immer wieder alle Punkte innerhalb eines bestimmten Radius eines Punktes finden.Räumliche Abfragen für k-ten nächste Nachbarn eines Punktes

Ich denke an mit k-d Bäume aus der nanoflann Bibliothek. Die Funktion knnSearch() gibt jedoch alle k nächsten Nachbarn zurück, die ich nicht benötige. (Die Funktion radiusSearch() kommt mir jedoch sehr entgegen).

Gibt es eine effizientere Art und Weise zu bekommen, was ich brauche, andere als schuften durch alle k nächsten Nachbarn jedes Mal? Eine bessere Datenstruktur oder eine bessere Implementierung? (Ich bin mit C++.)

Antwort

1

Ich bin der Verwendung von k-d Bäume denken

Ausgezeichnete Wahl für 2D oder 3D.

kd-Bäume sind eine gute Wahl für geringe Dimensionsdaten (die ich nehme an, Sie haben seit nanoflann ist „vor allem für 2D- oder 3D-Punktwolken optimieren.“).

Gibt es einen effizienteren Weg, um das zu bekommen, was ich brauche, außer jedes Mal, wenn ich alle k nächsten Nachbarn durchsuche?

Sie müssen die k-ten Nearest Neighbor (NN), aber wenn ein kd-Baum für k NNs, den kostspieligen Vorgang der Suche (in Bezug auf der Zeit) ist die erste NN zu finden (die man benötigt, um Abstieg der Baum, von der Wurzel bis zu einem Blatt). Das Finden der zweiten, dritten oder einer anderen indizierten NN ist relativ billig, und ich bezweifle stark, dass dies die Leistung beeinträchtigen wird (d. H., Dass das Erhalten des k-ten NN aus den durch den Baum zurückgegebenen k NNs der Flaschenhals ist).

Also, ich schlage vor, Sie stark nicht über diesen Schritt zu kümmern.

Eine bessere Datenstruktur oder eine bessere Implementierung?

Ich glaube nicht. Ich habe nicht Nanoflann, aber CGAL für diese Art von Abfragen verwendet, und es lohnt sich, einen Versuch zu geben (aber CGAL erfordert Installation (kein Stück Kuchen), während Nanoflann nur ein Header-Include ist).

+1

Die Abmessungen sind bekannt für jeden gegebenen Datensatz 5 oder weniger sein. Ich bin froh zu wissen, dass ich nicht der Grund für den Flaschenhals im Code bin. Im Moment bleibe ich bei Nanoflann, gerade weil es ein Header-Include ist, und implementiert nur k-d-Bäume, was alles ist, was ich brauche. Vielen Dank. –

Verwandte Themen