Quadtree

QuadTree lub czwartorzędowe drzewa ( P drzewa ) jest drzewo jak struktura danych , w którym każdy węzeł ma cztery dzieci. Czterodrzewa są najczęściej używane do podziału przestrzeni dwuwymiarowej poprzez rekurencyjny podział na cztery węzły.

Czterodrzewa to dwuwymiarowa analogia ośmiokątów . Nazwa składa się z kwadratu i drzewa . Każdy węzeł czwórki dzieli przestrzeń, którą reprezentuje, na cztery podprzestrzenie.

Rodzaje

Czterodrzewa można klasyfikować według typu danych, które reprezentują, w tym regionów, punktów, linii i krzywych. Oto kilka typowych typów drzew czworokątnych:

„Region” czwórki drzew

Kwadrant „region” reprezentuje podział przestrzeni w dwóch wymiarach poprzez rozbicie regionu na cztery równe ćwiartki, a następnie każdy kwadrant na cztery kwadranty i tak dalej, przy czym każdy „węzeł końcowy” zawiera dane odpowiadające konkretnemu pod-kwadrantowi. region. Każdy węzeł drzewa ma dokładnie: czworo dzieci lub żadnych (przypadek węzła końcowego). „Region” czwórki jest rodzajem drzewa przedrostków .

Czwórkę „regionu” o głębokości n można użyć do przedstawienia obrazu o  wymiarach 2 n × 2 n  pikseli, gdzie wartość każdego piksela wynosi 0 lub 1. Węzeł macierzysty reprezentuje cały obraz. Jeśli nie wszystkie piksele w danym regionie są równe 0 lub wszystkie 1, region ten jest dzielony. W takiej reprezentacji obrazu każdy węzeł końcowy reprezentuje blok pikseli, z których wszystkie mają wartość 0 lub wszystkie 1.

Czworokąt „regionu” może być również używany jako reprezentacja pola danych o zmiennej rozdzielczości. Na przykład temperatury obszaru mogą być przechowywane w postaci czwórki, w której każdy węzeł końcowy przechowuje średnią temperaturę reprezentowanego przez siebie podregionu.

Jeśli czworokąt „regionu” jest używany do reprezentowania zbioru punktów (na przykład szerokości i długości geograficznej grupy miast), regiony są dzielone tak, aby każdy węzeł końcowy zawierał tylko jeden punkt.

Czterodrzewo „punktowe”

Drzewo czworokątne „punktowe” jest adaptacją drzewa binarnego używanego do reprezentowania dwuwymiarowych danych „punktowych” (na przykład współrzędnych geograficznych). Ma cechy wszystkich czworonogów, będąc prawdziwym drzewem , ponieważ środek podziału jest zawsze w punkcie. Kształt drzewa zależy od kolejności przetwarzania danych. Taka reprezentacja jest często bardzo wydajna w porównaniu z uporządkowanymi dwuwymiarowymi danymi „punktowymi”, zwykle działającymi w czasie O (log n) .

Budowa węzła czwórki „punktowej”

Węzeł czworokątnego drzewa „punktowego” jest podobny do węzła drzewa binarnego , z tą dużą różnicą: pierwszy ma cztery wskaźniki (po jednym na każdy kwadrant), podczas gdy drugi ma tylko dwa („lewy” i „prawy”). Inna różnica, klucz jest zwykle podzielony na dwie części, odnoszące się do współrzędnych x i y. Dlatego węzeł zawiera następujące informacje:

  • cztery wskaźniki: quad [„NO”], quad [„NE”], quad [„SO”] i quad [„SE”]
  • punkt, który z kolei zawiera:
    • klucz: zwykle współrzędne (x, y)
    • wartość: na przykład nazwa.

Czterodrzewo „krawędzi”

Czworokątne drzewa „krawędziowe” są specjalnie używane do przechowywania linii, a nie punktów. Krzywe są aproksymowane przez podzielenie komórek do bardzo wysokiej rozdzielczości. Może to spowodować skrajnie niezrównoważone drzewa, a tym samym zanegować wartość indeksowania.

Czwórka „mapy wielokątnej”

Drzewo czworokątne „mapy wielokątnej” (lub drzewo czworokątne CP) jest odmianą drzewa czworokątnego używanego do przechowywania zbiorów potencjalnie zdegenerowanych (tj. Posiadających izolowane wierzchołki lub krawędzie) wielokątów. Istnieją trzy główne klasy drzew czworokątnych CP, różniące się w zależności od tego, jakie informacje przechowują w każdym „czarnym węźle”. Czworokątne drzewa CP3 mogą przechowywać dowolną liczbę „nie tnących krawędzi” i co najwyżej jeden punkt. Czworokątne drzewa CP2 są takie same jak drzewa poczwórne CP3, z tym wyjątkiem, że wszystkie krawędzie muszą mieć ten sam punkt końcowy. Wreszcie, poczwórne drzewa CP1 są podobne do poczwórnych drzew z CP2, ale „czarne węzły” mogą zawierać punkt i jego krawędzie lub tylko zestaw krawędzi współdzielących punkt (ale nie możesz mieć punktu i zestawu krawędzi. Które nie zawierają ten punkt).

