Ich versuche herauszufinden, welche Struktur für die Suche nach Punkten, einem kd-Baum oder einem Octree besser geeignet wäre. Es wurde bereits erwähnt in diese Frage , aber es gab keine Antwort. Es scheint mir, dass, da Octrees feste Größen für die Blätter haben, bereits die Zweige berechnet werden können, die ich besuchen muss, während für den kd-Baum iterativ Zweige besucht werden müssen, bis der Radius abgedeckt ist.
Für 3D und festen Query Radius sind Octrees eine gute Wahl. Wenn Sie auf der Festplatte arbeiten müssen, können andere Datenstrukturen besser sein, aber der k-d-Baum leuchtet auch hier nicht.
Warum versuchst du beides nicht und siehst, was besser für deine Daten funktioniert?
In meinem Projekt verwende ich einen Octree für die Bereichssuche und es funktioniert effizient und ist einfach zu implementieren. Habe es aber nie mit KD-Tree verglichen. Nach meinem Wissen ist die Komplexität der Zeit im ungünstigsten Fall in kd-Bäumen für diese Operation O (n ^ (2/3)) für dreidimensionale Daten, während Octree nur O (n) garantieren kann. Wenn Sie sich für die komplexeste Zeit interessieren, wählen Sie KD Tree. (Ich interessiere mich nicht für die Komplexität der schlimmsten Zeit, wenn ich in meinem Datensatz weiß, wird dies nie passieren.)
Ich habe beides persönlich und genau zu diesem Zweck umgesetzt, würde für den Octree stimmen. Ich fand es viel einfacher, mit dem Octree ein effizienteres Ergebnis zu erzielen. Ich sage einfacher, weil ich denke, dass es bei diesen subtilen Unterscheidungen mehr um den Implementierer als um die Datenstruktur geht. Aber ich denke, für die meisten Menschen wäre es einfacher, den Octree zu optimieren.
Einer der Gründe dafür ist, dass K-D-Bäume inhärent tiefer sind als binäre Bäume, die sich jeweils in einer Dimension aufspalten. Diese tiefere Natur kann hilfreich sein, wenn Sie nach einem genau passenden Element am Blatt suchen, wie bei einem Strahl / Dreieck-Schnitt mit einem einzigen, eindeutigen Pfad den Baum hinunter. Es ist nützlich, wenn ein tiefer Baum, sorgfältig gespalten, mit der Idee der Suchqualität übereinstimmt.
Es ist nicht so hilfreich, einen tiefen, sorgfältig gespaltenen Baum zu haben, wenn Sie nach dem nächsten Punkt innerhalb eines maximalen Radius suchen, wo Sie die meiste Zeit damit verbringen, den Baum auf und ab zu gehen, vom Blatt zum Elternteil Geschwister zu Großeltern zu Geschwistern und so weiter. Da hilft es, etwas flacher zu sein, wenn man alles cachefreundlich nutzen kann, und man kann leicht einen Cachefreundlichen Octree machen, indem man alle 8 Kinder zusammenhängend speichert, dann kann man das einfach machen:
%Vor%Wie auch immer, ich stimme in diesem Fall für den Octree, wenn dies die beiden Möglichkeiten sind. Auch für diese Art der Nähe-Suche ist es nicht unbedingt notwendig, dass der Octree zu tief ist. Selbst wenn wir mit einem flacheren Baum mehr Punkte als optimal betrachten müssen, kann das besser sein, als den Baum viel auf und ab gehen zu müssen. Es hilft, wenn die Punkte, die Sie in einem Blatt speichern, zusammenhängend sind. Sie können das möglicherweise mit einem Post-Prozess erreichen, nachdem Sie mit dem Aufbau Ihres Baums fertig sind.
Beachten Sie bei beiden Lösungen, dass Sie sich Geschwisterknoten ansehen müssen. Der nächstgelegene Punkt zu einem Punkt ist nicht notwendigerweise derjenige, der sich in demselben Blattknoten befindet. Es gibt auch einige Fälle, in denen ein dreidimensionales Gitter tatsächlich für diesen Zweck ziemlich optimal sein kann, abhängig von der Art Ihrer Daten, da Sie mit dem 3D-Gitter nicht einmal von Kind zu Eltern zu Geschwistern gehen müssen. 3D-Gitter können bei der Speicherbenutzung explosiv erscheinen, müssen aber nicht unbedingt erforderlich sein, wenn Sie den Speicherbedarf einer Gitterzelle auf einen 32-Bit-Index reduzieren. In einem solchen Fall benötigt ein 100x100x100-Raster weniger als 4 Megabyte.
Tags und Links search data-structures kdtree octree