Quadtree z duplikatami

Wdrażam quadtree. Dla tych, którzy nie znają tej struktury danych, dołączam następujący mały opis:

QuadTree jest strukturą danych i jest w płaszczyźnie euklidesowej co za Octree jest w 3-wymiarowej przestrzeni. Częstym zastosowaniem czworokątów jest indeksowanie przestrzenne.

Podsumowując, jak działają, quadtree to kolekcja - powiedzmy tutaj o prostokątach - o maksymalnej pojemności i początkowej obwiedni. Przy próbie wstawienia elementu do kwadratu, który osiągnął maksymalną pojemność, kwadratura jest podzielona na 4 kwadraty (których geometryczna reprezentacja będzie miała cztery razy mniejszą powierzchnię niż drzewo przed wstawieniem); każdy element jest redystrybuowany w poddrzewach zgodnie z jego pozycją, tj. górna lewa granica podczas pracy z prostokątami.

Tak więc czworokąt jest albo liściem i ma mniej elementów niż jego pojemność, albo drzewem z czterema czworokątami jako dziećmi (zwykle północny zachód, północny wschód, południowy zachód, południowy wschód).

Obawiam się, że jeśli spróbujesz dodać duplikaty, może to być ten sam element kilka razy lub kilka różnych elementów o tej samej pozycji, poczwórne drzewa mają podstawowy problem z obsługą krawędzi.

Na przykład, jeśli pracujesz z czterokołowcem o pojemności 1 i prostokątem jednostki jako obwiednią:

[(0,0),(0,1),(1,1),(1,0)]

I próbujesz wstawić dwa razy prostokąt, którego górna lewa granica jest początkiem: (lub podobnie, jeśli spróbujesz wstawić go N + 1 razy w kwadracie o pojemności N> 1)

quadtree->insert(0.0, 0.0, 0.1, 0.1)
quadtree->insert(0.0, 0.0, 0.1, 0.1)

Pierwsza wkładka nie będzie problemem:

Ale wtedy pierwsza wstawka uruchomi podział (ponieważ pojemność wynosi 1):

Oba prostokąty są zatem umieszczone w tym samym poddrzewie.

Z drugiej strony oba elementy pojawią się w tym samym quadree i uruchomią poddział…

I tak dalej, i tak dalej, metoda podziału będzie działać w nieskończoność, ponieważ (0, 0) zawsze będzie w tym samym poddrzewie spośród czterech utworzonych, co oznacza, że ​​pojawia się nieskończony problem rekurencji.

Czy możliwe jest posiadanie kwadratu z duplikatami? (Jeśli nie, można go zaimplementować jako Set)

Jak możemy rozwiązać ten problem, nie niszcząc całkowicie architektury quadtree?

Wdrażasz strukturę danych, więc musisz podejmować decyzje dotyczące implementacji.

Chyba że quadtree ma coś konkretnego do powiedzenia na temat wyjątkowości - i nie jestem tego świadomy - jest to decyzja wdrożeniowa. Jest on ortogonalny w stosunku do definicji drzewa czworokątnego i możesz go obsługiwać w dowolny sposób. Czteroosobowy mówi, jak wstawiać i aktualizować klucze, ale nie określa, czy muszą być unikalne, czy co można dołączyć do każdego węzła.

Podejmowanie decyzji wdrożeniowych nie jest odradzaniem koła , a przynajmniej pisaniem własnej implementacji.

Dla porównania, standardowa biblioteka C ++ oferuje unikalny zestaw, nieunikalny multiset, unikalną mapę (zasadniczo zestaw par klucz-wartość uporządkowanych i porównanych tylko według klucza) oraz nieunikalną multimapę. Wszystkie są zwykle implementowane przy użyciu tego samego czerwono-czarnego drzewa i żadne nie łamie architektury , po prostu dlatego, że definicja czerwono-czarnego drzewa nie ma nic do powiedzenia na temat unikalności kluczy lub typów przechowywanych w węzłach liści.

Wreszcie, jeśli uważasz, że istnieją badania na ten temat, znajdź je, a następnie możemy to omówić. Może przeoczyłem poczwórne niezmienniki lub jakieś dodatkowe ograniczenie, które pozwala na lepszą wydajność.