Niektóre typowe zastosowania drzew czworokątnych

Pseudo kod

Poniższy pseudokod ilustruje możliwą implementację quadtree obsługującego tylko punkty. Istnieją inne ważne podejścia.

Wymagania wstępne

Zakłada się, że używane są następujące struktury.

// Objet de coordonnées simples pour représenter des points et des vecteurs struct XY { float x; float y; function __construct(float _x, float _y) {...} } // Zone de délimitation alignée sur l'axe, représentée par sa demi-dimension et son centre struct AABB { XY center; XY halfDimension; function __construct(XY center, XY halfDimension) {...} function containsPoint(XY p) {...} function intersectsAABB(AABB other) {...} }

Klasa QuadTree

Ta klasa reprezentuje zarówno drzewo poczwórne, jak i jego węzeł nadrzędny.

class QuadTree { // Constante arbitraire indiquant combien d'éléments peuvent être stockés dans ce nœud de quadtree constant int QT_NODE_CAPACITY = 4; // Zone de délimitation alignée sur l'axe (représentée par sa demi-dimension et son centre) // représentant les limites de ce quadtree AABB boundary; // Points de ce nœeud de quadtree Array of XY [size = QT_NODE_CAPACITY] points; // Enfants QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast; // Méthodes function __construct(AABB _boundary) {...} function insert(XY p) {...} function subdivide() {...} // créer quatre enfants permettant de diviser ce quadrant en quatre quadrants d'égales dimensions function queryRange(AABB range) {...} }

Wprowadzenie

Poniższa metoda wstawia punkt w odpowiedniej ćwiartce drzewa czworokątnego, w razie potrzeby wykonując podział.

class QuadTree { ... // Insérer un point dans le QuadTree function insert(XY p) { // Ignorer les objets qui n'appartiennent pas à ce quadtree if (!boundary.containsPoint(p)) return false; // l'objet ne doit pas être ajouté // S'il reste de la place dans ce quadtree, y ajouter l'objet if (points.size < QT_NODE_CAPACITY) { points.append(p); return true; } // Sinon, subdiviser le quadtree, puis ajouter le point au nœud qui l'acceptera if (northWest == null) subdivide(); if (northWest→insert(p)) return true; if (northEast→insert(p)) return true; if (southWest→insert(p)) return true; if (southEast→insert(p)) return true; // Sinon, le point ne peut être inséré, pour une raison inconnue (cela ne devrait jamais arriver) return false; } }

Szukaj w okolicy

Poniższa metoda znajduje wszystkie punkty w „polu wyszukiwania”.

class QuadTree { ... // Trouver tous les points apparaissant à l'intérieur d'une «zone de recherche» function queryRange(AABB range) { // Préparer le tableau de résultats Array of XY pointsInRange; // Tout interrompre si la «zone de recherche» n'intersecte pas ce quadrant if (!boundary.intersectsAABB(range)) return pointsInRange; // liste vide // Vérifier les objets à ce niveau de quadrant for (int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Terminer ici, s'il n'y a pas d'enfant if (northWest == null) return pointsInRange; // Sinon, relancer la recherche sur les 4 enfants et ajouter les points trouvés pointsInRange.appendArray(northWest→queryRange(range)); pointsInRange.appendArray(northEast→queryRange(range)); pointsInRange.appendArray(southWest→queryRange(range)); pointsInRange.appendArray(southEast→queryRange(range)); return pointsInRange; } }

Zobacz też

Uwagi i odniesienia

Uwagi

  1. Hanan Samet  (w) i Robert Webber. „Przechowywanie zbioru wielokątów za pomocą czworokątów”. ACM Transactions on Graphics, lipiec 1985: 182-222. InfoLAB . Sieć. 23 marca 2012
  2. Tomas G. Rokicki, „  Algorytm kompresji czasu i przestrzeni  ” ,1 st kwiecień 2006(dostęp 20 maja 2009 )
  3. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13th International Conference on Information Fusion, Edynburg, Wielka Brytania, lipiec 2010.

Ogólne odniesienia

  1. Raphael Finkel i JL Bentley , „  Quad Trees: A Data Structure for Retrieval on Composite Keys  ”, Acta Informatica , vol.  4, N O  1,1974, s.  1–9 ( DOI  10.1007 / BF00288933 )
  2. Mark de Berg , Marc van Kreveld , Mark Overmars i Otfried Schwarzkopf , Computational Geometry , Springer-Verlag ,2000( ISBN  3-540-65620-0 )Rozdział 14: Czterodrzewa: s.  291–306 .
  3. Hanan Samet i Robert Webber , „  Przechowywanie kolekcji wielokątów przy użyciu czworokątów  ” ,Lipiec 1985(dostęp 23 marca 2012 )

Linki zewnętrzne