Która metoda jest preferowana do przechowywania dużych obiektów geometrycznych w kwadracie?

15

Podczas umieszczania obiektów geometrycznych w kwadracie (lub oktawie) możesz umieszczać obiekty większe niż pojedynczy węzeł na kilka sposobów:

  1. Umieszczenie odniesienia do obiektu w każdym liściu, dla którego jest zawarty
  2. Umieszczenie odniesienia do obiektu w najgłębszym węźle, dla którego jest w pełni zawarty
  3. Zarówno # 1, jak i # 2

Na przykład:

wprowadź opis zdjęcia tutaj

Na tym obrazku możesz umieścić okrąg we wszystkich czterech węzłach liści (metoda nr 1) lub tylko w węźle głównym (metoda nr 2) lub w obu (metoda nr 3).

Która metoda jest bardziej powszechna i dlaczego?

graphics data-structures computational-geometry nsantorello
źródło
1
Z pewnością powinien to być punkt odniesienia. Zamierzam zapytać, czy w celu przeszukiwania kwadratu powinny znajdować się odniesienia w liściach, liściach innych lub obu.
nsantorello
PS Edytowane, aby, miejmy nadzieję, wyjaśnić intencje pytania.
nsantorello
Jakie zapytanie próbujesz obsłużyć?
Joe,
@Joe Szczególnie interesuję się wykrywaniem kolizji, indeksowaniem przestrzennym oraz wycinaniem regionu / frustum.
nsantorello
1
@nsantorello Reguła może się różnić w zależności od tego, które z zapytań chcesz obsługiwać, ale wydaje się to bardzo istotne w przypadku wykrywania kolizji: stackoverflow.com/questions/4434335/…
Joe

Odpowiedzi:

8

Zakładając, że przechowujesz odwołanie, a nie sam obiekt, może być sensowne, aby zrobić to inaczej w zależności od aplikacji.

Na przykład, jeśli obliczasz kolizje z tym (jednolitym) kołem, a kolizja występuje w lewym dolnym rogu, byłoby łatwiej, gdybyś miał dostęp do całej geometrii tego liścia bezpośrednio z tego liścia (metoda nr 3) (bez konieczności przesuwania drzewa w górę i określania odziedziczonej geometrii). Ale powiedzmy, że do rysowania geometrii używasz tylko czworokątów, powinieneś użyć metody nr 1, ponieważ sensowne jest tylko narysowanie czegoś w węźle, dla którego jest on w pełni zawarty (trudniej byłoby ustalić, która część narysować dla każdego węzła liścia i gdzie).

Jeśli chodzi o to, co jest bardziej powszechne, moim jedynym doświadczeniem z czworokątami jest pisanie symulacji n-ciała, w której obiekty geometryczne były tak naprawdę tylko punktami, które nie miały obszaru, więc nie mogę definitywnie na to odpowiedzieć.

Rafe Kettler
źródło
Dzięki Rafe, myślę, że masz rację, że zależy to od aplikacji.
nsantorello,
6

Jedną z zalet Quadtree jest to, że nie trzeba dzielić węzła na jego węzły potomne, jeśli wszystkie węzły potomne zawierałyby te same informacje. Może to zaoszczędzić dużo pamięci i przyspieszyć przetwarzanie.

Zgodnie z tą zasadą myślę, że sensowniej jest przechowywać go tylko w węźle głównym (metoda nr 2). Może zaoszczędzić dużo pamięci i myślę, że ułatwiłoby to przetwarzanie. Na przykład, jeśli próbujesz znaleźć przecięcia okręgu za pomocą linii przechodzącej przez trzy węzły liścia, musisz albo obliczyć przecięcie osobno dla każdego węzła liścia, albo pamiętaj, że przecinałeś już to koło.

Z drugiej strony, jeśli masz obiekty w węzłach liści, może to pomóc w wyeliminowaniu fałszywych trafień (obiektów, które musisz sprawdzić pod kątem przecięcia, ponieważ znajdują się we właściwym węźle, ale tak naprawdę się nie przecinają).

Myślę więc, że oba podejścia mają swoje zastosowania i nie jestem pewien, jak wybrać jedno z nich.

Prawdopodobnie nie użyłbym podejścia nr 3, ponieważ nie widzę w nim żadnych pozytywów.

svick
źródło