Quadtree

Home | Programming | C++ | QUADTREE | 01

It is being assumed, that the reader knows the basics about Quadtrees. If not, a brief overview can be obtained from Wikipedia, or by searching on Google. If not at least one of the following statements is true, one should not continue reading.

• Tried to implement a Quadtree/Octree and encountered a problem during the implementation
• Want to build your own Tree adapted to the needs
• Have a basic understanding about recursion (e.g. factorial)
• Are interested how a Octree/Quadtree works

The overall goal is to create a Octree with following properties:

• Insert and remove spatial objects without rebuilding the tree from scratch
• Debugging (draw the tree)
• All objects inserted into the tree should reside in the deepest node possible, i.e., no objects will be placed in any parent node at any time

Since we do not know much about Octrees (or any tree-like structure), we will approach it carefully. That means, starting point will be a Quadtree with non-spatial objects (points). The first task is, to create the simplest Quadtree possible. It will take one point at a time and insert this point into the Quadtree. When the Quadtree is finished and it can handle everything we want (e.g. object manipulation, queries), the Quadtree will be adapted for spatial objects and the final step will be taken into the third dimension.

Since simplicity is the virtue of clarity, the following code is not optimized for speed but for readability. First we focus on understanding, and then we may optimize for speed.

Starting with the pseudocode from Wikipedia, two structs pt2d and BoundaryBox. While the first one represents a single point on the x/y-plane, the second struct defines the boundary of a single node. The tree itself is stored in the class Quadtree. Each class objects gets a pointer to the four quadrants each (NW, NE, SW, SE), its actual boundary surface, the elements in this instance, a pointer to the parent node and the maximum amount of elements allowed in a single node. The public functions of this class are the constructor (initialize a class object), the insert-function (push a point into the tree), subdivide (split this node into four subnodes) and traverse_and_draw (draw the tree using OpenGL). All functions and their purpose will be examined further down.

The public functions of the class are:

Constructor
Initialize a new class object with empty child nodes (NW, NE, SW, SE). The dimensions of the boundary box, a pointer to the parent node and the depth of the created node is passed to the constructor.
traverse_and_draw
Draws the Quadtree using OpenGL recursively.
subdivide
This routine creates the four new nodes, i.e., the nullptr is overwritten with a pointer to the corresponding boundary box. 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
This function will take one single point and tries to insert it into the Quadtree. The first query checks, if the x/y-coordinates of this point match the boundary box of this node. If not, the function returns false and exits. If true, we check how many children (=points) are already in this node. With room we add the point to the std::vector and exit. If the node is full, and there are no children node corresponding to this node (northWest == nullptr), the node is being split with subdivide. 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); ?> How to use the Code & how does it work?
First a boundary box for the root node is defined and the quadtree is initialized (nullptr equals to the root node in the constructor). Every point is being pushed sequentially one after another. 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); ?>
The figure below demonstrates what the algorithm does when we insert some points with maxAmtElements set to one, which means that the node should be split if there is more than one point in the node. We start with an empty tree (a). Upon calling the insert-function for the first point (b), the function checks whether the point lies in the boundary of the root node which is true. Since there are none elements in the tree, the first point is pushed into the root node and the insert-function exits. Another point is then being pushed into the tree (c): Upon inserting, the root node is being split using subdivide because we have a point in the root node and this node has not been split (northWest == nullptr). After splitting the point is then inserted into the corresponding children node. Upon inserting another point (d), the same procedure as before is performed. But the northeast childnode is not being subdivided even though it seems like there are two points in the same node. The catch is, that the first inserted point resides in the root node. The insert-function sees an empty children node (NE) and inserts the third point into this childnode.

The tree (d) in the figure above can be displayed as follows: This behaviour is not intuitive, since we want all elements (points) of the tree only in the deepest nodes which are the child nodes. In the last insertion (d) the point from the root node should be taken out of the root node and reinserted into the tree. This shows, that the direct implementation of the wikipedia page can only be a starting point for a Quadtree. Especially for a Octree and upon insertion of spatial objects, this approach is not suitable.

We will adapt the insert-function, so that only the points can only occupy the deepest nodes:

Only push the point into the node, if it has no children (northWest == nullptr) which means, the deepest node possible was reached or if the maximum set depth has been reached. nodeDepth == maxDepth) { children.push_back(insertPt); return true; } '; print_cpp($ausgabe, $whitespace); ?>
Upon subdividing, all points of the current node must be shuffled into the four child nodes and after that removed from the current node. 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); ?>

We now have one of the most simple Quadtree possible. Pushing elements into the tree and drawing it using OpenGL is possible. All points only reside in the deepest nodes of the tree.

If we push two points close to each other into the tree, we get something like this:


The tree is being split into subnodes until the points can be placed in separate nodes which may result in a very deep tree.

Additional sources & informations:
Videos:
Showing the progression of inserting elements sequentially into the tree
Video1 - maxAmtElements = 5
Video2 - maxAmtElements = 1

Source files:
https://github.com/clauskovacs/quadtree-points-2d

validate pagespeed Contact