Quadtree

Ein Quadtree oder quaternärer Baum ( Q-Baum ) ist eine baumartige Datenstruktur, in der jeder Knoten vier untergeordnete Knoten hat. Quadtrees werden am häufigsten verwendet, um einen zweidimensionalen Raum durch rekursive Unterteilung in vier Knoten zu unterteilen.

Quadtrees sind die zweidimensionale Analogie von Octrees . Der Name wird aus Quad und Baum gebildet . Jeder Knoten eines Quadtree unterteilt den Raum, den er darstellt, in vier Unterräume.

Typen

Quadtrees können nach der Art der Daten klassifiziert werden, die sie darstellen, einschließlich Regionen, Punkten, Linien und Kurven. Hier sind einige gebräuchliche Arten von Quadtrees:

Die Quadtree "Region"

Die quadtree "Region" stellt eine Raumaufteilung in zwei Dimensionen dar, indem die Region in vier gleiche Quadranten, dann jeden Quadranten in vier Subquadranten usw. zerlegt wird, wobei jeder "Endknoten" Daten enthält, die einem bestimmten Subquadranten entsprechen Region. Jeder Knoten des Baums hat genau: entweder vier untergeordnete oder keine (bei einem Endknoten). Der Quadtree "Region" ist eine Art Präfixbaum .

Ein "Region" -Quadtree mit der Tiefe n kann verwendet werden, um ein Bild von 2 n  × 2 n  Pixeln darzustellen , wobei der Wert jedes Pixels 0 oder 1 ist. Der übergeordnete Knoten repräsentiert das gesamte Bild. Wenn die Pixel in einem bestimmten Bereich nicht alle 0 oder alle 1 sind, wird dieser Bereich unterteilt. In einer solchen Darstellung eines Bildes repräsentiert jeder Endknoten einen Block von Pixeln, die alle 0 oder alle 1 sind.

Ein Quadtree "Region" kann auch als Darstellung eines Datenfelds mit variabler Auflösung verwendet werden. Beispielsweise können die Temperaturen eines Bereichs in einem Quadtree gespeichert werden, in dem jeder Endknoten die Durchschnittstemperatur des Teilbereichs speichert, den er darstellt.

Wenn ein Quadtree „Region“ verwendet wird, um eine Reihe von Punkten darzustellen (z. B. die Breiten- und Längengrade einer Gruppe von Städten), werden die Regionen unterteilt, bis jeder Endknoten nur noch einen Punkt enthält.

Der "Punkt" Quadtree

Der "Punkt" -Quadreebaum ist eine Anpassung eines Binärbaums , der zur Darstellung zweidimensionaler "Punkt" -Daten (z. B. einer geografischen Koordinate) verwendet wird. Es teilt die Eigenschaften aller Quadtrees, während es ein echter Baum ist , da das Zentrum einer Unterteilung immer auf einem Punkt liegt. Die Form des Baums hängt von der Reihenfolge ab, in der die Daten verarbeitet werden. Eine solche Darstellung ist im Vergleich zu geordneten zweidimensionalen "Punkt" -Daten, die normalerweise in O (log n) -Zeit arbeiten, oft sehr effizient .

Struktur eines Knotens eines "Punkt" -Quadreebaums

Der Knoten eines "Punkt" -Quadreebaums ähnelt dem eines Binärbaums mit diesem großen Unterschied: Der erste hat vier Zeiger (einen für jeden Quadranten), während der zweite nur zwei ("links" und "rechts") hat. Ein weiterer Unterschied ist, dass ein Schlüssel normalerweise in zwei Teile unterteilt ist, die sich auf die x- und y-Koordinaten beziehen. Ein Knoten enthält daher folgende Informationen:

  • vier Zeiger: Quad ['NO'], Quad ['NE'], Quad ['SO'] und Quad ['SE']
  • ein Punkt, der wiederum enthält:
    • ein Schlüssel: normalerweise Koordinaten (x, y)
    • ein Wert: zum Beispiel ein Name.

Der Quadtree "Rand"

"Kanten" -Quadreebäume werden speziell zum Speichern von Linien anstelle von Punkten verwendet. Die Kurven werden angenähert, indem die Zellen auf eine sehr feine Auflösung unterteilt werden. Dies kann zu extrem unausgeglichenen Bäumen führen und somit den Wert der Indizierung negieren.

Der Quadtree "Polygonale Karte"

Der Quadtree (oder CP-Quadtree) der „polygonalen Karte“ ist eine Variation eines Quadtrees, der zum Speichern von Sammlungen potenziell entarteter Polygone (dh mit isolierten Eckpunkten oder Kanten) verwendet wird. Es gibt drei Hauptklassen von CP-Quadtrees, die variieren, je nachdem, welche Informationen sie in jedem "schwarzen Knoten" speichern. CP3-Quadtrees können beliebig viele „nicht schneidende Kanten“ und höchstens einen Punkt speichern. CP2-Quadtrees sind dieselben wie CP3-Quadtrees, außer dass alle Kanten denselben Endpunkt haben müssen. Schließlich ähneln CP1-Quadtrees CP2-Quadtrees, aber "schwarze Knoten" können einen Punkt und seine Kanten oder nur eine Reihe von Kanten enthalten, die sich einen Punkt teilen (Sie können jedoch keinen Punkt und keine Reihe von Kanten haben, die keine enthalten dieser Punkt).

Einige häufige Verwendungen von Quadtrees

Pseudocode

Der folgende Pseudocode zeigt eine mögliche Implementierung eines Quadtree, der nur Punkte behandelt. Es gibt andere gültige Ansätze.

Voraussetzungen

Es wird angenommen, dass die folgenden Strukturen verwendet werden.

// 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) {...} }

QuadTree-Klasse

Diese Klasse repräsentiert sowohl einen Quadtree als auch seinen übergeordneten Knoten.

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) {...} }

Einfügen

Die folgende Methode fügt einen Punkt in den entsprechenden Quadranten eines Quadtree ein und führt bei Bedarf eine Partition durch.

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; } }

Suche in einem Gebiet

Die folgende Methode findet alle Punkte in einem "Suchfeld".

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; } }

Siehe auch

Anmerkungen und Referenzen

Anmerkungen

  1. Hanan Samet  (in) und Robert Webber. "Speichern einer Sammlung von Polygonen mit Quadtrees". ACM Transactions on Graphics, Juli 1985: 182-222. InfoLAB . Netz. 23. März 2012
  2. Tomas G. Rokicki, "  Ein Algorithmus zur Komprimierung von Raum und Zeit  " ,1 st April 2006(abgerufen am 20. Mai 2009 )
  3. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Dichtebäume für eine effiziente nichtlineare Zustandsschätzung , Bericht der 13. Internationalen Konferenz über Informationsfusion, Edinburgh, Großbritannien, Juli 2010.

Allgemeine Hinweise

  1. Raphael Finkel und JL Bentley , "  Quad Trees: Eine Datenstruktur zum Abrufen auf zusammengesetzten Schlüsseln  ", Acta Informatica , vol.  4, n o  1,1974, p.  1–9 ( DOI  10.1007 / BF00288933 )
  2. Mark de Berg , Marc van Kreveld , Mark Overmars und Otfried Schwarzkopf , Computational Geometry , Springer-Verlag ,2000( ISBN  3-540-65620-0 )Kapitel 14: Quadtrees: p.  291–306 .
  3. Hanan Samet und Robert Webber , „  Speichern einer Sammlung von Polygonen mithilfe von Quadtrees  “ ,Juli 1985(abgerufen am 23. März 2012 )

Externe Links