The Quadtree: How to Search a Plane Without Looking at Every Point

The problem with a flat list of points

Ask "which of these ten thousand points lie inside this small box" and a plain array forces you to check every single point — O(n) per query, no matter how small the box is or how empty the rest of the plane happens to be. A quadtree, introduced by Raphael Finkel and J. L. Bentley in 1974, fixes this by organising space itself, not just the points in it, so that whole empty regions can be skipped without ever being visited.

Split into four when a node gets crowded

A quadtree node covers a square region of the plane and holds points up to some small capacity, typically 4 to 16. The moment a node would exceed that capacity, it splits into exactly four equal children — NW, NE, SW, SE — and its points are redistributed among them by which quadrant they fall in. The name comes directly from that four-way split; the analogous structure in three dimensions, splitting a cube into eight children, is an octree.

insert(node, point):
    if node has no children and node.points.length < capacity:
        node.points.push(point); return
    if node has no children:
        subdivide(node)          // create NW, NE, SW, SE, redistribute
    insert(child that contains point, point)

The tree ends up deep where points are dense and shallow where they are sparse — it adapts automatically to the data, unlike a fixed grid that wastes memory on empty cells or crams too many points into one bucket wherever the data happens to cluster.

Why a range query skips most of the tree

To find every point inside a query rectangle, walk the tree from the root and, at each node, compare the node's square against the query rectangle before descending: if the two do not overlap at all, the entire subtree is discarded in one comparison, however many points it holds. If the node's square is fully contained in the query, every point below it is collected without further checks. Only nodes that partially overlap the query need to recurse into their children.

query(node, rect, out):
    if !intersects(node.bounds, rect): return          // prune the whole subtree
    for p in node.points: if rect.contains(p): out.push(p)
    if node has children:
        for child in [NW, NE, SW, SE]: query(child, rect, out)

For a roughly balanced tree over n points, a small range query touches about O(log n + k) nodes, where k is the number of results returned — a dramatic improvement over scanning all n points once n reaches the thousands. Nearest-neighbour search uses the same pruning idea in reverse: expand outward from the query point node by node, and stop exploring a subtree as soon as its bounding square is provably farther than the best candidate found so far.

Where quadtrees actually earn their keep

Game and physics engines use quadtrees for broad-phase collision detection: instead of testing every pair of the n moving objects against each other (O(n²)), each object only needs to be checked against the handful of other objects sharing its node or a neighbouring one. The Barnes-Hut algorithm builds a fresh quadtree every simulation step to approximate long-range gravitational or electrostatic forces in O(n log n). Map and image tile servers use a quadtree of tile indices to decide which square of imagery to fetch at which zoom level, and geographic databases use it to answer "what's nearby" queries over millions of records without a full table scan.

The trade-off: rebuilding versus updating

Quadtrees are cheap to build — O(n log n) for n points inserted one at a time — but keeping one correct as points move is where implementations differ. Removing and reinserting a moving point every frame is simple and often fast enough; a more careful implementation merges a node's children back together when their combined point count drops below capacity, keeping the tree from staying needlessly deep after objects disperse. For workloads dominated by moving points rather than moving queries, some engines simply rebuild the whole tree from scratch every frame — at O(n log n) per rebuild it is frequently cheaper than the bookkeeping needed for incremental updates.

Frequently asked questions

Try it live

Everything above runs in your browser — open Quadtree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.