PL 
EnglishDomyślny
Українська🌲 Drzewo czwórkowe
Drzewo czwórkowe rekurencyjnie dzieli płaszczyznę na cztery ćwiartki. Zobacz, jak dopasowuje się do Twojej chmury punktów i przyspiesza zapytania zakresowe, wyszukiwanie najbliższego sąsiada i wykrywanie kolizji — odwiedzając znacznie mniej węzłów niż O(n).
O indeksie przestrzennym Quadtree
Quadtree to struktura drzewiasta, w której każdy węzeł wewnętrzny dzieli swój dwuwymiarowy obszar na dokładnie cztery równe ćwiartki (NW, NE, SW, SE), rekurencyjnie, aż każdy region liściowy zawiera co najwyżej progową liczbę punktów (zwykle jeden). Wynaleziony przez Raphaela Finkela i J.L. Bentleya w 1974 roku i spopularyzowany w geometrii obliczeniowej w latach 80., quadtree redukuje zapytania przestrzenne z czasu liniowego O(n) do O(log n + k), gdzie k to liczba zwróconych wyników. Jest to standardowa struktura przyspieszająca wykrywanie kolizji w fazie wstępnej (broadphase) w dwuwymiarowych silnikach gier, w systemach informacji geograficznej (GIS) oraz w kompresji obrazów (obrazy kodowane quadtree zastępują jednolite regiony pojedynczym węzłem koloru).
Ten symulator pozwala rozrzucić losowe punkty lub klikać, aby umieszczać je pojedynczo, a następnie obserwować, jak drzewo dzieli się w czasie rzeczywistym, gdy przekroczony zostanie próg pojemności węzła. Możesz przeciągnąć prostokąt zapytania zakresowego, by zobaczyć dokładnie, które ćwiartki są odwiedzane, a które pomijane, zliczać odwiedzone węzły w porównaniu z naiwnym skanem liniowym oraz obserwować, jak rozkłady punktów skupionych i jednolitych wpływają na głębokość drzewa i wydajność zapytań.
Najczęściej zadawane pytania
Jaka jest złożoność czasowa zapytania zakresowego w quadtree?
Dla jednolicie losowego zbioru n punktów w jednostkowym kwadracie zapytanie zakresowe zwracające k punktów odwiedza w oczekiwaniu O(√n + k) węzłów — znacznie lepiej niż liniowy skan O(n). W najgorszym przypadku (silnie zdegenerowane rozkłady punktów lub zapytanie obejmujące wiele częściowo nakładających się węzłów) granica rośnie do O(n), ale w praktyce jest to rzadkie. Człon O(√n) pochodzi z liczby komórek quadtree przecinających granicę zapytania bez pełnego zawierania się w nim.
Jak quadtree przyspiesza wykrywanie kolizji w grach?
W dwuwymiarowym silniku fizyki sprawdzanie kolizji dla wszystkich par obiektów ma złożoność O(n²) — niewykonalne dla setek obiektów. Faza wstępna oparta na quadtree działa poprzez wstawienie prostokąta otaczającego każdego obiektu do drzewa, a następnie dla każdego obiektu odpytywanie jedynie obiektów w tej samej lub sąsiednich komórkach liściowych. Jeśli obiekty są rozłożone po przestrzeni, średnia liczba kandydatów na obiekt spada do O(log n) lub mniej, redukując całkowity koszt fazy wstępnej do O(n log n). Silniki takie jak Box2D, Unity 2D i LibGDX wykorzystują do tego celu drzewa przestrzenne (quadtree lub drzewa AABB).
Jaka jest różnica między quadtree punktowym a quadtree PR (point-region)?
Quadtree punktowy dzieli się w miejscu współrzędnych wstawianego punktu — cztery dzieci reprezentują ćwiartki wyśrodkowane na tym punkcie. Quadtree PR (point-region) dzieli przestrzeń w jej geometrycznym środku, niezależnie od położenia punktów, dając stałą strukturę hierarchicznej siatki. Quadtree PR są bardziej przewidywalne pod względem głębokości (zawsze ⌈log₂(D/ε)⌉ dla rozdzielczości ε w domenie D) i łatwiejsze do zaimplementowania bez balansowania. Ten symulator używa wariantu PR, ponieważ podział wokół stałego środka czyni wizualną animację czytelniejszą.
Jak głęboko może rosnąć quadtree?
Maksymalna głębokość quadtree PR jest ograniczona rozdzielczością układu współrzędnych. Dla 32-bitowych współrzędnych zmiennoprzecinkowych w jednostkowym kwadracie minimalna rozróżnialna odległość wynosi około 10⁻⁷, więc drzewo może osiągnąć maksymalnie ~23 poziomy, zanim dwa „odrębne” punkty znajdą się w tym samym liściu. Dla współrzędnych całkowitoliczbowych na siatce 1024×1024 maksymalna głębokość wynosi 10 (ponieważ 2¹⁰ = 1024). W praktyce bardzo głębokie drzewa powstają jedynie wtedy, gdy wiele punktów skupia się na małym obszarze; średnia głębokość dla jednolitego zbioru punktów wynosi O(log n).
Czy quadtree obsługuje dynamiczne wstawianie i usuwanie punktów?
Tak. Wstawianie przechodzi od korzenia do odpowiedniego liścia w czasie O(głębokość), dzieląc liść, jeśli przekracza pojemność. Usuwanie usuwa punkt i, jeśli łączna liczba punktów rodzica spadnie poniżej progu łączenia, zwija cztery węzły dzieci z powrotem w liść rodzica. Obie operacje mają średnio złożoność O(log n) dla jednolicie rozłożonych punktów. Częste wstawianie i usuwanie w skupionym zbiorze punktów może wymagać okresowej przebudowy, by zapobiec poważnemu niezbalansowaniu.
Czym jest octree i jak wiąże się z quadtree?
Octree to trójwymiarowe uogólnienie: każdy węzeł dzieli swój sześcian na osiem równych podsześcianów (oktantów). Octree są szeroko stosowane w trójwymiarowych silnikach gier, przyspieszaniu ray tracingu oraz przetwarzaniu chmur punktów LiDAR. Te same zasady algorytmiczne mają zastosowanie — zapytania zakresowe, wyszukiwanie najbliższego sąsiada i faza wstępna kolizji korzystają z hierarchii przestrzennej. W praktyce trójwymiarowe drzewa BVH (Bounding Volume Hierarchy) często przewyższają octree dla scen dynamicznych, ponieważ dostosowują się do rozkładu punktów zamiast używać stałych podziałów w środku.
Jak quadtree jest wykorzystywany w kompresji obrazów?
Kodowanie obrazu quadtree rekurencyjnie dzieli obraz na ćwiartki. Jeśli wszystkie piksele w ćwiartce mieszczą się w progu pojedynczej wartości koloru, ćwiartka jest przechowywana jako pojedynczy węzeł liścia z tym kolorem — bez potrzeby przechowywania danych per piksel. W przeciwnym razie ćwiartka jest dzielona ponownie. Daje to schemat kompresji bezstratnej (przy progu=0) lub stratnej (przy progu>0). Kompresja fraktalna obrazów (używana w niektórych wczesnych grach na CD-ROM) to pokrewna technika. Nowoczesne kodeki (HEVC, AV1) używają hierarchii jednostek kodujących (CU) podobnych do quadtree, by dzielić klatki na bloki o zmiennym rozmiarze do kodowania entropijnego.
Czym jest algorytm zapytania o najbliższego sąsiada w quadtree?
Wyszukiwanie najbliższego sąsiada zaczyna się od korzenia i schodzi do ćwiartki dziecka zawierającej punkt zapytania, utrzymując „aktualnie najlepszego” kandydata. Podczas powrotu w górę rekurencji sprawdzana jest każda ćwiartka siostrzana: jeśli minimalna możliwa odległość od zapytania do ćwiartki (odległość jej najbliższego rogu) jest mniejsza niż aktualnie najlepsza, ćwiartka musi zostać przeszukana — w przeciwnym razie jest pomijana. W praktyce odwiedza to O(log n) węzłów dla danych jednolicie losowych, choć najgorszy przypadek (adwersaryjne rozmieszczenie punktów) to O(n).
Jak quadtree odnosi się do drzewa k-d?
Drzewo k-d (k-wymiarowe drzewo, Bentley 1975) to drzewo podziału przestrzeni binarnej, które cyklicznie przechodzi przez osie współrzędnych przy podziałach, wybierając punkt medianowy wzdłuż bieżącej osi jako wartość podziału. Dla danych 2D drzewo k-d na przemian dzieli wg x i wg y. W przeciwieństwie do quadtree PR, drzewo k-d zawsze balansuje się idealnie (głębokość O(log n) dla n punktów), ale ma gorszą wydajność pamięci podręcznej i trudniej je dynamicznie aktualizować. Empirycznie drzewa k-d przewyższają quadtree dla statycznych zbiorów punktów i niższych wymiarów; quadtree są preferowane dla dynamicznych danych 2D i fazy wstępnej kolizji.
Czym jest „krzywa Z-order” i jak wiąże się z quadtree?
Krzywa Z-order (Mortona) mapuje współrzędne 2D na indeks 1D, przeplatając bity współrzędnych x i y: dla x = b₁b₂b₃ i y = c₁c₂c₃, kod Mortona to b₁c₁b₂c₂b₃c₃. Ta linearyzacja zachowuje lokalność przestrzenną: punkty bliskie na krzywej Z-order są blisko siebie w 2D. Kod Mortona punktu jest dokładnie ścieżką od korzenia do liścia w quadtree PR, zakodowaną jako ciąg binarny. Systemy baz danych (np. DynamoDB, Google S2) używają krzywych Mortona lub Hilberta do indeksowania danych przestrzennych w jednowymiarowych B-drzewach, osiągając wydajność zapytań równoważną quadtree przy użyciu standardowych struktur indeksu.
Czy quadtree może reprezentować niepunktowe dane przestrzenne, takie jak wielokąty?
Tak — quadtree regionowy przechowuje, które komórki (piksele) znajdują się „wewnątrz” wielokąta, dzieląc się, aż komórki są całkowicie wewnątrz, całkowicie na zewnątrz lub osiągnięty zostanie limit rozdzielczości (wtedy przechowywane jako częściowo pokryte). Quadtree wektorowe wstawiają odcinki linii lub wielokąty, testując na każdym poziomie podziału przecięcie. Naiwne przechowywanie dużych wielokątów powoduje duplikację w wielu węzłach; drzewa R (Guttman, 1984) są zazwyczaj preferowane do indeksowania prostokątów i wielokątów w GIS, ponieważ ściśle otaczają obiekty i unikają nadmiarowego przechowywania w wielu węzłach.
O tej symulacji
Ta symulacja na żywo buduje quadtree region-punktowy (PR), gdy rozrzucasz, przeciągasz lub malujesz punkty na płótnie 2D. Ilekroć komórka liścia zawiera więcej punktów niż bieżąca pojemność, dzieli się na cztery równe ćwiartki — NW, NE, SW i SE — wokół własnego środka, rekurencyjnie, dopóki każda komórka nie zmieści się w pojemności lub nie osiągnie stałego limitu głębokości. Zmiana trybu pozwala przeciągnąć prostokąt zapytania zakresowego, poszukać najbliższego sąsiada lub uruchomić ruch wszystkich punktów, by zobaczyć, jak to samo drzewo napędza fazę wstępną kolizji, z licznikami na żywo porównującymi odwiedzone węzły z naiwnym skanem liniowym.
🔬 Co pokazuje
Linie podziału są rysowane w miarę dzielenia się komórek, punkty wewnątrz aktywnego prostokąta zapytania zmieniają kolor na cyjan, a bieżące dopasowanie najbliższego sąsiada jest podświetlone na żółto z okręgiem promienia poszukiwań. W trybie ruchu/kolizji sąsiedztwo każdego punktu jest sprawdzane tylko względem pobliskich komórek, a nie każdego innego punktu, a statystyki porównują pary kandydatów znalezione przez drzewo z liczbą par wymaganą przez naiwne sprawdzenie wszystkich par.
🎮 Jak korzystać
Suwak Pojemność na liść (1–16, domyślnie 4) ustala, ile punktów pomieści komórka przed podziałem; Prędkość animacji (0,1×–3×) skaluje ruch w trybie ruchu/kolizji. Sześć przycisków trybu przełącza między dodaj/przeciągnij, maluj rój, usuń, zapytanie zakresowe, najbliższy sąsiad i ruch/kolizja; Rozrzuć 200, Wyczyść i Reset wypełniają lub opróżniają płótno, a checkboksy Pokaż podział / Pokaż punkty / Pokaż okno zapytania przełączają, co jest rysowane.
💡 Czy wiesz, że?
Quadtree PR zostały wprowadzone przez Raphaela Finkela i J. L. Bentleya w 1974 roku. Ponieważ ten wariant zawsze dzieli się w geometrycznym środku komórki, a nie we współrzędnych punktu, jego maksymalna głębokość jest ustalona wyłącznie przez rozdzielczość — tutaj ograniczona w kodzie do 10 poziomów, więc żadna komórka nie może dzielić się w nieskończoność, nawet jeśli wiele punktów skupi się na małym obszarze.
Najczęściej zadawane pytania
Jak ten quadtree decyduje, kiedy podzielić komórkę?
Każda komórka zaczyna jako pojedynczy liść przechowujący wszystkie jej punkty. Gdy tylko liczba punktów liścia przekroczy wartość suwaka Pojemność na liść, dzieli się on na cztery równe ćwiartki dzieci w swoim własnym środku, redystrybuuje swoje punkty do odpowiednich dzieci i staje się węzłem wewnętrznym. Podział zatrzymuje się, gdy głębokość komórki przekroczy 10, nawet jeśli nadal przechowuje więcej punktów niż jej pojemność.
Co zmienia podniesienie lub obniżenie suwaka pojemności na liść?
Niska pojemność zmusza komórki do znacznie wcześniejszego podziału, więc drzewo rośnie głębiej, z większą liczbą liści i węzłów wewnętrznych dla tego samego zbioru punktów — widoczne w statystykach Liście, Węzły wewnętrzne i Maksymalna głębokość. Wysoka pojemność pozwala każdemu liściowi przechowywać więcej punktów przed podziałem, dając płytsze drzewo, które odwiedza mniej węzłów na zapytanie, ale skanuje więcej punktów wewnątrz każdego liścia.
Jak tryb zapytania zakresowego wypada w porównaniu ze skanem liniowym?
Przeciągnięcie prostokąta w trybie zapytania zakresowego przechodzi drzewo od korzenia, schodząc tylko do ćwiartek dzieci przecinających prostokąt i całkowicie pomijając resztę. Statystyka Odwiedzone węzły dokładnie zlicza, ile komórek zostało w ten sposób sprawdzonych, podczas gdy Skan liniowy zawsze pokazuje łączną liczbę punktów — różnica między tymi dwiema liczbami to oszczędność, jaką daje drzewo w porównaniu ze sprawdzaniem każdego punktu z osobna.
Jak wyszukiwanie najbliższego sąsiada unika sprawdzania każdego punktu?
Wybranie celu w trybie najbliższego sąsiada najpierw przeszukuje ćwiartkę dziecka zawierającą punkt, by uzyskać wstępną aktualnie najlepszą odległość, a następnie ponownie sprawdza jedynie ćwiartki siostrzane, których najbliższy możliwy róg jest bliżej niż ta najlepsza odległość — reszta jest pomijana. Żółty okrąg narysowany wokół punktu zapytania oznacza aktualnie najlepszą odległość, a Odwiedzone węzły pokazuje, ile komórek faktycznie zbadano.
Co dzieje się w trybie ruchu/kolizji?
Każdy punkt otrzymuje prędkość i odbija się od krawędzi płótna, a w każdej klatce quadtree jest przebudowywany i używany do wykonania małego zapytania zakresowego wokół każdego punktu, by znaleźć pobliskich kandydatów do kolizji, zamiast porównywać go z każdym innym punktem. Statystyki Wynik zapytania i Odwiedzone węzły pokazują unikalne pary kandydatów znalezione przez quadtree, podczas gdy Skan liniowy pokazuje łączną liczbę par wymaganą przez naiwne sprawdzenie wszystkich par.