den nächsten Punkt finden

Question

Ich habe Vektor von Zeigern auf eine sehr einfache Point Klasse:

class Point{ 
public: 
    float x; 
    float y; 
    float z; 
}; 

Wie finde ich das nächste Objekt zu einem referenten Punkt mit STL?
Muss ich zuerst den Vektor sortieren oder gibt es einen effizienteren Weg?

Answer 1

Sortierung dauert O(n*log(N)), also ist es nicht sehr effizient. Sie können es in O(n) tun, indem Sie einfach durch die Elemente iterieren und die beste Übereinstimmung merken.

Mit for_each von <algorithm> können Sie eine Funktion definieren, die die nächsten Elemente verfolgt und in O(n) abschließt.

Oder Sie können wahrscheinlich sogar min_element verwenden, auch von <algorithm>.

Answer 2

Sie können nicht schneller als ein linearer Vergleich gehen, wenn Sie nur wissen, dass es Punkte in einem Vektor gibt. Wenn Sie jedoch zusätzliches Wissen haben, kann vieles verbessert werden. Wenn Sie zum Beispiel wissen, dass alle Punkte geordnet sind und auf derselben Linie liegen, gibt es eine logarithmische Lösung.

Auch gibt es bessere Datenstrukturen, um Ihr Problem zum Beispiel eine k-d tree zu lösen. Es ist nicht Teil der STL - Sie müssen es selbst implementieren, aber es ist die Datenstruktur, die Sie verwenden, um das Problem zu lösen, das Sie haben.

Answer 3

Die grundlegende Frage hier ist, wie oft Sie Abfragen gegen eine einzelne Menge von Punkten tun werden.

Wenn Sie einen Punkt in der Menge einmal finden, dann hat @Lucian Recht: Sie können die Punkte auch nicht sortiert lassen und eine lineare Suche durchführen, um den richtigen Punkt zu finden.

Wenn Sie eine relativ große Anzahl von Abfragen für die gleiche Menge von Punkten durchführen, ist es sinnvoll, die Punktdaten zu organisieren, um die Abfragegeschwindigkeit zu verbessern. @izomorphius hat bereits einen k-d Baum erwähnt, und das ist definitiv ein guter Vorschlag. Eine andere Möglichkeit (zugegebenermaßen sehr ähnlich) ist ein Oktobaum. Zwischen den beiden finde ich einen Oktbaum, der ein wenig leichter zu verstehen ist. In der Theorie sollte ein k-d-Baum (im Durchschnitt) etwas effizienter sein, aber ich habe nie viel Unterschied gesehen - obwohl vielleicht mit anderen Daten der Unterschied signifikant werden würde.

Beachten Sie jedoch, dass der Aufbau so etwas wie ein k-d-Baum oder oct-tree nicht schrecklich langsam ist, so brauchen Sie nicht eine Menge von Abfragen für eine Reihe von Punkten zu tun eins zu rechtfertigen den Bau. Eine Abfrage rechtfertigt dies offensichtlich nicht, und zwei wahrscheinlich auch nicht - aber im Gegensatz zu dem, was Luchian impliziert, ist O (N log N) (nur zum Beispiel) nicht wirklich sehr langsam. Grob gesagt, log (N) ist die Anzahl der Ziffern in der Zahl N, also ist O (N log N) nicht wirklich eine ganze Menge langsamer als O (N). Das bedeutet wiederum, dass Sie nicht eine besonders große Anzahl von Abfragen benötigen, um die Organisation der Daten zu rechtfertigen, um die einzelnen zu beschleunigen.

Answer 4

können Sie versuchen, Quadtree verwenden http://en.wikipedia.org/wiki/Quadtree

oder etwas ähnliches.