Hallo
Ich entwickle gerade eine Anwendung in der ich recht viele (5000) Punkte im R3 habe und für einen beliebigen neuen Punkt den Nachbar suche. Die Suche nach dem Nachbar ist sehr zeitkritisch, die Punktwolke ist konstant, d.h. die Zeit zum Einfügen oder Entfernen von Punkten, optimieren usw, ist egal.
Trivial in O(n) wäre ein bischen blöd, deswegen habe ich mich ein bischen umgeschaut und bin auf octrees und kdtrees gestoßen.
Da die ganze Anwendung in C++ geschrieben wird habe ich noch ein bischen gesucht und bin auf den
libkdtree++ gestoßen, der sich eigentlich recht gut anhört. Bei den Octrees habe ich keine Implementation gefunden, die auch ein find_nearest() unterstützt. Eine eigene Implementation will ich nicht machen, da das Hauptproblem der Anwendung eigentlich wo anders liegt und ich zu wenig Zeit habe, alles selber zu schreiben.
Eine Alternative wäre ein 3d-Grid über die Wolke zu legen. Wenn meine Wolke 1m^3 groß ist, könnte ich zum Beispiel 1000 1dm^3 große Kistchen bauen und in jeder Kiste notieren, welche Punkte darin liegen. Wenn ich dann zu einem Punkt seinen Nachbarn suche, schau ich nach, in welche Kiste der Punkt liegt und überprüfe alle anderen Punkte darin. Wenn der Punkt dann einen geringeren Abstand zu einer der Wände als zum bis dahin nächsten Nachbarn hat, muss ich auch die Punkte in der anderen Kiste betrachten.
Bei den Bäumen läuft die Suche nach dem Nachbar in O(log N) (N =#Punkt in der Wolke), in der Grid-Version in O(?*n) mit (n= durchschnittliche # Punkte pro Kiste und ?=etwas das die WKeit beschreibt, noch mehr Kisten zu durchsuchen). Da ich Punkte, deren Nachbar mehr als grob 20cm entfernt ist, ignorieren kann, könnte ich sogar auf ein WorstCase verhalten von O(9*n) kommen. (Wobei die Frage ist, ob das besser als O(log N) ist.
Ich weiss leider nicht, was da schneller ist (an die Implementierung des Grids setze ich mich gleich) und hoffe, dass jemand von euch das Problem schon mal hatte und sich mit sinnvollen Gründen für eine Idee entschieden hat. (Wer auch noch eine gute C++ implementation kennt, ist natürlich auch gerne gesehen)
Nikolas