Quadtree

Startseite | Programmieren | C++ | QUADTREE | 01

Ein Überblick bezüglich Quadtrees ist Voraussetzung für das Verständnis dieses Textes. Sollten hier Defizite bestehen, so empfehle ich z.B. Wikipedia oder eine kurze Suche per Google. Sollte nicht mindestens eines dieser Aussagen wahr sein, so ist von einem Weiterlesen abzuraten

• Bei dem Versuch einen Quadtree/Octree zu implementieren ist ein Problem aufgetaucht
• Interesse an der Funktionsweise eines Octrees/Quadtrees
• Es besteht ein grundlegendes Verständnis von rekursiven Funktionen (z.B. Fakultät)

Das Ziel ist einen Octree zu erstellen, der folgende Eigenschaften hat:

• Einfügen und Entfernen von räumlich ausgedehnten Objekten ohne den Octree komplett neu zu erstellen
• Debugging (graphische Darstellung des Trees)
• Alle Objekte im Baum sollen in der tiefsten Ebene (=Knoten, en.: Node) liegen

Um uns an den Octree langsam heranzutasten, beginnen wir mit einer einfachen Version. Als Start beschäftigen wir uns mit einem Quadtree, in den wir Punkte einfügen, welche keine räumliche Ausdehnung besitzen. Die erste Aufgabe besteht darin, den einfachst möglichen Quadtree zu erzeugen. Danach wird der Quadtree angepasst, so dass dieser räumlich ausgedehnte Objekte aufnehmen kann und der letzte Schritt ist die Erweiterung in die dritte Dimension (Octree).

Nachdem der nachfolgende Text versucht ein möglichst gutes Verständnis über Quadtrees zu geben, ist er nicht auf Geschwindigkeit (Programmlaufzeit) optimiert.

Ausgehend von dem Pseudocode, welcher auf der (englischen) Seite von Wikipedia steht, werden zwei Structs (pt2d und BoundaryBox) initialisiert. Das erste repräsentiert einen Punkt in einer zweidimensionalen Ebene und das zweite Struct stellt die Dimension (Ausdehnung) einer Ebene dar. Der Baum selbst wird in Klassenobjekten der Klasse Quadtree gespeichert. Jedes Objekt der Klasse besitzt einen Pointer zu den vier Quadranten (NW, NE, SW, SE), seine Ausdehnung (boundary), die Punkte welche zu der Ebene gehören (children), einen Pointer zu der Elternebene und die Anzahl der Objekte die maximal in einer Ebene gespeichert werden können. Die öffentliche Funktionen dieser Klasse sind: Konstruktor (initialisiert ein Klassenobjekt), die insert-Funktion (fügt ein Objekt dem Baum hinzu), subdivide (teilt den Knoten in vier gleich große Unterknoten), traverse_and_draw (graphische Darstellung des Baums mittels OpenGL). All diese Funktionen werden weiter unten detaillierter erläutert. Die öffentliche Klassenfunktionen sind:

