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
Der Bereichsquaternärbaum (englischregion 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 × 2nPixeln 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 (englischpoint 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 (englischedge 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 (englischcompressed 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 ist.
Obwohl viel von einem Baum abgeschnitten wird, wenn diese Kompression durchgeführt wird, ist es immer noch möglich, eine Suche in logarithmischerLaufzeit 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.[1]
Gut abgestimmter Quaternärbaum
Ein gut abgestimmter Quaternärbaum (englischwell-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 (englischself-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 (englischill-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.[1]
Anwendungen
Quadtrees werden für folgende Anwendungen verwendet:
Quadtrees sind die zweidimensionale Entsprechung zu Octrees.
Gittererzeugung
Ein 2-Quadtree zur Gittererzeugung wird abgeleitet, indem Quadrantenrekursiv 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.[4]
#include<iostream>#include<cmath>usingnamespacestd;// Dieser Datentyp deklariert einen Punkt in der zweidimensionalen EbenestructPoint{intx;inty;// KonstruktorenPoint(int_x,int_y){x=_x;y=_y;}Point(){x=0;y=0;}};// Dieser Datentyp deklariert einen Knoten des BaumsstructNode{Pointpoint;intvalue;// KonstruktorenNode(Point_point,int_value){point=_point;value=_value;}Node(){value=0;}};// Diese Klasse deklariert einen Quadtree und seine 4 TeilbäumeclassQuadtree{// WurzelknotenNode*root;// Diese Punkte definieren den Bereich des QuadtreePointtopLeft;PointbottomRight;// Kindknoten des QuadtreeQuadtree*topLeftTree;Quadtree*topRightTree;Quadtree*bottomLeftTree;Quadtree*bottomRightTree;public:// KonstruktorenQuadtree(){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 hinzuvoidinsert(Node*node){if(node==NULL){return;}// Wenn das Gebiet des aktuellen Quadtree den Punkt nicht enthält, Funktion verlassenif(!inBoundary(node->point)){return;}// Wenn das Gebiet des aktuellen Quadtree den Punkt nicht enthält, Funktion verlassenif(abs(topLeft.x-bottomRight.x)<=1&&abs(topLeft.y-bottomRight.y)<=1){if(root==NULL){root=node;}return;}// Bedingung für den Teilbaum links untenif((topLeft.x+bottomRight.x)/2>=node->point.x){// Bedingung für den Teilbaum links untenif((topLeft.y+bottomRight.y)/2>=node->point.y){if(topLeftTree==NULL){topLeftTree=newQuadtree(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 untenelse{if(bottomLeftTree==NULL){bottomLeftTree=newQuadtree(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 obenif((topLeft.y+bottomRight.y)/2>=node->point.y){if(topRightTree==NULL){topRightTree=newQuadtree(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 untenelse{if(bottomRightTree==NULL){bottomRightTree=newQuadtree(Point((topLeft.x+bottomRight.x)/2,(topLeft.y+bottomRight.y)/2),Point(bottomRight.x,bottomRight.y));}bottomRightTree->insert(node);}}}// Diese rekursive Funktion sucht einen KnotenNode*searchNode(Pointpoint){if(!inBoundary(point)){returnNULL;}if(root!=NULL){returnroot;}// Wenn der untere rechte Teilbaum leer istif((topLeft.x+bottomRight.x)/2>=point.x){// Wenn der Knoten im Gebiet für den oberen linken Teilbaum liegtif((topLeft.y+bottomRight.y)/2>=point.y){if(topLeftTree==NULL){returnNULL;}returntopLeftTree->searchNode(point);}// Wenn der Knoten im Gebiet für den unteren linken Teilbaum liegtelse{if(bottomLeftTree==NULL){returnNULL;}returnbottomLeftTree->searchNode(point);}}else{// Wenn der Knoten im Gebiet für den oberen rechte Teilbaum liegtif((topLeft.y+bottomRight.y)/2>=point.y){if(topRightTree==NULL){returnNULL;}returntopRightTree->searchNode(point);}// Wenn der Knoten im Gebiet für den unteren rechten Teilbaum liegtelse{if(bottomRightTree==NULL){returnNULL;}returnbottomRightTree->searchNode(point);}}};// Prüft, ob der aktuelle Quadtree den Punkt enthältboolinBoundary(Pointpoint){return(point.x>=topLeft.x&&point.x<=bottomRight.x&&point.y>=topLeft.y&&point.y<=bottomRight.y);}};// Hauptfunktion die das Programm ausführtintmain(){Quadtreecenter(Point(0,0),Point(8,8));Nodenode1(Point(1,1),1);Nodenode2(Point(2,5),2);Nodenode3(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));}
Literatur
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. Band4, Nr.1, ISSN0001-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.
↑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.