effiziente 2D k-nearest neighbor Library ?
-
Huhu!
Kennt jemand eine lib oder hat jemand source code zur Hand, der effizient die nächsten Nachbarn (eines Punktes) findet?
Würd gern sowohl den NN als auch die 2NN finden.
Und Brute Force über plumpen Distanzvergleich ist für mein Problem einfach ... zu schneckenlahm."schicke Algorithmen" gibt's ja ... aber die sind nicht mal eben schnell implementiert und getestet.
Wär' super, wenn jemand was wüsste.
-
http://www.twilightsembrace.com/personal/gamelibs.php#genpurp
Schau dir mal mal Quadtrees,BSP und ein paar andere Bäume an. Das könnte in etwa das sein, was du suchst.
(Weiss nicht, ob es da etwas auf dem Link zu finden ist. Kannst mal suchen.. ;))
-
Wie siehts mit libkdtree++ aus?
libkdtree++ is an STL-like C++ template container implementation of k-dimensional space sorting, using a kd-tree. It sports a theoretically unlimited number of dimensions, and can store any data structure. Provided the data structure, it provides operator[0 - k-1] to access the individual dimensional components (arrays, std::vector already do) and a std::less implementation for the type of dimensional components. It has support for custom allocators, implements iterators, and provides standard find as well as range queries. It has amortised O(lg n) time (O(n lg n) worst case) on most operations (insert/erase/find optimised) and worst-case O(n) space, and also provides a means to rebalance and thus optimise the tree.
-
lorenz__ schrieb:
Wie siehts mit libkdtree++ aus?
Grml... sieht super aus.
Scheint aber leider linux only zu sein.
(Das Debian im Namen hätt mich schon irritieren sollen)Visual Studio 2005 mag's mal nicht fressen...
Bei anderen auch nicht: http://lists.alioth.debian.org/pipermail/libkdtree-devel/2007-November/000045.html
-
Samhayne schrieb:
Grml... sieht super aus.
Scheint aber leider linux only zu sein.
(Das Debian im Namen hätt mich schon irritieren sollen)Visual Studio 2005 mag's mal nicht fressen...
Das ist doch "lediglich" eine Datenstruktur. Die wird also wohl kaum auf Linux-Systemaufrufe zurückgreifen. Daher sollte sie eigentlich auf jedem Betriebssystem laufen (habs mir aber nicht angeschaut).
Es kann natürlich sein, dass sie ein paar Dinge benutzt haben, die der GCC kann aber der Microsoft compiler nicht.
Was für Fehler bekommst du beim kompilieren?
-
Hattest natürlich absolut Recht.
Hab's inzwischen hingekriegt und in der Mailingliste des Projekts geschrieben, was ich ändern musste.
Die nächsten Versionen werden dann hoffentlich VC kompatibel.
Und der Speedup ist gewaltig.
