Traversing a Quad Tree

Question

I have implemented a Quadtree for sorting points in a graph. Each time a point falls within a quadrant that already contains a point, the quadrant is subdivided again to allow each point to fall into it's own quadrant. Each node has the following attributes:

Rectangle bounds; //The bounds of the quadrant
int num = 0; //The number of points in or below this node
Point point; //The point stored in this node. If the quadrant is divided, this is set to null.
Quadtree sub[]; //Pointers to the 4 subdivided quadrants.

Say I wanted to go through every node that is stored in this tree, and count the number of points that fall within the bounds of a given rectangle, how would I go about recursively checking every node in the tree (Assuming I already have methods that check if they fall in a certain region)?

score 1 · Accepted Answer · edited May 23 '17 at 12:06

You would recurse down each node whose bounds overlap with the given rectangle.

Here's some pseudo code based on the fields that you mention in your question:

int countPointsInRect(Quadtree root, Rectangle r) {

    // Entire bound of current node outside of given rectangle?
    if (root.bounds outside r)
        return 0

    // Part, or whole of current bound inside given rectangle:
    // Recurse on each subtree
    int sum = 0
    for (Quadtree q : sub)
        sum += countPointsInRect(q, r)
    return sum
}

You can optimize it slightly by adding the following check before recursing down the subtrees:

    // Entire bound of current node inside given rectangle?
    if (root.bounds inside r)
        return num  // return immediately. No need to recurse

Additional reading:

Two Rectangles intersection

Ok, that makes sense. Where I'm struggling is how to make a recursive method to check each node. — mattegener, Mar 08 '15 at 20:36
Sure, no problem. Note that I refined it slightly in my last edit. — aioobe, Mar 08 '15 at 20:40

Traversing a Quad Tree

1 Answers1