Quadtree

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.

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 (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 2ⁿ × 2ⁿ 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.

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 ${\displaystyle O(\log(n))}$ oft sehr effizient beim Vergleichen zweidimensionaler, sortierter Datenpunkte.

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ä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.

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 ${\displaystyle u}$ am Anfang dieses Pfads gespeichert werden muss und der an seinem Ende angehängte Teilbaum an den Knoten ${\displaystyle u}$. Es ist immer noch möglich, dass diese komprimierten Bäume eine lineare Höhe haben, wenn die Eingabedaten ungünstig ist.

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 ${\displaystyle q}$, d. h die Bestimmung des Bereichs, die ${\displaystyle q}$ enthalten würde, die Operationen Einfügen und Löschen alle in der Laufzeit ${\displaystyle O(\log(n))}$ durchgeführt werden, d. h. die Zeit, die benötigt wird, um eine Suche in der zugrunde liegenden Datenstruktur der geordneten Menge durchzuführen.^[1]

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 ${\displaystyle c}$ wird von einem Nachbarn ${\displaystyle c'}$ bedrängt, wenn ${\displaystyle c}$ genau einen Punkt enthält, und ${\displaystyle c'}$ 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 ${\displaystyle c}$ heißt schlecht abgestimmt (englisch ill-graded), wenn er eine Nachbarzelle ${\displaystyle c'}$ hat, deren Seitenlänge höchstens 4-mal so klein ist wie die Seitenlänge von ${\displaystyle c}$.
• Ein Quaternärbaum heißt gut abgestimmt, wenn jeder seiner nicht zerlegten Bereiche gut abgestimmt ist und nicht bedrängt ist.^[1]

Quadtrees werden für folgende Anwendungen verwendet:

• Bilddarstellung
  
• 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^[2]
• Zustandsrekonstruktion^[3]
• Quadtrees werden auch im Bereich der fraktalen Bildverarbeitung genutzt
• Größte unzusammenhängende Mengen

Quadtrees sind die zweidimensionale Entsprechung zu Octrees.

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 ${\displaystyle l(q)}$ eines Quadranten ${\displaystyle q}$ ist wie folgt definiert:

• ${\displaystyle l(q)=0}$ für den Quadranten ${\displaystyle q}$ des Wurzelknotens
• ${\displaystyle l(q_{s})=l(q)+1}$, wenn ${\displaystyle q_{s}}$ der Quadrant des Kindknotens von Quadrant ${\displaystyle q}$ ist

Ein Quadtree heißt balanciert, wenn gilt:

1. Für jeden Quadranten haben entweder keine oder alle seiner Kindknoten selbst Kindknoten.
2. Für die Level benachbarter Quadranten ${\displaystyle q}$ und ${\displaystyle q'}$ gilt ${\displaystyle |l(q)-l(q')|\leq 1}$.

Die folgenden Operationen können zum Ausgleichen eines Quadtrees verwendet werden:

• Wenn die Bedingung 1. für den Quadranten ${\displaystyle q}$ verletzt ist, teile die Kindknoten von ${\displaystyle q}$, die Quadranten von Blattknoten sind.
• Für benachbarte Quadranten ${\displaystyle q}$ und ${\displaystyle q'}$ der Blattknoten, die die Ungleichung ${\displaystyle l(q)<l(q')-1}$ erfüllen, teile ${\displaystyle q}$.

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 ${\displaystyle l(q)}$, die Knoten mit Level ${\displaystyle l(v)>l(q)}$ 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.^[4]

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.^[5]

