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.
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" 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" -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" -QuadreebaumsDer 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:
"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 (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).
Der folgende Pseudocode zeigt eine mögliche Implementierung eines Quadtree, der nur Punkte behandelt. Es gibt andere gültige Ansätze.
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) {...} }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) {...} }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; } }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; } }