Quad Tree (C++ Implementation)

2025-11-20

A quadtree is a tree data structure that partitions 2D space by recursively subdividing it into four quadrants (NE, NW, SE, SW). Quadtrees are commonly used for spatial indexing, collision detection, image compression, adaptive meshes, and range/nearest-neighbor queries.

This article covers:

  • The purpose of quadtrees
  • Key data structures and public interfaces
  • A clean C++ implementation for a point quadtree (PR quadtree)
  • Example usage
  • Complexity, applications, and enhancements

Purpose

Quadtrees are designed to make spatial queries efficient. Instead of scanning all points, a quadtree narrows down the search to regions that intersect with the query, dramatically reducing the number of checks when points are distributed over a large area.

Key Concepts

  • Spatial partitioning: Each node represents an axis-aligned rectangle (boundary). If a node has more points than a threshold (capacity), it subdivides into 4 childs each representing a sub-rectangle.
  • Leaf node: Node with no children, storing up to capacity points.
  • Internal node: Node with 4 children and usually no points stored (or a small buffer).
  • Range queries: Search in a specified rectangle (AABB).
  • Nearest neighbor queries: Search for closest point(s) by pruning subtrees whose boundary cannot contain a closer point than the current best candidate.

Main Data Structures

  • Point: A simple 2D point with associated data or ID.
  • Rect: Axis-aligned bounding box for containment and intersection tests.
  • QuadTree / Node: Stores boundary, vector of points (in leaves), children (subtrees), and the public interfaces (insert, queryRange, nearest, remove, clear).

C++ Implementation (Point Quadtree)

This example implements a simple, robust PR-point quadtree storing points within an AABB. It supports insert, range query, nearest neighbor (1-NN), remove, and clear.

// A compact single-file implementation (C++17)
// Save as quadtree.cpp and compile: g++ -std=c++17 -O2 -Wall quadtree.cpp -o quadtree

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    int id; // optional payload
};

struct Rect {
    double minx, miny, maxx, maxy;
    
    Rect() : minx(0), miny(0), maxx(0), maxy(0) {}
    Rect(double x1, double y1, double x2, double y2)
        : minx(min(x1, x2)), miny(min(y1, y2)), maxx(max(x1, x2)), maxy(max(y1, y2)) {}
    
    bool contains(const Point& p) const {
        return p.x >= minx && p.x <= maxx && p.y >= miny && p.y <= maxy;
    }
    bool intersects(const Rect& other) const {
        return !(other.minx > maxx || other.maxx < minx ||
                 other.miny > maxy || other.maxy < miny);
    }
    double centerX() const { return (minx + maxx) * 0.5; }
    double centerY() const { return (miny + maxy) * 0.5; }
    
    // Squared distance from a point to this rectangle (for NN pruning)
    double sqDistToPoint(double x, double y) const {
        double dx = 0, dy = 0;
        if (x < minx) dx = minx - x;
        else if (x > maxx) dx = x - maxx;
        if (y < miny) dy = miny - y;
        else if (y > maxy) dy = y - maxy;
        return dx * dx + dy * dy;
    }
};

class QuadTree {
public:
    QuadTree(Rect boundary, size_t capacity = 4, unsigned maxDepth = 16)
        : boundary_(boundary), capacity_(capacity), maxDepth_(maxDepth),
          divided_(false), depth_(0) {}

    QuadTree(Rect boundary, size_t capacity, unsigned maxDepth, unsigned depth)
        : boundary_(boundary), capacity_(capacity), maxDepth_(maxDepth),
          divided_(false), depth_(depth) {}

    ~QuadTree() { clear(); }

