Dlaczego ktoś miałby używać Octree zamiast drzewa KD?

Mam pewne doświadczenie w obliczeniach naukowych i intensywnie korzystałem z drzewek kd do aplikacji BSP (partycjonowanie przestrzeni binarnej). Niedawno zapoznałem się raczej z oktatami, podobną strukturą danych do partycjonowania trójwymiarowych przestrzeni euklidesowych, ale taką, która działa w ustalonych regularnych odstępach czasu, z tego, co zbieram.

Trochę badań dotyczących niezależności wydaje się wskazywać, że drzewa kd są zazwyczaj lepsze pod względem wydajności dla większości zestawów danych - szybsze w budowaniu i wyszukiwaniu. Moje pytanie brzmi: jakie są zalety oktetów w wydajności przestrzennej / czasowej lub w inny sposób i w jakich sytuacjach są najbardziej odpowiednie (słyszałem programowanie grafiki 3D)? Najbardziej doceniłbym podsumowanie zalet i problemów obu typów.

Dodatkowo, jeśli ktoś mógłby rozwinąć wykorzystanie struktury danych R-drzewa i jego zalet, byłbym również za to wdzięczny. R-drzewa (bardziej niż ósemki) wydają się być stosowane podobnie do drzew KD w przypadku wyszukiwania najbliższego sąsiada lub zasięgu.

Komórki w drzewku mogą mieć wysoki współczynnik kształtu, podczas gdy komórki oktty są gwarantowane jako sześcienne. Ponieważ jest to tablica teorii, podam teoretyczny powód, dla którego wysoki współczynnik kształtu stanowi problem: uniemożliwia użycie granic objętości do kontrolowania liczby komórek, które należy zbadać podczas rozwiązywania przybliżonych zapytań najbliższego sąsiada.$kD$

Bardziej szczegółowo: jeśli poprosisz o przybliżonego najbliższego sąsiada do punktu zapytania , a faktyczny najbliższy sąsiad znajduje się w odległości , zwykle kończy się wyszukiwaniem, które sprawdza każdą komórkę struktury danych, która dociera od wewnątrz do zewnętrzna część pierścienia lub pierścieniowa powłoka o wewnętrznym promieniu i zewnętrznym promieniu . Jeśli komórki mają ograniczony współczynnik kształtu, ponieważ znajdują się w poczwórnym drzewie, to może istnieć co najwyżej takich komórek, i możesz udowodnić, że istnieją dobre granice czasu na zapytanie. Jeśli współczynnik kształtu nie jest ograniczony, jak w drzewku , te ograniczenia nie mają zastosowania.q d d ( 1 + ε ) d 1 / ε d - 1 K $\epsilon$$q$$d$$d$$(1+\epsilon)d$$1/\epsilon^{d-1}$$kD$

$kD$drzewa mają inną przewagę nad kwadratami, ponieważ mają gwarancję co najwyżej logarytmicznej głębokości, co również przyczynia się do czasu najbliższego zapytania sąsiada. Ale głębokość kwadratu to co najwyżej liczba bitów precyzji wejściowej, która zasadniczo nie jest duża, i istnieją teoretyczne metody kontrolowania głębokości, które mają być w zasadzie logarytmiczne (patrz struktura danych pomijających kwadratura).

Grupa przyjaciół i ja pracujemy nad kosmiczną grą RTS jako zabawnym projektem pobocznym. Używamy wielu rzeczy, których nauczyliśmy się w informatyce, aby uczynić ją wysoce wydajną, umożliwiając nam później tworzenie potężnych armii.

W tym celu zastanawialiśmy się nad użyciem drzewek kd, ale szybko je odrzuciliśmy: wstawienia i usunięcia są niezwykle powszechne w naszym programie (rozważmy statek latający w kosmosie), a to jest nieświęty bałagan z drzewkami kd. Dlatego wybraliśmy ósemki do naszej gry.

jakie są zalety oktetów w wydajności przestrzennej / czasowej lub w inny sposób, i w jakich sytuacjach są najbardziej odpowiednie (słyszałem programowanie grafiki 3D)?

