mini|300x300px|Ein Punktequaternärbaum mit Punktdaten. Behälterkapazität: 1. mini|300x300px|Quaternärbaumkompression eines Bildes, Schritt für Schritt Ein Quadtree oder Quaternärbaum ist in der Informatik eine Baumstruktur, in der jeder innere Knoten genau vier Kindknoten hat. Quadtrees werden hauptsächlich zur Unterteilung eines zweidimensionalen Raumes genutzt, indem rekursiv in vier Bereiche (Quadranten) unterteilt wird. Die Bereiche können quadratisch oder rechteckig sein oder beliebige Formen haben. Eine ähnliche Aufteilung ist als Q-tree bekannt. Alle Formen von Quadtrees teilen bestimmte Merkmale: Sie zerlegen den Raum in anpassbare Bereiche Jeder Bereich hat eine Maximalkapazität. Wird diese erreicht, so wird der Bereich unterteilt. Das Baumverzeichnis folgt der räumlichen Unterteilung des Quadtrees.
Klassifikation Quadtrees können nach der Art der von ihnen repräsentierten Daten eingeteilt werden, einschließlich Flächen, Punkten und Linien. Quadtrees können auch danach eingeteilt werden, ob die Form des Baumes von der Datenverarbeitungsreihenfolge abhängt oder nicht. Einige gebräuchliche Arten von Quadtrees sind:
Der Bereichsquaternärbaum Der Bereichsquaternärbaum (englisch region quadtree) stellt eine Aufteilung des Raums in zwei Dimensionen dar, der den Bereich in vier gleiche Quadranten, Unterquadranten usw. zerlegt, wobei jeder Endknoten Daten eines bestimmten Unterbereiches enthält. Jeder Knoten in dem Baum hat entweder genau vier Kinder oder gar keine (Blattknoten). Der Bereichsquaternärbaum ist eine Art von Trie.
Ein Bereichsquaternärbaum mit einer Tiefe von n kann benutzt werden um ein Bild aus 2n × 2n Pixeln darzustellen, wobei jeder Bildpunkt den Wert 1 oder 0 hat. Der Wurzelknoten repräsentiert den gesamten Bildbereich. Sofern in einem Bereich nicht alle Bildpunkte Nullen oder Einsen sind, wird dieser unterteilt. In dieser Anwendung steht jeder Endknoten für einen Bildbereich, dessen Bildpunkte sämtlich Nullen oder Einsen sind.
Ein Bereichsquaternärbaum kann auch als eine variabel aufgelöste Repräsentation eines Datenfeldes genutzt werden. Beispielsweise können die Temperaturen in einem Gebiet als Quadtree gespeichert werden, wobei in jedem Blatt die Durchschnittstemperatur des Teilgebietes gespeichert wird.
Wenn ein Bereichsquaternärbaum benutzt wird, um einen Punktdatensatz zu repräsentieren (zum Beispiel Längengrade und Breitengrade einer Anzahl von Städten), so werden Bereiche so oft unterteilt, bis jedes Blatt höchstens einen Punkt enthält.
Punktquaternärbaum Der Punktquaternärbaum (englisch point quadtree) ist eine Anpassung eines Binärbaumes, die zur Darstellung zweidimensionaler Punktdaten genutzt wird. Es teilt die Merkmale eines Quadtrees, ist allerdings ein echter Baum, da das Zentrum einer Unterteilung immer ein Punkt ist. Die Form des Baumes hängt von der Reihenfolge der Datenverarbeitung ab. Er ist mit einer Laufzeit von üblicherweise oft sehr effizient beim Vergleichen zweidimensionaler, sortierter Datenpunkte.
Knotenstruktur eines Punkt-Quad-Trees Ein Knoten eines Quadtrees ähnelt einem Knoten eines Binärbaumes, von dem er sich hauptsächlich durch die vier Zeiger (einer pro Quadrant) von den zwei Zeigern (links und rechts) eines gewöhnlichen Binärbaumes unterscheidet. Zusätzlich ist ein Schlüssel gewöhnlich in zwei Komponenten gegliedert, die sich auf die x- und die y-Koordinaten beziehen. Daher enthält ein Knoten die folgende Information: vier Zeiger: quad[‘NW’], quad[‘NO’], quad[‘SW’] und quad[‘SO’] Punkt, welcher wiederum enthält: Attribut, gewöhnlich als x- und y-Koordinaten ausgedrückt Wert, beispielsweise ein Name
Kantenquaternärbaum Kantenquaternärbäume (englisch edge quadtree) werden besonders zur Speicherung von Linien statt Punkten genutzt. Kurven werden durch fein aufgelöste Unterteilung von Zellen angenähert. Dies kann zu sehr unausgewogenen Bäumen führen, was dem Zweck der Indizierung zuwiderlaufen kann.
Komprimierter Quaternärbaum Wenn jeder Knoten aufbewahrt werden soll, der einer unterteilten Bereiche entspricht, können am Ende viele leere Knoten gespeichert werden. Die Größe solcher sparsamen Bäume kann begrenzt werden, indem nur Teilbäume gespeichert werden, deren Blätter interessante Daten haben. Ein daraus entstehender Quadtree wird komprimierter Quaternärbaum (englisch compressed quadtree) genannt.
Wenn nur wichtige Teilbäume erhalten bleiben, kann der „Beschneidungsprozess“ lange Pfade in dem Baum hinterlassen, in dem die Zwischenknoten den Grad 2 haben (ein Link zu einem Elternknoten und einem Kindknoten). Es stellt sich heraus, dass nur der Knoten am Anfang dieses Pfads gespeichert werden muss und der an seinem Ende angehängte Teilbaum an den Knoten . Es ist immer noch möglich, dass diese komprimierten Bäume eine lineare Höhe haben, wenn die Eingabedaten ungünstig sind.
Obwohl viel von einem Baum abgeschnitten wird, wenn diese Kompression durchgeführt wird, ist es immer noch möglich, eine Suche in logarithmischer Laufzeit die Operationen Suchen, Einfügen und Löschen zu erreichen, indem die Z-Kurve verwendet wird. Die Z-Kurve ordnet jeden Bereich des vollständigen Quadtrees – und damit sogar des komprimierten Quadtrees – in konstanter Laufzeit auf eine eindimensionale Linie ab und ordnet sie auch in konstanter Laufzeit umgekehrt zu, wodurch eine Totalordnung der Elemente entsteht. Daher kann der Quadtree in einer Datenstruktur für geordnete Mengen gespeichert werden, in der die Knoten des Baums gespeichert werden.
Mit diesen Annahmen können die Lokalisierung eines gegebenen Punktes , d. h die Bestimmung des Bereichs, die enthalten würde, die Operationen Einfügen und Löschen alle in der Laufzeit durchgeführt werden, d. h. die Zeit, die benötigt wird, um eine Suche in der zugrunde liegenden Datenstruktur der geordneten Menge durchzuführen.Umut A. Acar, Benoît Hudson: Dynamic Mesh Refinement with Quad Trees and Off-Centers
Gut abgestimmter Quaternärbaum Ein gut abgestimmter Quaternärbaum (englisch well-graded quadtree) ergibt eine hierarchische Unterteilung des Raums in Bereiche (Hyperwürfel in der jeweiligen Dimension), mit der ein gutes Polygonnetz der Eingabedaten durch Anwenden eines Nachbearbeitungsschritts hergestellt werden kann.
Ein gut abgestimmter Quaternärbaum wird wie folgt definiert:
Ein Bereich heißt selbstbedrängt (englisch self-crowded), wenn er zwei oder mehr Eingabepunkte enthält. Ein Bereich wird von einem Nachbarn bedrängt, wenn genau einen Punkt enthält, und mindestens einen Punkt enthält. Ein Bereich heißt bedrängt, wenn er selbstbedrängt ist oder von einem Nachbarn bedrängt wird. Ein Bereich heißt schlecht abgestimmt (englisch ill-graded), wenn er eine Nachbarzelle hat, deren Seitenlänge höchstens 4-mal so klein ist wie die Seitenlänge von . Ein Quaternärbaum heißt gut abgestimmt, wenn jeder seiner nicht zerlegten Bereiche gut abgestimmt ist und nicht bedrängt ist.
Anwendungen Quadtrees werden für folgende Anwendungen verwendet: Bilddarstellung380x380px|Rastergrafik und zugehörige komprimierte Quaternärbaumdarstellung Gittererzeugung Flächenindizierung (zum Beispiel in GIS-Programmen) Effiziente Kollisionserkennung in zwei Dimensionen Sichtvolumenbestimmung bei Geodaten Speichern spärlicher Daten wie der Formatierungsinformation für eine Tabelle oder für manche Matrixberechnungen Lösung von mehrdimensionalen Feldern (numerische Strömungsmechanik, Elektromagnetismus) Conways Spiel des Lebens ZustandsrekonstruktionHenning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation. Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, Juli 2010. Quadtrees werden auch im Bereich der fraktalen Bildverarbeitung genutzt Größte unzusammenhängende Mengen Quadtrees sind die zweidimensionale Entsprechung zu Octrees.
Gittererzeugung Ein 2-Quadtree zur Gittererzeugung wird abgeleitet, indem Quadranten rekursiv in 4 Unterquadranten aufgeteilt werden. Die Tiefe im Quadtree definiert die Level eines Quadranten. Die konforme Hülle kann nur für balancierte Quadtrees gefunden werden. Der Level eines Quadranten ist wie folgt definiert:
für den Quadranten des Wurzelknotens , wenn der Quadrant des Kindknotens von Quadrant ist
Ein Quadtree heißt balanciert, wenn gilt: Für jeden Quadranten haben entweder keine oder alle seiner Kindknoten selbst Kindknoten. Für die Level benachbarter Quadranten und gilt .
Die folgenden Operationen können zum Ausgleichen eines Quadtrees verwendet werden:
Wenn die Bedingung 1. für den Quadranten verletzt ist, teile die Kindknoten von , die Quadranten von Blattknoten sind. Für benachbarte Quadranten und der Blattknoten, die die Ungleichung erfüllen, teile .
Um den Einfügeprozess zu steuern, wird jedem Knoten der Level des kleinsten benachbarten Quadranten als Level für die Knotenunterteilung zugewiesen. Quadranten des Levels , die Knoten mit Level haben, müssen geteilt werden, und die Konfiguration der markierten Knoten bestimmt die Templates, die in die Übergangsquadranten eingefügt werden:
Wenn mehr als 2 Knoten markiert sind, wird Template 2 gewählt. Wenn 2 Knoten markiert sind, bestimmt die Position des zentralen Knotens, wie Template 1 eingefügt wird. Bei weniger als 2 markierten Knoten bleibt der Quadrant unverändert.Robert Schneiders: Algorithms for Quadrilateral and Hexahedral Mesh Generation
Programmierung Das folgende Beispiel in der Programmiersprache C++ zeigt die Implementierung des Quadtree der als Baum mit Zeigern gespeichert wird. Jeder Knoten enthält die Koordinaten für einen Punkt in der zweidimensionalen Ebene. Bei der Ausführung des Programms wird die Funktion main verwendet, die einen kürzesten Weg auf der Konsole ausgibt.GeeksforGeeks: Quad Tree #include <iostream> #include <cmath> using namespace std;
// Dieser Datentyp deklariert einen Punkt in der zweidimensionalen Ebene struct Point { int x; int y; // Konstruktoren Point(int _x, int _y)
x = _x; y = _y;
Point()
x = 0; y = 0;
// Dieser Datentyp deklariert einen Knoten des Baums struct Node { Point point; int value; // Konstruktoren Node(Point _point, int _value)
point = _point; value = _value;
Node()
value = 0;
// Diese Klasse deklariert einen Quadtree und seine 4 Teilbäume class Quadtree { // Wurzelknoten Node* root; // Diese Punkte definieren den Bereich des Quadtree Point topLeft; Point bottomRight; // Kindknoten des Quadtree Quadtree* topLeftTree; Quadtree* topRightTree; Quadtree* bottomLeftTree; Quadtree* bottomRightTree;
public: // Konstruktoren Quadtree()
topLeft = Point(0, 0); bottomRight = Point(0, 0); root = NULL; topLeftTree = NULL; topRightTree = NULL; bottomLeftTree = NULL; bottomRightTree = NULL;
Quadtree(Point _topLeft, Point _bottomRight)
root = NULL; topLeftTree = NULL; topRightTree = NULL; bottomLeftTree = NULL; bottomRightTree = NULL; topLeft = _topLeft; bottomRight = _bottomRight;
// Diese rekursive Funktion fügt dem Quadtree einen Knoten hinzu void insert(Node* node)
if (node == NULL)
return;
// Wenn das Gebiet des aktuellen Quadtree den Punkt nicht enthält, Funktion verlassen if (!inBoundary(node->point))
return;
// Wenn das Gebiet des aktuellen Quadtree den Punkt nicht enthält, Funktion verlassen if (abs(topLeft.x - bottomRight.x) <= 1 && abs(topLeft.y - bottomRight.y) <= 1)
if (root == NULL)
root = node;
return;
// Bedingung für den Teilbaum links unten if ((topLeft.x + bottomRight.x) / 2 >= node->point.x)
// Bedingung für den Teilbaum links unten if ((topLeft.y + bottomRight.y) / 2 >= node->point.y)
if (topLeftTree == NULL)
topLeftTree = new Quadtree(Point(topLeft.x, topLeft.y), Point((topLeft.x + bottomRight.x) / 2, (topLeft.y + bottomRight.y) / 2));
topLeftTree->insert(node);
// Bedingung für den Teilbaum rechts unten else
if (bottomLeftTree == NULL)