    bool insert(const Point& p) {
        if (!boundary_.contains(p)) return false;

        if (!divided_ && points_.size() < capacity_) {
            points_.push_back(p);
            return true;
        }

        if (!divided_) {
            if (depth_ >= maxDepth_) {
                // leaf at max depth, accept points
                points_.push_back(p);
                return true;
            }
            subdivide();
        }

        // Pass insertion to children
        if (nw_->insert(p)) return true;
        if (ne_->insert(p)) return true;
        if (sw_->insert(p)) return true;
        if (se_->insert(p)) return true;

        // Should not happen.
        return false;
    }

    // Query points inside a rectangular range
    void queryRange(const Rect& range, vector<Point>& found) const {
        if (!boundary_.intersects(range)) return;

        for (const auto& p : points_) {
            if (range.contains(p)) found.push_back(p);
        }

        if (!divided_) return;

        nw_->queryRange(range, found);
        ne_->queryRange(range, found);
        sw_->queryRange(range, found);
        se_->queryRange(range, found);
    }

    // Nearest neighbor (single)
    optional<Point> nearest(double x, double y) const {
        optional<Point> best;
        double bestDist2 = numeric_limits<double>::infinity();
        nearestRec(x, y, best, bestDist2);
        return best;
    }

    // Remove a point (based on coords and optional ID)
    bool remove(const Point& p) {
        if (!boundary_.contains(p)) return false;

        auto it = find_if(points_.begin(), points_.end(),
                          [&](const Point& q){ return q.id == p.id && q.x == p.x && q.y == p.y; });
        if (it != points_.end()) {
            points_.erase(it);
            return true;
        }

        if (!divided_) return false;

        if (nw_->remove(p)) tryMerge();
        else if (ne_->remove(p)) tryMerge();
        else if (sw_->remove(p)) tryMerge();
        else if (se_->remove(p)) tryMerge();
        else return false;

        return true;
    }

    void clear() {
        points_.clear();
        if (divided_) {
            nw_.reset(); ne_.reset(); sw_.reset(); se_.reset();
            divided_ = false;
        }
    }

    size_t size() const {
        size_t s = points_.size();
        if (divided_) {
            s += nw_->size();
            s += ne_->size();
            s += sw_->size();
            s += se_->size();
        }
        return s;
    }

private:
    Rect boundary_;
    size_t capacity_;
    unsigned maxDepth_;
    unsigned depth_;

    vector<Point> points_;
    bool divided_;

    unique_ptr<QuadTree> nw_, ne_, sw_, se_;

    void subdivide() {
        double cx = boundary_.centerX();
        double cy = boundary_.centerY();

        nw_ = make_unique<QuadTree>(Rect(boundary_.minx, cy, cx, boundary_.maxy), capacity_, maxDepth_, depth_+1);
        ne_ = make_unique<QuadTree>(Rect(cx, cy, boundary_.maxx, boundary_.maxy), capacity_, maxDepth_, depth_+1);
        sw_ = make_unique<QuadTree>(Rect(boundary_.minx, boundary_.miny, cx, cy), capacity_, maxDepth_, depth_+1);
        se_ = make_unique<QuadTree>(Rect(cx, boundary_.miny, boundary_.maxx, cy), capacity_, maxDepth_, depth_+1);

        // Move existing points to children where they belong
        for (const auto& p : points_) {
            if (nw_->insert(p)) continue;
            if (ne_->insert(p)) continue;
            if (sw_->insert(p)) continue;
            if (se_->insert(p)) continue;
        }
        points_.clear();
        divided_ = true;
    }

    // If children are empty and this node is not at max depth, undo subdivision
    void tryMerge() {
        if (!divided_) return;
        if (nw_->size() + ne_->size() + sw_->size() + se_->size() == 0) {
            nw_.reset(); ne_.reset(); sw_.reset(); se_.reset();
            divided_ = false;
        }
    }

