Quelltext der Seite Quadtree

[[Datei:Point quadtree.svg|mini|300x300px|Ein Punktequaternärbaum mit Punktdaten. Behälterkapazität: 1.]]
[[Datei:Quadtree compression of an image.gif|mini|300x300px|Quaternärbaumkompression eines Bildes, Schritt für Schritt]]
Ein '''Quadtree''' oder '''Quaternärbaum''' ist in der [[Informatik]] eine [[Baum (Graphentheorie)|Baum]][[Datenstruktur|struktur]], in der jeder [[Innerer Knoten|innere Knoten]] genau vier Kindknoten hat. Quadtrees werden hauptsächlich zur Unterteilung eines [[Zweidimensional|zweidimensionalen]] Raumes genutzt, indem [[Rekursive Programmierung|rekursiv]] in vier Bereiche ([[Quadrant]]en) unterteilt wird. Die Bereiche können [[quadratisch]] oder [[Rechteck|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'' ([[Englische Sprache|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<sup>n</sup> × 2<sup>n</sup> [[Pixel]]n 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'' ([[Englische Sprache|englisch]] ''point quadtree'') ist eine Anpassung eines [[Binärbaum]]es, 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 (Informatik)|Laufzeit]] von üblicherweise  <math>O(\log(n))</math> 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 (Informatik)|Zeiger]] (einer pro [[Quadrant]]) von den zwei Zeigern (links und rechts) eines gewöhnlichen [[Binärbaum]]es 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'' ([[Englische Sprache|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 [[Baum (Datenstruktur)|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 ([[Englische Sprache|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 (Graphentheorie)|Grad]] 2 haben (ein Link zu einem Elternknoten und einem Kindknoten). Es stellt sich heraus, dass nur der Knoten <math>u</math> am Anfang dieses Pfads gespeichert werden muss und der an seinem Ende angehängte Teilbaum an den Knoten <math>u</math>. 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 [[Datenkompression|Kompression]] durchgeführt wird, ist es immer noch möglich, eine Suche in [[Logarithmisch|logarithmischer]] [[Laufzeit (Informatik)|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 <math>q</math>, d. h die Bestimmung des Bereichs, die <math>q</math> enthalten würde, die Operationen Einfügen und Löschen alle in der [[Laufzeit (Informatik)|Laufzeit]] <math>O(\log(n))</math> durchgeführt werden, d. h. die Zeit, die benötigt wird, um eine Suche in der zugrunde liegenden Datenstruktur der [[Geordnete Menge|geordneten Menge]] durchzuführen.<ref name=":0">Umut A. Acar, Benoît Hudson: [https://www.cs.cmu.edu/~bhudson/papers/acar08dynamic.pdf Dynamic Mesh Refinement with Quad Trees and Off-Centers]</ref>

=== Gut abgestimmter Quaternärbaum ===
Ein ''gut abgestimmter Quaternärbaum'' ([[Englische Sprache|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'' ([[Englische Sprache|englisch]] ''self-crowded''), wenn er zwei oder mehr Eingabepunkte enthält.
* Ein Bereich <math>c</math> wird von einem Nachbarn <math>c'</math> ''bedrängt'', wenn <math>c</math> genau einen Punkt enthält, und <math>c'</math> 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 <math>c</math> heißt ''schlecht abgestimmt'' ([[Englische Sprache|englisch]] ''ill-graded''), wenn er eine Nachbarzelle <math>c'</math> hat, deren Seitenlänge höchstens 4-mal so klein ist wie die Seitenlänge von <math>c</math>.
* Ein Quaternärbaum heißt ''gut abgestimmt'', wenn jeder seiner nicht zerlegten Bereiche gut abgestimmt ist und nicht bedrängt ist.<ref name=":0" />

== Anwendungen ==
Quadtrees werden für folgende Anwendungen verwendet:
* Bilddarstellung<br />[[Datei:Quad tree bitmap.svg|380x380px|Rastergrafik und zugehörige komprimierte Quaternärbaumdarstellung]]
* [[Gittererzeugung]]
* Flächenindizierung (zum Beispiel in [[Geoinformationssystem|GIS]]-Programmen)
* Effiziente [[Kollisionserkennung (Algorithmische Geometrie)|Kollisionserkennung]] in zwei Dimensionen
* [[Sichtbarkeitsproblem|Sichtvolumenbestimmung]] bei [[Geodaten]]
* Speichern spärlicher Daten wie der Formatierungsinformation für eine [[Tabellenkalkulation|Tabelle]] oder für manche [[Matrix (Mathematik)|Matrixberechnungen]]
* Lösung von mehrdimensionalen [[Feld (Physik)|Feldern]] ([[numerische Strömungsmechanik]], [[Elektromagnetismus]])
* [[Conways Spiel des Lebens]]<ref>{{Cite web|url=http://www.ddj.com/hpc-high-performance-computing/184406478|title=An Algorithm for Compressing Space and Time|date=2006-04-01|accessdate=2009-05-20|author=Tomas G. Rokicki}}</ref>
* [[Beobachter (Regelungstechnik)|Zustandsrekonstruktion]]<ref>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.</ref>
* Quadtrees werden auch im Bereich der [[Fraktale Bildkompression|fraktalen]] [[Bildverarbeitung]] genutzt
* Größte unzusammenhängende Mengen
Quadtrees sind die zweidimensionale Entsprechung zu [[Octree]]s.

=== Gittererzeugung ===
Ein 2-Quadtree zur [[Gittererzeugung]] wird abgeleitet, indem [[Quadrant]]en [[Rekursion|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 <math>l(q)</math> eines Quadranten <math>q</math> ist wie folgt definiert:

* <math>l(q) = 0</math> für den Quadranten <math>q</math> des Wurzelknotens
* <math>l(q_s) = l(q) + 1</math>, wenn <math>q_s</math> der Quadrant des Kindknotens von Quadrant <math>q</math> 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 <math>q</math> und <math>q'</math> gilt <math>|l(q) - l(q')| \leq 1</math>.

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

* Wenn die Bedingung 1. für den Quadranten <math>q</math> verletzt ist, teile die Kindknoten von <math>q</math>, die Quadranten von Blattknoten sind.
* Für benachbarte Quadranten <math>q</math> und <math>q'</math> der Blattknoten, die die Ungleichung <math>l(q) < l(q') - 1</math> erfüllen, teile <math>q</math>.

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 <math>l(q)</math>, die Knoten mit Level <math>l(v) > l(q)</math> 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.<ref>Robert Schneiders: [https://www.robertschneiders.de/papers/vki.pdf Algorithms for Quadrilateral and Hexahedral Mesh Generation]</ref>

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C++]] zeigt die Implementierung des Quadtree der als [[Baum (Graphentheorie)|Baum]] mit [[Zeiger (Informatik)|Zeigern]] gespeichert wird. Jeder Knoten enthält die [[Koordinatensystem|Koordinaten]] für einen Punkt in der [[Zweidimensional|zweidimensionalen]] [[Ebene (Mathematik)|Ebene]]. Bei der Ausführung des Programms wird die [[Funktion (Informatik)|Funktion]] ''main'' verwendet, die einen [[Kürzester Weg|kürzesten Weg]] auf der Konsole ausgibt.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/quad-tree/ Quad Tree]</ref>
{|
|
|<syntaxhighlight lang="c++">
#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));
}
</syntaxhighlight>
|}

== 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.
* {{Literatur
   |Autor=R. A. Finkel, J. L. Bentley
   |Titel=Quad trees a data structure for retrieval on composite keys
   |Sammelwerk=Acta Informatica
   |Band=4
   |Nummer=1
   |Verlag=
   |Datum=
   |ISSN=0001-5903
   |Seiten=1–9
   |DOI=10.1007/BF00288933}}
* {{Literatur
   |Autor=
   |Hrsg=Mark de Berg, Marc van Kreveld, [[Mark Overmars]], Otfried Schwarzkopf
   |Titel=Computational Geometry. Algorithms and applications
   |Auflage=2., rev.
   |Verlag=Springer
   |Ort=Berlin u. a.
   |Datum=2000
   |ISBN=3-540-65620-0
   |Kapitel=14: Quadtrees
   |Seiten=291–306}}
* {{Internetquelle
   |url=http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf
   |titel=Storing a Collection of Polygons Using Quadtrees
   |datum=1985-07
   |autor=Hanan Samet, Robert Webber
   |format=PDF
   |zugriff=2012-03-23}}

== Weblinks ==
{{Commonscat|Quadtrees}}
* [http://donar.umiacs.umd.edu/quadtree/index.html Raumunterteilungsdemos] (englisch)
* [http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html Besprechung des Quaternärbaumes mit einer Anwendung]
* {{Webarchiv | url=http://homepages.ge.ucl.ac.uk/~mhaklay/java.htm | wayback=20120204170335 | text=Besprechung und Vorführungen räumlicher Indizierung}}
* [https://github.com/varunpant/Quadtree/ Java-Implementierung]
* [http://javaprogrammernotes.blogspot.ru/2015/01/why-algorithms-matter-quad-tree-example.html Java-Anleitung]
* [[SourceForge:projects/quadtreedemo/|C++-Implementierung eines Quaternärbaumes zur räumlichen Indizierung von Dreiecken]]
* [http://robots.thoughtbot.com/how-to-handle-large-amounts-of-data-on-maps/ Objective-C-Implementierung eines Quaternärbaumes für GPS-Clustering]
* [http://squarelanguage.sourceforge.net/ SquareLanguage]
* [http://jsfiddle.net/sombra2eternity/vNS7m/ Funktionsfähige Vorführung des Quaternärbaumalgorithmus in JavaScript]
* [https://github.com/sombra2eternity/quadtree MIT-lizenzierte Quaternärbaum-Bibliothek in JavaScript]
* [https://bl.ocks.org/mbostock/87fbdfc4533df2ffa02b5bb62bfb5cb6 Animierter Quaternärbaum mit Source Code in JavaScript]

== Einzelnachweise ==
<references />

{{SORTIERUNG:Quadtree}}
[[Kategorie:Suchbaum]]