Konstruktor
Initialisiert ein neues Klassenobjekt mit leeren Kindebenen (NW, NE, SW, SE). Initialisierungsparameter des Konstruktors sind die Abmessungen der Ebene (boundary box), ein Pointer zur Elternebene und die Tiefe des Knotens (Root hat Tiefe Null).
traverse_and_draw
Zeichnet den Quadtree mittels OpenGL rekursiv.
subdivide
Diese Routine generiert vier neue Knoten, d.h. der Nullpointer wird mit dem zugehörigen Klassenpointer überschrieben. nodeDepth < maxDepth) // split the node only if the maximum depth has not been reached yet { // subdivide NW std::shared_ptr BB_init_NW(new BoundaryBox(boundary2->cx-boundary2->dim*0.5, boundary2->cy+boundary2->dim*0.5, boundary2->dim*0.5)); northWest = new Quadtree(std::move(BB_init_NW), this, this->nodeDepth+1); // subdivide NE std::shared_ptr BB_init_NE(new BoundaryBox(boundary2->cx+boundary2->dim*0.5, boundary2->cy+boundary2->dim*0.5, boundary2->dim*0.5)); northEast = new Quadtree(std::move(BB_init_NE), this, this->nodeDepth+1); // subdivide SE std::shared_ptr BB_init_SE(new BoundaryBox(boundary2->cx+boundary2->dim*0.5, boundary2->cy-boundary2->dim*0.5, boundary2->dim*0.5)); southEast = new Quadtree(std::move(BB_init_SE), this, this->nodeDepth+1); // subdivide SW std::shared_ptr BB_init_SW(new BoundaryBox(boundary2->cx-boundary2->dim*0.5, boundary2->cy-boundary2->dim*0.5, boundary2->dim*0.5)); southWest = new Quadtree(std::move(BB_init_SW), this, this->nodeDepth+1); } } '; print_cpp($ausgabe, $whitespace); ?>
insert
Dieser Funktion wird ein einzelner Punkt übergeben und dieser Punkt wird in den Quadtree einsortiert. Die erste Abfrage überprüft, ob die x/y-Koordinaten in den Grenzen der aktuellen Ebene liegen. Wenn nicht, wird die Funktion mit false beendet. Sollte der Punkt in der Ebene liegen, so wird überprüft wie viele Elemente in der Ebene sind (anzahl von children). Sollte noch Platz sein, so wird er Punkt dem std::vector hinzugefügt und die Funktion beendet. Wenn die maximale Anzahl an Elementen erreicht wurde, und diese Ebene noch keine Kinder hat (northWest == nullptr), so wird die Ebene mittels subdivide unterteilt. boundary2->cx+boundary2->dim or insertPt.x <= boundary2->cx-boundary2->dim or insertPt.y > boundary2->cy+boundary2->dim or insertPt.y <= boundary2->cy-boundary2->dim) return false; if ((children.size() < maxAmtElements and northWest == nullptr) or this->nodeDepth == maxDepth) // there is room in the node for this pt. Insert the point only if there is no children node available to sort into or if the maximum depth allowed has been reached { children.push_back(insertPt); return true; } // maximum amount of pts in this node reached -> split into 4 new nodes if (northWest == nullptr) // this node has not been split yet -> nullptr { subdivide(); // remove all points from the parent node, and sort this points into the child nodes for (int i = 0; i < (int)children.size(); i++) { // sort this element into the according quadrant(NE, NW, SE, SW) pt2d queryPt(children[i].x, children[i].y); // point to insert into child node insert(queryPt); } for (int i = 0; i < (int)children.size(); i++) children.erase(children.begin()+i); } if (northEast->insert(insertPt)) { return true; } if (northWest->insert(insertPt)) { return true; } if (southWest->insert(insertPt)) { return true; } if (southEast->insert(insertPt)) { return true; } return false; } '; print_cpp($ausgabe, $whitespace); ?> Verwendung der Klasse & deren Funktionen:
Zuerst wird eine boundary box erstellt welche die Umgrenzung der obersten Ebene festlegt (= root node). Danach wird der Quadtree initialisiert (mit der Umgrenzung und dem Nullpointer als Elternknoten). Jeder Punkt kann nun einzeln in den Baum mittels insert() hinzugefügt werden. BB_init2(new BoundaryBox(BB_centerx, BB_centery, BB_dim)); // initialize the QT Quadtree *quadtreeTest = new Quadtree(std::move(BB_init2), nullptr, 0); // insert a point pt2d *insertPt = new pt2d(0, 0); quadtreeTest->insert(*insertPt); // draw the tree quadtreeTest->traverse_and_draw(quadtreeTest, BB_dim); '; print_cpp($ausgabe, $whitespace); ?>
Das nachfolgende Bild zeigt was der Alogrithmus macht, wenn Elemente (Punkte) in den Baum hinzugefügt werden wobei maxAmtElements eins ist, d.h., sollte sich in einer Ebene mehr als ein Punkt befinden so wird diese Ebene (Node) geteilt. Ausgehend von einem leeren Baum (a) wird die insert-Funktion aufgerufen und ein Punkt wird in den Baum hinzugefügt (b) (Der Punkt liegt in der Ebene und kein Punkt befindet sich in dieser Ebene. Der erste Punkt wird somit in die oberste (root) Ebene eingefügt. Ein zweiter Punkt wird in den Baum eingefügt (c): Der Punkt liegt in der obersten Ebene, diese ist aber schon mit einem Punkt belegt. Demzufolge wird diese Ebene mittels subdivide geteilt und der Punkt in die entsprechende Kinderebene eingefügt. Wir fügen einen dritten Punkt (d) hinzu. Genauso wie beim Punkt zuvor ist die oberste Ebene besetzt, es existieren aber Kinderebenen. Dieser Punkt wird somit in die Kinderebene (Nordost) eingefügt. Es sieht so aus, als ob zwei Punkte in der selben Ebene liegen, obwohl maxAmtElements diese Anzahl mit einem Element begrenzen sollte. Das liegt daran, dass ein Punkt in der obersten Ebene (root node) liegt und ein Punkt in der Kinderebene.

Der Baum in (d) kann folgenderweise dargestellt werden (root bezeichnet die erste Ebene):

Dieses Verhalten ist nicht intuitiv, nachdem alle Elemente (Punkte) des Baums nur in den untersten Ebenen sein sollten. Um dies zu erreichen müssen die Punkte nach dem unterteilen (subdivide) neu auf die Kinderebenen aufgeteilt werden. Insbesondere für einen Octree und beim einfügen von räumlich ausgedehnten Objekten in den Baum ist der Pseudocode von Wikipedia nur als Anhaltspunkt zu gebrauchen.

Wir werden nun den Code der insert-Funktion anpassen, sodass sich nur Elemente in den tiefsten Ebenen befinden können:

Der Punkt wird nur in die aktuelle Ebene eingefügt, wenn diese keine Kinderebenen hat (northWest == nullptr) oder die maximale Tiefe maxDepth erreicht wurde. nodeDepth == maxDepth) { children.push_back(insertPt); return true; } '; print_cpp($ausgabe, $whitespace); ?>
Nach dem Teilen der Ebene (subdivide) müssen alle Elemente aus der bestehenden Ebene an die Kinderebenen aufgeteilt werden. split into 4 new nodes if (northWest == nullptr) // this node has not been split yet -> nullptr { subdivide(); // remove all points from the parent node, and sort this points into the child nodes for (int i = 0; i < (int)children.size(); i++) { // sort this element into the according quadrant(NE, NW, SE, SW) pt2d queryPt(children[i].x, children[i].y); // point to insert into child node // sort the point insert(queryPt); } // delete all points in the parent node, so th for (int i = 0; i < (int)children.size(); i++) children.erase (children.begin()+i); } '; print_cpp($ausgabe, $whitespace); ?>

Wir haben nun den wahrscheinlich einfachsten Quadtree, welchen wir realisieren können: Es können Punkte in den Baum hinzugefügt werden und zum debuggen kann der Baum mittels OpenGL dargestellt werden. Alle Elemente des Baums existieren nur in der tiefsten Ebene.

Wenn zwei Punkte, welche nahe beinander liegen in den Baum hinzugefügt werden ergibt sich u.a. folgendes:


Der Baum wurde so oft in Unterebenen unterteilt bis beide Punkte in unterschiedlichen Ebenen liegen was zu einem sehr tiefen Baum führt.

Zusätzliche Quellen & Information:
Videos:
Zeitliche Verhalten des Baums beim hinzufügen von Punkten:
Video1 - maxAmtElements = 5
Video2 - maxAmtElements = 1

Quellcode-Dateien:
https://github.com/clauskovacs/quadtree-points-2d

validate pagespeed Kontakt