kd-Baum gegen Octree für 3D-Radius Suche

Question

Ich versuche herauszufinden, welche Struktur wäre besser für mehrere Radius-Suche von Punkten, ein kd-Baum oder ein Octree tun? Es wurde bereits in this question erwähnt, 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 die Zweige besucht werden müssen, bis der Radius abgedeckt ist.

Answer 1

Für 3D und festen Query Radius sind Octrees eine gute Wahl. Wenn Sie auf der Festplatte arbeiten müssen, sind andere Datenstrukturen vielleicht besser, aber der k-d-Baum leuchtet auch hier nicht.

Warum versuchen Sie nicht beide und sehen, welche besser für Ihre Daten funktioniert?

Answer 2

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 des ungünstigsten Falles 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 schlimmste Zeit Komplexität, wenn ich in meinem Datensatz weiß, wird dies nie passieren.)

Answer 3

Ich habe beide persönlich implementiert und genau für diesen Zweck 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 Leute wäre es einfacher, den Octree zu optimieren.

Einer der Gründe dafür ist, dass K-D-Bäume von Natur aus tiefer sind und binäre Bäume sind, 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 nur den Baum hinauf und hinunter gehen, von Blatt zu Eltern zu Geschwister zu Großeltern zu Geschwistern und so weiter. Da hilft es, etwas flacher zu sein, wenn man alles auf Cache-freundliche Weise erreichen kann, und man kann leicht einen Cache-freundlichen 8-Kind-Speicher erstellen, an dem man einfach folgendes tun kann:

Also, jedenfalls stimme ich für den Octree in diesem Fall, 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 dies möglicherweise mit einem Post-Prozess erreichen, nachdem Sie mit der Erstellung 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.