C++UCS301
Spatial Data StructuresC++17

Quadtrees

A quadtree recursively divides a 2D region into four quadrants, refining only areas that need more detail.

What to understand

  • Recursive subdivision
  • Point and region queries
  • Adaptive resolution
  • Spatial occupancy

Remember this

  1. 1Each internal node has four quadrants
  2. 2Depth depends on spatial distribution
  3. 3Excellent for sparse, non-uniform maps

Detailed notes

A quadtree recursively partitions a rectangular region into northwest, northeast, southwest, and southeast children. Uniform or empty regions remain coarse while crowded regions subdivide, creating adaptive spatial resolution.

Point-region queries prune any node whose box does not intersect the query. Performance depends on distribution, capacity, and maximum depth; extremely clustered or identical points need termination safeguards.

How it works

  1. 1Define a node boundary and point capacity.
  2. 2Store points locally until capacity is exceeded.
  3. 3Subdivide and route points into containing children.
  4. 4For queries, recurse only into intersecting regions.

Worked trace

Adaptive subdivision

Capacity 2; insert three points in the northeast region
  1. 1The first two points fit in the root node.
  2. 2The third exceeds capacity, so split into four quadrants.
  3. 3Redistribute or route points into their containing quadrants.
  4. 4Only the crowded northeast branch gains more detail.
Result: Sparse regions remain shallow while dense regions refine

Where it is used

  • Map tiles, collision detection, and image compression
  • Pollution and green-cover monitoring
  • Spatial bin and waste-site indexing

Common mistakes

  • Subdividing forever for coincident points
  • Using inconsistent boundary inclusion rules
  • Searching every child without intersection pruning

C++ implementation

C++17 reference
main.cpp

Point quadtree insertion skeleton

A production implementation should add capacity, maximum depth, removal, and geometric range intersection tests.

struct Point { double x, y; };
struct Box { double x, y, width, height; };

class QuadTree {
    Box region;
    vector<Point> points;
    unique_ptr<QuadTree> children[4];
    static constexpr int capacity = 4;

    bool contains(Point p) const {
        return p.x >= region.x && p.x < region.x + region.width &&
               p.y >= region.y && p.y < region.y + region.height;
    }
public:
    explicit QuadTree(Box box) : region(box) {}
    bool insert(Point point) {
        if (!contains(point)) return false;
        if (points.size() < capacity && !children[0]) {
            points.push_back(point);
            return true;
        }
        if (!children[0]) subdivide();
        for (auto& child : children)
            if (child->insert(point)) return true;
        return false;
    }
};
27 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.