Drzewa kD są zrównoważonymi drzewami binarnymi, a liczby są próbami, więc zalety i wady są prawdopodobnie odziedziczone po tych bardziej ogólnych strukturach danych. Konkretnie:

• Ponowne równoważenie może być kosztowne (oktoty nie wymagają ponownego równoważenia).
• Równoważenie lepiej radzi sobie z heterogenicznością, ponieważ jest adaptacyjne.
• Wyższy współczynnik rozgałęzienia w oktatach oznacza płytsze drzewa (mniej pośrednich i alokacji) dla jednorodnych rozkładów.

Również bisekcja (jak w oktatach) nadaje się do trywialnej implementacji pod względem kręcenia bitów. Podobnie, wyobrażam sobie, że oktany mogą znacznie skorzystać ze wstępnie obliczonych odległości podczas wyszukiwania zasięgu.

EDYTOWAĆ

Najwyraźniej moje odniesienia do prób i jednorodności wymagają wyjaśnienia.

Próby są rodziną struktur danych reprezentowanych przez drzewa słowników i są używane jako słowniki dla kluczy, które są sekwencjami (w szczególności ciągami, ale także sekwencjami DNA i bitami o wartości skrótu dla prób skrótu). Jeśli każdy słownik odwzorowuje jeden bit każdej ze współrzędnych x, y i z (najbardziej znaczący bit na pierwszym poziomie trie, następny znaczący bit na drugim poziomie itd.), Wówczas trie jest oktawą, która równomiernie dzieli przestrzeń 3D. W związku z tym ósemki dziedziczą cechy prób, które są na ogół:

• Wysoki współczynnik rozgałęzienia może oznaczać płytkie drzewa, które powodują niewielką liczbę pośrednich, dzięki czemu wyszukiwanie jest szybkie, np. 20 poziomów drzewa binarnego można zapisać na 4 poziomach drzewa ze współczynnikiem rozgałęzienia wynoszącym 256.
• Próbki nie są ponownie równoważone podczas wstawiania i usuwania, co oszczędza kosztownej operacji wymaganej dla zrównoważonych drzew binarnych.

Wadą jest to, że heterogeniczność może prowadzić do niezrównoważonych prób / oktetów, więc wyszukiwania mogą wymagać wielu pośrednich. Równoważny problem w próbach rozwiązuje się za pomocą kompresji krawędzi, aby zwinąć wiele poziomów pośrednich na jednym poziomie. Oktty tego nie robią, ale nic nie stoi na przeszkodzie, byś kompresował oktree (ale nie sądzę, byś mógł nazwać wynik ósemką!).

Dla porównania rozważ specjalistyczny słownik kluczy ciągów, który jest reprezentowany jako trie. Pierwszy poziom trie rozgałęzia się na pierwszej postaci w kluczu. Drugi poziom drugiej postaci i tak dalej. Dowolny ciąg znaków można wyszukać, wyszukując pierwszy znak z klucza w słowniku, aby uzyskać drugi słownik, który służy do wyszukiwania drugiego znaku z klucza i tak dalej. Zestaw losowych ciągów kluczy byłby jednorodnym rozkładem. Zestaw ciągów kluczy, które mają ten sam przedrostek (np. Wszystkie słowa zaczynające się od „anty”) są heterogenicznedystrybucja. W tym drugim przypadku pierwszy słownik zawiera tylko jedno wiązanie dla „a”, drugi tylko dla „n” i tak dalej. Wyszukiwanie dowolnego mapowania w trie zawsze polega na przeszukiwaniu tych samych czterech słowników za pomocą tych samych czterech kluczy. Jest to nieefektywne i tak robią oktany, jeśli na przykład są one używane do przechowywania niejednorodnych rozkładów cząstek, w których ogromna większość cząstek znajduje się w niewielkiej objętości w przestrzeni wektorowej.

Octrees są użyteczne jako typ danych bazowy dla modeli ciągłych, patrz na przykład Gerris płynąć Solver. Życie jest wystarczająco trudne w dynamice płynów, więc świadomość, że rozmiary wszystkich twoich podklub zależą tylko od ich głębokości, musi być czynnikiem upraszczającym.

Uwaga: Nie jestem płynnym dynamistą!