Quadtree

Ein Quadtree oder Quaternärbaum ist in der Informatik eine Baum struktur, 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 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.

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 $O(\log(n))$ 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 $u$ am Anfang dieses Pfads gespeichert werden muss und der an seinem Ende angehängte Teilbaum an den Knoten $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 $q$ , d. h die Bestimmung des Bereichs, die $q$ enthalten würde, die Operationen Einfügen und Löschen alle in der Laufzeit $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]

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 $c$ wird von einem Nachbarn $c'$ bedrängt, wenn $c$ genau einen Punkt enthält, und $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 $c$ heißt schlecht abgestimmt (englisch ill-graded), wenn er eine Nachbarzelle $c'$ hat, deren Seitenlänge höchstens 4-mal so klein ist wie die Seitenlänge von $c$ .
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:

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.

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

$l(q)=0$ für den Quadranten $q$ des Wurzelknotens
$l(q_{s})=l(q)+1$ , wenn $q_{s}$ der Quadrant des Kindknotens von Quadrant $q$ 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 $q$ und $q'$ gilt $|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 $q$ verletzt ist, teile die Kindknoten von $q$ , die Quadranten von Blattknoten sind.
Für benachbarte Quadranten $q$ und $q'$ der Blattknoten, die die Ungleichung $l(q)<l(q')-1$ erfüllen, teile $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 $l(q)$ , die Knoten mit Level $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]

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.^[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));
}

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

Weblinks

Commons: Quadtrees – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

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

[:0-1] 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

[1]

[2]

[3]

[4]

[5]