#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)                 {                     bottomLeftTree = new Quadtree(Point(topLeft.x, (topLeft.y + bottomRight.y) / 2), Point((topLeft.x + bottomRight.x) / 2, bottomRight.y));                 }                 bottomLeftTree->insert(node);             }         }         else         {             // Bedingung für den Teilbaum rechts oben             if ((topLeft.y + bottomRight.y) / 2 >= node->point.y)             {                 if (topRightTree == NULL)                 {                     topRightTree = new Quadtree(Point((topLeft.x + bottomRight.x) / 2, topLeft.y), Point(bottomRight.x, (topLeft.y + bottomRight.y) / 2));                 }                 topRightTree->insert(node);             }             // Bedingung für den Teilbaum rechts unten             else             {                 if (bottomRightTree == NULL)                 {                     bottomRightTree = new Quadtree(Point((topLeft.x + bottomRight.x) / 2, (topLeft.y + bottomRight.y) / 2), Point(bottomRight.x, bottomRight.y));                 }                 bottomRightTree->insert(node);             }         }     }      // Diese rekursive Funktion sucht einen Knoten     Node* searchNode(Point point)     {         if (!inBoundary(point))         {             return NULL;         }         if (root != NULL)         {             return root;         }         // Wenn der untere rechte Teilbaum leer ist         if ((topLeft.x + bottomRight.x) / 2 >= point.x)         {             // Wenn der Knoten im Gebiet für den oberen linken Teilbaum liegt             if ((topLeft.y + bottomRight.y) / 2 >= point.y)             {                 if (topLeftTree == NULL)                 {                     return NULL;                 }                 return topLeftTree->searchNode(point);             }             // Wenn der Knoten im Gebiet für den unteren linken Teilbaum liegt             else             {                 if (bottomLeftTree == NULL)                 {                     return NULL;                 }                 return bottomLeftTree->searchNode(point);             }         }         else         {             // Wenn der Knoten im Gebiet für den oberen rechte Teilbaum liegt             if ((topLeft.y + bottomRight.y) / 2 >= point.y)             {                 if (topRightTree == NULL)                 {                     return NULL;                 }                 return topRightTree->searchNode(point);             }             // Wenn der Knoten im Gebiet für den unteren rechten Teilbaum liegt             else             {                 if (bottomRightTree == NULL)                 {                     return NULL;                 }                 return bottomRightTree->searchNode(point);             }         }     };      // Prüft, ob der aktuelle Quadtree den Punkt enthält     bool inBoundary(Point point)     {         return (point.x >= topLeft.x && point.x <= bottomRight.x && point.y >= topLeft.y && point.y <= bottomRight.y);     } };  // Hauptfunktion die das Programm ausführt int main() {     Quadtree center(Point(0, 0), Point(8, 8));     Node node1(Point(1, 1), 1);     Node node2(Point(2, 5), 2);     Node node3(Point(7, 6), 3);     center.insert(&node1);     center.insert(&node2);     center.insert(&node3);     cout << "Knoten 1: " << center.searchNode(Point(1, 1))->value << "\n";     cout << "Knoten 2: " << center.searchNode(Point(2, 5))->value << "\n";     cout << "Knoten 3: " << center.searchNode(Point(7, 6))->value << "\n";     cout << "Nicht existierender Knoten: " << center.searchNode(Point(5, 5)); } 

• Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50255-0.
• Hanan Samet: Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50300-X.
• R. A. Finkel, J. L. Bentley: Quad trees a data structure for retrieval on composite keys. In: Acta Informatica. Band 4, Nr. 1, ISSN 0001-5903, S. 1–9, doi:10.1007/BF00288933. 
• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf (Hrsg.): Computational Geometry. Algorithms and applications. 2., rev. Auflage. Springer, Berlin u. a. 2000, ISBN 3-540-65620-0, 14: Quadtrees, S. 291–306. 
• Hanan Samet, Robert Webber: Storing a Collection of Polygons Using Quadtrees. (PDF) Juli 1985, abgerufen am 23. März 2012. 

Commons: Quadtrees – Sammlung von Bildern, Videos und Audiodateien

• Raumunterteilungsdemos (englisch)
• Besprechung des Quaternärbaumes mit einer Anwendung
• Besprechung und Vorführungen räumlicher Indizierung (Memento vom 4. Februar 2012 im Internet Archive)
• Java-Implementierung
• Java-Anleitung
• C++-Implementierung eines Quaternärbaumes zur räumlichen Indizierung von Dreiecken
• Objective-C-Implementierung eines Quaternärbaumes für GPS-Clustering
• SquareLanguage
• Funktionsfähige Vorführung des Quaternärbaumalgorithmus in JavaScript
• MIT-lizenzierte Quaternärbaum-Bibliothek in JavaScript
• Animierter Quaternärbaum mit Source Code in JavaScript

1. ↑ ^{a b} Umut A. Acar, Benoît Hudson: Dynamic Mesh Refinement with Quad Trees and Off-Centers
2. ↑ Tomas G. Rokicki: An Algorithm for Compressing Space and Time. 1. April 2006, abgerufen am 20. Mai 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, Edinburgh, United Kingdom, Juli 2010.
4. ↑ Robert Schneiders: Algorithms for Quadrilateral and Hexahedral Mesh Generation
5. ↑ GeeksforGeeks: Quad Tree