Quadtree: Jak Wyszukiwać Płaszczyznę Bez Sprawdzania Każdego Punktu

Problem z prostym zestawem punktów

Zadaj pytanie "Których z tych dziesięciu tysięcy punktów leży w środku tego małego kwadratu?" i prosta tablica zmusza Cię do sprawdzenia każdego pojedynczego punktu – O(n) dla każdej zapytania, niezależnie od tego, jak mały jest kwadrat lub jak pusta reszta płaszczyzny. Drzewo quadry, wprowadzone przez Rafała Finkel i J.L. Bentley'ego w 1974 roku, rozwiązuje to, organizując przestrzeń samą w sobie, a nie tylko punkty w niej zawarte, dzięki czemu całe puste obszary można pomijać bez ich odwiedzania.

Podział na cztery, gdy węzeł jest zatłoczony

Quadtree to węzeł, który obejmuje obszar płaszczyzny w postaci kwadratu i przechowuje punkty o określonej, niewielkiej pojemności, zazwyczaj 4 do 16. Gdy węzeł przekroczyłby tę pojemność, dzieli się na dokładnie cztery równe potomstwa – NW, NE, SW, SE – a punkty są pomiędzy nimi rozkładane w zależności od tego, w który kwadrant spadają. Nazwa pochodzi bezpośrednio od tego czterokrotnego podziału; analogiczna struktura w trzech wymiarach, dzieląca sześcienne kostkę na osiem potomków, to octree.

insert(node, point): if node nie ma potomstwa i długość punktów w węźle jest mniejsza niż pojemność: node.points.push(point); return if node nie ma potomstwa: subdivide(node) // tworzy NW, NE, SW, SE, rozkłada punkty insert(potomstwo, które zawiera punkt, point) Drzewo jest głębokie tam, gdzie punkty są gęsto rozmieszczone, a płytkie tam, gdzie są rzadko rozmieszczone – adaptuje się automatycznie do danych, w przeciwieństwie do stałego siatki, która marnuje pamięć na puste komórki lub przepełnia zbyt wiele punktów w jednym pojemniku, gdziekolwiek skupiają się dane.

insert(node, point):
    if node has no children and node.points.length < capacity:
        node.points.push(point); return
    if node has no children:
        subdivide(node)          // create NW, NE, SW, SE, redistribute
    insert(child that contains point, point)

Dlaczego zapytanie o zakres pomija większość drzewa

Aby znaleźć każdy punkt wewnątrz kwadratu zapytania, należy przejść przez drzewo od korzenia i, w każdym węźle, porównać kwadrat węzła z kwadratem kwadratu zapytania. Jeśli dwa się nie przecinają wcale, całe poddrzewie jest odrzucane w jednym porównaniu, niezależnie od liczby punktów, które ono zawiera. Jeśli kwadrat węzła jest całkowicie zawarty w kwadracie zapytania, wszystkie punkty poniżej niego są zbierane bez dalszych sprawdzian. Tylko węzły, które częściowo przecinają kwadrat zapytania, muszą być rekursywnie przetwarzane przez ich potomstwa.

query(node, rect, out): if !intersects(node.bounds, rect): return // odetnij całe poddrzewie for p in node.points: if rect.contains(p): out.push(p) if node has children: for child in [NW, NE, SW, SE]: query(child, rect, out)

query(node, rect, out):
    if !intersects(node.bounds, rect): return          // prune the whole subtree
    for p in node.points: if rect.contains(p): out.push(p)
    if node has children:
        for child in [NW, NE, SW, SE]: query(child, rect, out)

Gdzie naprawdę się sprawdzają quadtree’e

Silniki gier i fizyczne wykorzystują quadtree’e do szerokozakresowej detekcji kolizji: zamiast testować każdą parę z n ruchomych obiektów przeciwko sobie (O(n²)), każdy obiekt musi być sprawdzony tylko w odniesieniu do niewielkiej liczby innych obiektów, które dzielą z nim ten sam węzeł lub sąsiędzne. Algorytm Barnes-Hut buduje nowy quadtree za każdym razem, gdy uruchamiana jest symulacja, aby przybliżyć długodystansowe siły grawitacyjne lub elektrostatyczne w czasie O(n log n). Serwery map i obrazów tile’owych wykorzystują quadtree indeksów tile'owych, aby zdecydować, który kwadrat obrazu pobrać na danym poziomie zoomu, a bazy danych geograficznych wykorzystują go do odpowiadania na zapytania "co jest w pobliżu" dla milionów rekordów bez pełnego skanowania tabeli.

Wymiana zdań: odtworzenie kontra aktualizacja

Drzewa quadry – są tanie w budowie – O(n log n) dla n punktów wprowadzanych pojedynczo – ale utrzymywanie jednego poprawnego punktu, gdy punkty się poruszają, to właśnie tutaj różnią się implementacje. Usuwanie i ponowne wprowadzanie poruszającego się punktu co ułamek sekundy jest proste i często wystarczająco szybkie; bardziej precyzyjna implementacja łączy potomków węzła, gdy łączna liczba punktów spadnie poniżej dopuszczalnego poziomu, zapobiegając nadmiernemu pogłębianiu się drzewa po rozproszeniu obiektów. W przypadku obciążeń opartych głównie na poruszających się punktach zamiast na zapytaniach o ruch, niektóre silniki po prostu budują całe drzewo od zera co ułamek sekundy – O(n log n) na ponowne zbudowanie jest często tańsze niż koszty prowadzenia ewidencji przy inkrementalnych aktualizacjach.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Quadtree i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.