    void nearestRec(double x, double y, optional<Point>& best, double& bestDist2) const {
        if (!best && points_.empty() && !divided_) return;

        // If this node can't have a closer point, prune
        double nodeDist2 = boundary_.sqDistToPoint(x, y);
        if (nodeDist2 > bestDist2) return;

        // Check current node points
        for (const auto& p : points_) {
            double dx = p.x - x, dy = p.y - y;
            double d2 = dx*dx + dy*dy;
            if (d2 < bestDist2) {
                bestDist2 = d2;
                best = p;
            }
        }

        if (!divided_) return;

        // Search children in order of proximity to point (heuristic)
        array<pair<double, const QuadTree*>, 4> children = {{
            {nw_->boundary_.sqDistToPoint(x, y), nw_.get()},
            {ne_->boundary_.sqDistToPoint(x, y), ne_.get()},
            {sw_->boundary_.sqDistToPoint(x, y), sw_.get()},
            {se_->boundary_.sqDistToPoint(x, y), se_.get()}
        }};
        sort(children.begin(), children.end(), [](auto &a, auto &b){ return a.first < b.first; });

        for (auto &c : children) {
            if (c.first > bestDist2) break; // prune
            c.second->nearestRec(x, y, best, bestDist2);
        }
    }
};

// Example usage
int main() {
    Rect world(0, 0, 1000, 1000);
    QuadTree tree(world, 4, 10);

    // Insert random points
    std::mt19937 rng(12345);
    std::uniform_real_distribution<double> dist(0.0, 1000.0);
    for (int i = 0; i < 10000; ++i) {
        Point p{dist(rng), dist(rng), i};
        tree.insert(p);
    }

    // Range query
    Rect query(200, 200, 600, 600);
    vector<Point> found;
    tree.queryRange(query, found);
    cout << "Range query found: " << found.size() << " points\n";

    // Nearest neighbor
    double qx = 500, qy = 500;
    auto nearest = tree.nearest(qx, qy);
    if (nearest) {
        cout << "Nearest to (" << qx << "," << qy << ") is id=" << nearest->id
             << " at (" << nearest->x << "," << nearest->y << ")\n";
    }

    return 0;
}

Key Interfaces

  • QuadTree(Rect boundary, size_t capacity, unsigned maxDepth)
    • Construct a tree with a boundary, capacity (points/leaf), and max depth (stop subdividing).
  • bool insert(const Point& p)
    • Insert a point. Returns true if successful.
  • void queryRange(const Rect& range, vector& found)
    • Returns all points in range.
  • optional nearest(double x, double y)
    • Returns the single closest point, using bounding-rectangle pruning.
  • bool remove(const Point& p)
    • Remove a point if present. The implementation merges children if empty.
  • void clear()
    • Empty the tree.

Complexity

  • Average insertion: O(log n), but depends on capacity and distribution.
  • Worst-case insertion: O(n) in degenerate distributions where points fall in same quadrant until max depth.
  • Range query: O(k + log n) typically, where k is number of reported points.
  • Nearest neighbor: efficiency depends on how aggressively branches are pruned; often O(log n) expected.

Applications

  • Spatial indexing in games and simulations (collision detection).
  • GIS: store points, find nearby features.
  • Nearest-neighbor searches for approximate queries.
  • Image compression (region quadtrees).
  • Load balancing and adaptive mesh refinement.

Practical Tips and Enhancements

  • Use a dynamic capacity: small capacity for dense clusters, larger for sparse areas.
  • Implement removal and node merging carefully to avoid memory churn.
  • Add bulk-construction by inserting many points or creating balanced tree from points (faster than inserting one-by-one).
  • Add k-NN, radius search, or weighted searches.
  • For very large datasets, consider disk-backed or hierarchical LOD quadtrees.
  • For moving objects (game entities), avoid full deletion/insert each frame; group updates or lazy updates help.

Conclusion

Quadtrees are an essential spatial data structure to make geometric queries efficient. The implementation above provides robust basics for point insertion, range queries, nearest neighbor search, removal, and cleanup. Start with this foundation and extend it for your application’s specific needs — for example, storing rectangles instead of points, or adopting dynamic capacity, or adding concurrency-safe operations.