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.kd-tree vs octree dla wyszukiwania promienia 3d
Odpowiedz
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?
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.)
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.
- 1. symetria 3D wyszukiwania algorytm
- 2. KDTree dla długości/szerokości geograficznej
- 3. KDTree Dzielenie
- 4. Implementacja KDTree w Javie
- 5. Kiedy używać partycji Binary Space, Quadtree, Octree?
- 6. scipy kdtree z metadanych
- 7. canvas vs. webGL vs. CSS 3d -> który wybrać?
- 8. Unity 3D: Asset Bundles vs. Resource Folder vs www.Texture
- 9. Algorytmy dla 3D Mazes
- 10. Wykres 3D dla .NET
- 11. SDL vs GLUT w programowaniu 3D OpenGL
- 12. Obliczenie promienia CriteriaBuilder
- 13. Śledzenie promienia - błąd refrakcji
- 14. MySQL vs PostgreSQL Funkcje wyszukiwania JSON
- 15. Hostowane opcje wyszukiwania pełnotekstowego - IndexTank vs Solr vs Lucene
- 16. Biblioteka map 3D dla Androida
- 17. Który silnik 3D dla ruby
- 18. Google Maps Android API v2: Wizualizacja promienia wyszukiwania za pomocą funkcji ValueAnimator
- 19. Optymalizuj scipy najbliższego sąsiada wyszukiwania
- 20. perspektywa krzywoliniowa: Konwersja 3D do 2D
- 21. zmiana promienia narożnika uitableview zgrupowanego w iOS6
- 22. Jak szybko przetestować skrzyżowania promienia z wąską grupą OOBB?
- 23. Algorytm wyszukiwania, ale dla funkcji
- 24. Spersonalizowane wyniki wyszukiwania dla Elasticsearch
- 25. 3D Framework C# WinForm dla symulacji mikromechanicznych
- 26. Stwórz animację 3D dla aplikacji Androidowych
- 27. Czy istnieje struktura opensource dla canvas 3D?
- 28. Silniki gier 3D dla Ruby lub Python?
- 29. Cieniowanie Phonga dla błyszczących powierzchni Pythona 3D
- 30. pozycje etykiet zaznaczania dla matplotlib 3D plot
Chciałbym, żeby to był papier, więc mógłbym cię zacytować ... Ludzie nigdy nie zawracają sobie głowy tymi rzeczami (w mojej dziedzinie) – kotoko