kd-tree vs octree dla wyszukiwania promienia 3d

Question

Próbuję dowiedzieć się, która struktura byłaby lepsza do robienia kilku wyszukiwania promienia punktów, drzewa kd lub ośmiu? Było już wspomniane w this question, ale nie było odpowiedzi. Wydaje mi się, że skoro ośmiokrotne ma ustalone rozmiary dla skrzydeł, to można już obliczyć gałęzie, które muszę odwiedzić, podczas gdy dla kd-tree musisz iteracyjnie odwiedzać gałęzie, dopóki promień się nie pokryje.

Answer 1

Dla 3D i ustalonego promienia zapytania, ósemki są dobrym wyborem. Jeśli chcesz pracować na dysku, inne struktury danych mogą być lepsze, ale k-d-tree też tutaj nie świeci.

Dlaczego nie spróbujesz obu i zobaczysz, które działa lepiej dla twoich danych?

Answer 2

W moim projekcie używam ośmiornicy do wyszukiwania zakresów, która działa sprawnie i jest łatwa do wdrożenia. Nigdy jednak nie porównywałem go do drzewa KD. Według mojej wiedzy, najgorszy przypadek złożoności czasowej w drzewach kd dla tej operacji to O (n^(2/3)) dla danych trójwymiarowych, podczas gdy Octree może gwarantować tylko O ​​(n). Więc jeśli zależy Ci na najtrudniejszej złożoności czasu, wybierz Drzewo KD. (Nie dbam o najgorszą złożoność czasu, jeśli wiem, że w moim zestawie danych tak się nigdy nie stanie.)

Answer 3

Zaimplementowałem zarówno osobiście, jak i precyzyjnie w tym celu głosowałbym na ósemkę. Stwierdziłem, że o wiele łatwiej uzyskać bardziej wydajne wyniki przy pomocy ósemki. Mówię łatwiej, ponieważ myślę, że przy takich subtelnych rozróżnieniach, bardziej chodzi bardziej o programistę niż o strukturę danych. Ale myślę, że dla większości ludzi łatwiej będzie zoptymalizować ósemkę.

Jednym z powodów jest to, że drzewa K-D są z natury głębsze, ponieważ drzewa binarne dzielą się na jeden wymiar na raz. Ta głębsza natura może być pomocna, jeśli szukasz precyzyjnego pasującego elementu na liściu jak na skrzyżowaniu promienia/trójkąta z pojedynczą, jednoznaczną ścieżką w dół drzewa. Przydaje się, gdy głębokie drzewo, starannie podzielone, pasuje do idei jakości wyszukiwania.

Nie jest tak pomocne mieć głębokie, starannie podzielone drzewo, jeśli szukasz najbliższego punktu w promieniu maksymalnym, w którym spędzasz większość czasu, przechodząc w górę iw dół drzewa, od liścia do rodzica do rodzeństwa do dziadka rodzica rodzica i tak dalej. Pomaga to w uzyskaniu bardziej płaskiego dostępu do wszystkich elementów w sposób przyjazny dla pamięci podręcznej i umożliwia łatwe tworzenie ośmiu podręcznych pamięci podręcznych, takich jak przechowywanie wszystkich ośmiu dzieci w sposób ciągły, w którym to momencie można to zrobić:

struct OctreeNode 
{ 
    // Index of first child node. To get to the 4th node, 
    // we just access nodes[first_child+3], e.g. 
    int first_child; 
    ... 
}; 

Tak czy inaczej, głosuję na ośmiu w tym przypadku, jeśli są to dwie opcje. Także w przypadku tego typu wyszukiwania zbliżeniowego niekoniecznie chcesz, aby ósemka była zbyt głęboka. Nawet jeśli musimy popatrzeć na więcej punktów niż optymalnie z płytszym drzewem, może to być lepsze niż konieczność częstego wspinania się po drzewie. Pomaga, jeśli punkty, które przechowujesz w liściu, sąsiadują ze sobą. Możesz to osiągnąć poprzez postproces po ukończeniu budowy drzewa.

Uwaga dla obu rozwiązań, które należy przeanalizować w węzłach siostrzanych. Najbliższy punkt do punktu niekoniecznie musi znajdować się w tym samym węźle. Istnieją również przypadki, w których tylko trójwymiarowa siatka może być całkiem optymalna do tego celu, w zależności od charakteru danych, ponieważ w przypadku siatki 3D nigdy nie trzeba się męczyć, aby przejść od dziecka do rodzica, a potem rodzeństwa. Siatki 3D mogą wydawać się wybuchowe w użyciu pamięci, ale nie muszą być koniecznie, jeśli zmniejszysz obciążenie pamięci komórki siatki do zaledwie 32-bitowego indeksu. W takim przypadku siatka o wymiarach 100x100x100 zajmuje mniej niż 4 megabajty.