Datenstruktur für die Sortierung von Punkten in einer Wolke gesucht.
-
Hallo
Mich hat es vorgestern wieder einmal so richtig gepackt und ich bin dabei, eine Simulation zu programmieren. Derzeit versuche ich gerade, einen etwas komplizierten Algorithmus auf eine Punktewolke anzuwenden, jedoch stosse ich dabei auf das Problem, dass der derzeitige unsortierte Ansatz alles andere als performant ist.
Wie kann ich Punkte in einer Wolke so sortieren, dass Punkte, welche nahe beieinander sind, schneller aufgefunden werden können? Ich arbeite im 3-dimensionalen Raum und die Menge der Punkte ist in der Grössenordnung von 10'000 bis 1'000'000 Punkten. Desweiteren sind die Punkte ungefähr auf der Oberfläche einer Kugel verteilt und bewegen sich vorübergehend nicht mehr.
Hat jemand eine Idee?
-
dazu verwendet man normalerweise einen KD-Tree
-
rapso schrieb:
dazu verwendet man normalerweise einen KD-Tree
zum Beispiel die ANN lib, schön, schnell und einfach zu benutzen:
http://www.cs.umd.edu/~mount/ANN/
-
Besten Dank für das Stichwort KD-Tree, ich werde mich gleich mal einarbeiten.
MfG