Myślę, że tutaj jest nieporozumienie.

Jak rozumiem, każdy węzeł czteroosobowy zawiera wartość indeksowaną przez punkt. Innymi słowy, zawiera potrójną (x, y, wartość).

Zawiera także 4 wskaźniki do węzłów podrzędnych, które mogą być zerowe. Istnieje zależność algorytmiczna między kluczami a łączami potomnymi.

Twoje wkładki powinny wyglądać tak.

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

Pierwsza wstawka tworzy (nadrzędny) węzeł i wstawia do niego wartość.

Druga wstawka tworzy węzeł potomny, łączy się z nim i wstawia do niego wartość (która może być taka sama jak pierwsza wartość).

To, który węzeł potomny zostanie utworzony, zależy od algorytmu. Jeśli algorytm ma postać [x), a przestrzeń współrzędnych mieści się w zakresie [0,1), wówczas każde dziecko obejmie zakres [0,0,5), a punkt zostanie umieszczony w dziecku NW.

Nie widzę nieskończonej rekurencji.

Powszechnym rozwiązaniem, z którym się zetknąłem (w problemach wizualizacji, a nie w grach) jest porzucenie jednego z punktów, albo zawsze zastępując, albo nigdy nie zastępując.

Myślę, że główną zaletą jest to, że jest to łatwe do zrobienia.

Zakładam, że indeksujesz elementy, które są mniej więcej tego samego rozmiaru, w przeciwnym razie życie stanie się skomplikowane lub wolne, albo jedno i drugie ……

Węzeł Quadtree nie musi mieć stałej pojemności. Pojemność jest przyzwyczajona

• Pozwól, aby każdy węzeł drzewa miał ustalony rozmiar w pamięci lub na dysku - nie jest wymagany, jeśli węzeł drzewa zawiera zestaw elementów o zmiennej wielkości i używasz systemu alokacji przestrzeni, który kopiuje. (Np. Obiekty java / c # w pamięci.)
• Zdecyduj, kiedy podzielić węzeł.
  • Możesz po prostu przedefiniować regułę, tak aby węzeł został podzielony, jeśli zawiera więcej niż „n” elementów okręgu, gdzie dystrykt jest definiowany zgodnie z położeniem elementów.
  • Lub użyj „ elementu złożonego ”, więc jeśli w tym samym miejscu znajduje się wiele elementów, możesz wprowadzić nowy element, który zawiera listę tych elementów.

Kiedy masz do czynienia z problemami z indeksowaniem przestrzennym, tak naprawdę polecam zacząć od przestrzennego skrótu lub mojego osobistego ulubionego: zwykłej starej siatki.

... i najpierw zrozum jego słabości, zanim przejdziesz do struktur drzewa, które pozwalają na rzadkie reprezentacje.

Jedną z oczywistych słabości jest to, że możesz marnować pamięć na wiele pustych komórek (chociaż przyzwoicie zaimplementowana siatka nie powinna wymagać więcej niż 32-bitów na komórkę, chyba że faktycznie masz miliardy węzłów do wstawienia). Innym jest to, że jeśli masz elementy średniej wielkości, które są większe niż rozmiar komórki i często obejmują, powiedzmy, dziesiątki komórek, możesz zmarnować dużo pamięci, wstawiając te średniej wielkości elementy do znacznie większej liczby komórek niż idealna. Podobnie, gdy wykonujesz zapytania przestrzenne, być może będziesz musiał sprawdzić więcej komórek, czasem znacznie więcej niż idealne.

Ale jedyną rzeczą, którą należy dopracować za pomocą siatki, aby była jak najbardziej optymalna w stosunku do pewnych danych wejściowych, jest to cell size, co nie pozostawia zbyt wiele do myślenia i majstrowania, i dlatego jest to moja przejdź do struktury danych dla problemów z indeksowaniem przestrzennym, dopóki nie znajdę powodów, aby go nie używać. Jest łatwa do wdrożenia i nie wymaga majstrowania przy niczym więcej niż jednym wejściu środowiska uruchomieniowego.

Możesz wiele wyciągnąć ze zwykłej starej siatki, a ja pokonałem wiele implementacji quad-tree i kd używanych w oprogramowaniu komercyjnym, zastępując je zwykłą starą siatką (choć niekoniecznie były to najlepiej zaimplementowane , ale autorzy spędzili o wiele więcej czasu niż 20 minut, które spędziłem na zrobieniu siatki). Oto krótka rzecz, którą wymyśliłem, aby odpowiedzieć na pytanie w innym miejscu za pomocą siatki do wykrywania kolizji (nawet nie tak naprawdę zoptymalizowanej, zaledwie kilka godzin pracy i musiałem spędzać większość czasu, ucząc się, jak działa wyszukiwanie ścieżek, aby odpowiedzieć na pytanie i po raz pierwszy wdrożyłem tego rodzaju wykrywanie kolizji):

Inną słabością siatek (ale są to ogólne słabości wielu struktur indeksowania przestrzennego) jest to, że jeśli wstawisz wiele zbieżnych lub nakładających się elementów, takich jak wiele punktów o tej samej pozycji, zostaną one wstawione do dokładnie tej samej komórki (s) ) i obniżyć wydajność podczas przechodzenia przez tę komórkę. Podobnie, jeśli wstawisz wiele masywnych elementów, które są znacznie, znacznie większe niż rozmiar komórki, będą chciały zostać wstawione do zestawu komórek i wykorzystują dużo pamięci, zmniejszając czas potrzebny na zapytania przestrzenne na całej planszy .

