2D indeksowania przestrzennego pytanie:Co to jest nieskończony bezdrzewny quadtree?
Co nazywasz strukturę danych, która jest w zasadzie nieskończona * QuadTree którego węzły zawierają ani współrzędne bezwzględne ani bezwzględne skale - w którym każdy węzeł systemu współrzędnych zostały znormalizowane do jednostki kwadrat (0,0) - (1,1), w którym węzeł najwyższego poziomu nie jest ustalony absolutnie?
To oczywiście czwórka, ale co to jest typ z quadtree? (Czy istnieje powszechna nazwa? Widziałem dziesiątki typów quadtrees wymienionych i opisywanych w literaturze, ale nie w tym konkretnym.)
Aby renderować scenę, dostaniesz jakiś początkowy węzeł (niekoniecznie korzeń), jego rozmiar w pikselach i jego położenie na ekranie. Następnie rysujesz wszystkie obiekty w węźle, skalując ich współrzędne przy użyciu bieżącej macierzy transformacji, którą przesuwasz na stos i zmniejszasz o połowę, gdy idziesz w dół drzewa. Współrzędne bezwzględne węzłów są więc dostępne tylko podczas tymczasowych zmiennych roboczych podczas renderowania i nie są zawarte w samej strukturze danych.
Jeśli obiekt znajdujący się w węźle przemieszcza się poza węzeł (np. Poza kwadratem jednostki), przekazuje się go rodzicowi w celu ponownego przypisania do innego węzła. Jeśli obiekt ulega fragmentacji (na przykład, asteroidę trafioną przez pocisk), mniejsze części są przekazywane do węzłów podrzędnych, które muszą odpowiednio skalować współrzędne, aby utrzymać normalizację kwadratów jednostkowych w każdym węźle.
Kluczową różnicą w stosunku do tradycyjnych implementacji systemów czworokątnych stosowanych w indeksowaniu przestrzennym jest to, że współrzędne obiektów są zawsze względem układu współrzędnych węzła, w którym się znajdują. Relatywizm ten dotyczy nie tylko pozycji, ale i skali.
* Nieskończone z powodu braku współrzędnych bezwzględnych; nawet współrzędne zmiennoprzecinkowe o podwójnej precyzji nadają ograniczeniom położenie i rozmiar, gdy są używane do pozycjonowania absolutnego.
Fred? (żartuję). – bmargulies