Quadtrees: 2D Spatial Partitioning and Accelerated Range Searching

In two-dimensional geometric applications—such as game collision detection, geospatial mapping (GIS), and physics simulations—querying objects within a specific geographic window or detecting overlapping pairs naively requires evaluating every object against every other object in O(N^2) time.

Invented by Raphael Finkel and J.L. Bentley in 1974, the Quadtree is a tree data structure that hierarchically decomposes a two-dimensional space by recursively subdividing regions into four quadrants (sub-grids). By pruning entire spatial quadrants that do not intersect a query region, Quadtrees reduce spatial search and collision detection complexity to O(log N).

Quadtree Taxonomy and Node Structure

A Quadtree node models an Axis-Aligned Bounding Box (AABB) defined by its center coordinate (x, y) and half-dimension bounds (halfWidth, halfHeight). Depending on how coordinates are partitioned, Quadtrees fall into two primary classifications:

• Point Quadtree: Similar to a 2D binary search tree where each inserted point acts as the exact coordinate center dividing the parent plane into four quadrants.
• Point-Region (PR) Quadtree: The bounding space is partitioned into four equal-sized quadrants regardless of where inserted points lie within the boundary. This structure avoids data skew based on insertion order and is standard in geospatial applications.
• Four Child Quadrants: Northwest (NW), Northeast (NE), Southwest (SW), and Southeast (SE).

Core Operations and Sub-Division Mechanics

1. Insertion and Automatic Sub-division

Each node maintains a fixed capacity threshold (e.g., 4 or 8 points). When a new 2D coordinate is inserted:

1. Check if the point lies within the node's bounding box; if not, reject immediately.
2. If the node has not reached its capacity and has no children, append the point to the node's local array.
3. If capacity is exceeded, subdivide the node into four child quadrants (NW, NE, SW, SE), migrate existing points into their respective child bounding boxes, and route the new point down to its quadrant.

2. Spatial Range Query (Window Query)

To locate all points residing within a target bounding box or circular radius:

1. If the node's bounding box does not intersect the search boundary, prune the subtree and return immediately.
2. Iterate over points stored in the current node and collect those falling inside the search boundary.
3. Recursively invoke the query across all four child sub-quadrants.

Average Time Complexity: O(log N + K), where K is the number of points reported in the target range.

Quadtree vs. Uniform Spatial Grid: Trade-Offs

• Adaptive Resolution: A uniform grid partitions space into fixed cell sizes, wasting memory on empty terrain and causing performance bottlenecks in densely clustered areas. Quadtrees adaptively subdivide only where object density is high.
• Memory Efficiency: Empty regions in a Quadtree remain unallocated leaf nodes rather than consuming fixed matrix memory slots.
• Dynamic Object Movement: Fast-moving objects in dynamic physics simulations require removing and reinserting nodes across quadrant boundaries, whereas flat spatial hashing grids can update dynamic object coordinates with lower constant overhead.

C++ Implementation Blueprint (PR Quadtree)

#include <vector>
#include <memory>

struct Point { double x, y; };

struct AABB {
    double cx, cy, hw, hh;
    bool contains(const Point& p) const {
        return (p.x >= cx - hw && p.x <= cx + hw && p.y >= cy - hh && p.y <= cy + hh);
    }
    bool intersects(const AABB& other) const {
        return !(other.cx - other.hw > cx + hw || other.cx + other.hw < cx - hw ||
                 other.cy - other.hh > cy + hh || other.cy + other.hh < cy - hh);
    }
};

class Quadtree {
private:
    static constexpr int CAPACITY = 4;
    AABB boundary;
    std::vector<Point> points;
    bool divided = false;
    std::unique_ptr<Quadtree> nw, ne, sw, se;

    void subdivide() {
        double hw = boundary.hw / 2, hh = boundary.hh / 2;
        nw = std::make_unique<Quadtree>(AABB{boundary.cx - hw, boundary.cy + hh, hw, hh});
        ne = std::make_unique<Quadtree>(AABB{boundary.cx + hw, boundary.cy + hh, hw, hh});
        sw = std::make_unique<Quadtree>(AABB{boundary.cx - hw, boundary.cy - hh, hw, hh});
        se = std::make_unique<Quadtree>(AABB{boundary.cx + hw, boundary.cy - hh, hw, hh});
        divided = true;
    }

public:
    Quadtree(AABB b) : boundary(b) {}

    bool insert(const Point& p) {
        if (!boundary.contains(p)) return false;
        if (points.size() < CAPACITY && !divided) {
            points.push_back(p);
            return true;
        }
        if (!divided) subdivide();
        return (nw->insert(p) || ne->insert(p) || sw->insert(p) || se->insert(p));
    }

    void queryRange(const AABB& range, std::vector<Point>& results) const {
        if (!boundary.intersects(range)) return;
        for (const auto& p : points) {
            if (range.contains(p)) results.push_back(p);
        }
        if (divided) {
            nw->queryRange(range, results);
            ne->queryRange(range, results);
            sw->queryRange(range, results);
            se->queryRange(range, results);
        }
    }
};

Real-World Engineering and Scientific Applications

1. Game Engine Broad-Phase Collision Detection: Pruning non-colliding entities across 2D map regions before executing computationally expensive pixel-perfect or SAT polygon narrow-phase intersection tests.
2. Geographic Information Systems (GIS) & Mapping Tiles: Hierarchical spatial partitioning used by OpenStreetMap and Google Maps to stream vector map tiles at varying zoom levels (LOD).
3. Image Compression (Quadtree Decomposition): Dividing 2D raster image matrices into homogeneous color blocks to compress redundant pixel regions.
4. Astrophysical N-Body Simulations (Barnes-Hut Algorithm): Approximating gravitational force calculations across clusters of celestial bodies by treating distant subtrees as single centers of mass, reducing complexity from O(N^2) to O(N log N).
5. 3D Extension (Octrees): Generalizing the 4-way 2D decomposition into an 8-way 3D spatial index for 3D point clouds, voxel rendering engines, and ray-tracing acceleration.