Jednak te dwa bezpośrednie problemy powyżej z przypadkowymi i masywnymi elementami są w rzeczywistości problematyczne dla wszystkich przestrzennych struktur indeksujących. Zwykła stara siatka faktycznie radzi sobie z tymi patologicznymi przypadkami nieco lepiej niż wiele innych, ponieważ przynajmniej nie chce rekurencyjnie dzielić komórki w kółko.

Kiedy zaczynasz od siatki i dążysz do czegoś w rodzaju drzewa czworokątnego lub drzewa KD, głównym problemem, który chcesz rozwiązać, jest problem z wstawieniem elementów do zbyt wielu komórek, posiadaniem zbyt wielu komórek i / lub konieczność sprawdzania zbyt wielu komórek za pomocą tego rodzaju gęstej reprezentacji.

Ale jeśli myślisz o quad-drzewie jako optymalizacji nad siatkąw przypadku konkretnych przypadków użycia nadal warto pomyśleć o „minimalnym rozmiarze komórki”, aby ograniczyć głębokość rekurencyjnego podziału węzłów drzewa czworokątnego. Gdy to zrobisz, najgorszy scenariusz drzewa czworokątnego będzie nadal rozkładał się w gęstą siatkę na liściach, tylko mniej wydajną niż siatka, ponieważ zajmie to logarytmiczny czas, aby przejść od korzenia do komórki siatki zamiast czas stały. Jednak myślenie o tym minimalnym rozmiarze komórki pozwoli uniknąć scenariusza nieskończonej pętli / rekurencji. W przypadku elementów masywnych istnieją również alternatywne warianty, takie jak luźne drzewa czworokątne, które niekoniecznie dzielą się równomiernie i mogą nakładać się na siebie bloków AABB dla węzłów potomnych. BVH są również interesujące jako struktury indeksowania przestrzennego, które nie dzielą równomiernie swoich węzłów. W przypadku elementów zbieżnych przeciwko strukturom drzewnym najważniejsze jest po prostu nałożenie ograniczenia na podział (lub, jak sugerowali inni, po prostu je odrzucić lub znaleźć sposób, aby traktować je tak, jakby nie przyczyniały się do unikalnej liczby elementów w liściu podczas określania, kiedy liść powinien się podzielić). Drzewo Kd może być również przydatne, jeśli spodziewasz się danych wejściowych z wieloma zbieżnymi elementami, ponieważ musisz wziąć pod uwagę tylko jeden wymiar przy określaniu, czy węzeł powinien podzielić medianę.