Quadtree

How a quadtree works

Imagine a square map with 10,000 ships scattered across it, and you want to know which ships are within 50 km of New York. Without spatial indexing, you compare your query point to every single ship — 10,000 distance calculations. A quadtree organizes the same data so you only check ships in the same neighborhood as your query, reducing the work to roughly the logarithm of the total.

The recursive idea is dead simple. Start with one big square covering all the data. If it contains more points than some small threshold (say, 4), split it into four equal sub-squares and reassign each point to whichever child it lands in. Recurse on each child that's still over the threshold. Empty regions stop subdividing immediately, so dense areas get fine-grained cells and sparse areas stay coarse.

Two operations dominate:

1. Insert(point). Descend from the root, picking the child whose region contains the point. If the leaf is over capacity, subdivide it and redistribute. O(log n) expected.
2. Range query (rectangle). Recursively visit any node whose region intersects the query rectangle. Skip the rest entirely. O(log n + k) where k is the number of points returned.

For collision broad-phase, you also do k-nearest neighbors (start at the leaf containing your query point, expand outward) and pair-overlap (for each leaf, test pairs of points in it and pairs spanning sibling leaves).

When to use a quadtree

• 2D game collision broad-phase. Bullet-hell shooters, tile-based games, top-down RPGs. The quadtree filters out 99% of pair tests; an O(n²) algorithm at 5,000 entities does 12.5M tests/frame and crushes a 60 Hz budget.
• GIS range queries. "Find every point of interest in this map viewport" — the rectangular region query is exactly what quadtrees were designed for.
• Image compression. Region quadtrees on binary images store only the largest uniform blocks, getting strong compression on documents and screenshots before any further encoding.
• Mesh refinement. Adaptive numerical grids (FEM, fluid simulation) refine where curvature is high and stay coarse elsewhere — that's a quadtree by another name.
• Fractal terrain LOD. Render a planet by storing terrain tiles in a quadtree and only recursing where the camera is close.

Quadtree vs grid vs k-d tree

	Quadtree	Uniform grid	k-d tree (2D)	R-tree
Insert	O(log n)	O(1)	O(log n)	O(log n)
Range query	O(log n + k)	O(cells in range + k)	O(√n + k)	O(log n + k)
Adapts to point density	Yes — auto-refines	No — fixed cell size	Yes — splits at median	Yes — node MBR
Memory	O(n) typical, O(n log n) clustered	O(W·H) regardless of n	O(n)	O(n)
Update on move	Re-insert (rare subdivide)	O(1) bucket swap	Hard — usually rebuild	Rebalances
Best for	Sparse points, varied density	Uniform density, fixed scale	Static point sets, NN search	Bounding boxes, GIS
Worst case	O(n) on clustered points	One bucket gets all items	O(n) on adversarial inserts	Heavily-overlapping MBRs

Practical rule: if your points are roughly uniform and dynamic (lots of moves per frame), use a uniform grid — O(1) updates beat O(log n) every time. If they cluster wildly or you need adaptive precision, use a quadtree. For static data with nearest-neighbor queries, prefer a k-d tree.

JavaScript implementation — collision broad-phase

This is the canonical "PR quadtree" used in games — points stored in leaves, capacity threshold triggers subdivision. The candidatePairs() method is the broad-phase that turns O(n²) into roughly O(n log n).

class Quadtree {
  constructor(bounds, capacity = 4, depth = 0, maxDepth = 8) {
    this.bounds = bounds;          // {x, y, w, h}
    this.capacity = capacity;
    this.depth = depth;
    this.maxDepth = maxDepth;
    this.points = [];              // populated only in leaves
    this.children = null;          // [NW, NE, SW, SE] when subdivided
  }

  contains(p) {
    const b = this.bounds;
    return p.x >= b.x && p.x < b.x + b.w &&
           p.y >= b.y && p.y < b.y + b.h;
  }

  intersects(rect) {
    const b = this.bounds;
    return !(rect.x > b.x + b.w || rect.x + rect.w < b.x ||
             rect.y > b.y + b.h || rect.y + rect.h < b.y);
  }

  subdivide() {
    const { x, y, w, h } = this.bounds;
    const hw = w / 2, hh = h / 2;
    this.children = [
      new Quadtree({ x,      y,      w: hw, h: hh }, this.capacity, this.depth + 1, this.maxDepth),
      new Quadtree({ x: x+hw, y,      w: hw, h: hh }, this.capacity, this.depth + 1, this.maxDepth),
      new Quadtree({ x,      y: y+hh, w: hw, h: hh }, this.capacity, this.depth + 1, this.maxDepth),
      new Quadtree({ x: x+hw, y: y+hh, w: hw, h: hh }, this.capacity, this.depth + 1, this.maxDepth),
    ];
    for (const p of this.points) {
      for (const c of this.children) if (c.contains(p)) { c.insert(p); break; }
    }
    this.points = null;  // internal node — no points stored here
  }

  insert(p) {
    if (!this.contains(p)) return false;
    if (this.children) {
      for (const c of this.children) if (c.insert(p)) return true;
      return false;
    }
    if (this.points.length < this.capacity || this.depth >= this.maxDepth) {
      this.points.push(p);
      return true;
    }
    this.subdivide();
    return this.insert(p);
  }

  query(rect, found = []) {
    if (!this.intersects(rect)) return found;
    if (this.children) {
      for (const c of this.children) c.query(rect, found);
    } else {
      for (const p of this.points) {
        if (p.x >= rect.x && p.x < rect.x + rect.w &&
            p.y >= rect.y && p.y < rect.y + rect.h) found.push(p);
      }
    }
    return found;
  }

  // Collision broad-phase: yield candidate pairs without doing O(n²).
  *candidatePairs() {
    if (this.children) {
      for (const c of this.children) yield* c.candidatePairs();
    } else {
      for (let i = 0; i < this.points.length; i++)
        for (let j = i + 1; j < this.points.length; j++)
          yield [this.points[i], this.points[j]];
    }
  }
}

// Usage in a 60 Hz game loop:
const tree = new Quadtree({ x: 0, y: 0, w: 1024, h: 1024 });
for (const e of entities) tree.insert(e);
for (const [a, b] of tree.candidatePairs()) {
  if (overlap(a, b)) resolveCollision(a, b);
}

Note that candidatePairs only yields pairs in the same leaf — entities straddling a boundary need a wider AABB query. In production you'd insert each entity's bounding rectangle into every leaf it overlaps, or maintain a separate "loose" quadtree where children extend beyond their parent bounds.

Python implementation

class Quadtree:
    def __init__(self, bounds, capacity=4, depth=0, max_depth=8):
        self.bounds = bounds                     # (x, y, w, h)
        self.capacity = capacity
        self.depth = depth
        self.max_depth = max_depth
        self.points = []
        self.children = None

    def contains(self, p):
        x, y, w, h = self.bounds
        return x <= p[0] < x + w and y <= p[1] < y + h

    def intersects(self, rect):
        x, y, w, h = self.bounds
        rx, ry, rw, rh = rect
        return not (rx > x + w or rx + rw < x or ry > y + h or ry + rh < y)

    def subdivide(self):
        x, y, w, h = self.bounds
        hw, hh = w / 2, h / 2
        d = self.depth + 1
        self.children = [
            Quadtree((x,      y,      hw, hh), self.capacity, d, self.max_depth),
            Quadtree((x + hw, y,      hw, hh), self.capacity, d, self.max_depth),
            Quadtree((x,      y + hh, hw, hh), self.capacity, d, self.max_depth),
            Quadtree((x + hw, y + hh, hw, hh), self.capacity, d, self.max_depth),
        ]
        for p in self.points:
            for c in self.children:
                if c.contains(p):
                    c.insert(p)
                    break
        self.points = None

    def insert(self, p):
        if not self.contains(p):
            return False
        if self.children is not None:
            return any(c.insert(p) for c in self.children)
        if len(self.points) < self.capacity or self.depth >= self.max_depth:
            self.points.append(p)
            return True
        self.subdivide()
        return self.insert(p)

    def query(self, rect, found=None):
        if found is None:
            found = []
        if not self.intersects(rect):
            return found
        if self.children is not None:
            for c in self.children:
                c.query(rect, found)
        else:
            rx, ry, rw, rh = rect
            for p in self.points:
                if rx <= p[0] < rx + rw and ry <= p[1] < ry + rh:
                    found.append(p)
        return found

    def candidate_pairs(self):
        if self.children is not None:
            for c in self.children:
                yield from c.candidate_pairs()
        else:
            for i in range(len(self.points)):
                for j in range(i + 1, len(self.points)):
                    yield self.points[i], self.points[j]

Variants

• Region quadtree. Stores binary or palette image data. Each leaf is a uniform color block. Compressing a 1024×1024 black-and-white scan can drop from 1 MB to a few KB.
• Point-region (PR) quadtree. The flavor used above — partition space by geometry, store points in leaves with a capacity threshold. The most common general-purpose form.
• MX quadtree. "Matrix" quadtree — recursion bottoms out at a fixed pixel grid, and points snap to grid cells. Ideal when coordinates are inherently discrete.
• Loose quadtree. Each child's region extends beyond its parent's strict quadrant by a slack factor. Eliminates the "object straddles a boundary" pathology that hurts collision broad-phase.
• Compressed quadtree. Skip nodes with only one non-empty child by chaining branches. Cuts memory roughly in half on sparse point sets without changing query complexity.
• Linear quadtree. Encode each leaf with a Morton-order (Z-order) key and store the leaves in a sorted array or B-tree. Plays well with disk-based GIS, since neighbors in Morton order are usually neighbors in space.

Common bugs and edge cases

• Pathological clustering. A thousand identical points trigger infinite subdivision; the recursion only stops because of the maxDepth cap, after which the leaf becomes a long linear list. Always cap depth.
• Floating-point boundary glitches. When points sit exactly on a quadrant boundary, choose a single tiebreak rule (e.g., < on the low edges and <= on the high) and use it everywhere. Mismatched rules drop points silently.
• Inserting bounding boxes as if they were points. A 50×50 sprite that straddles the centerline lives in two children, not one. Either pick one home and accept missed collisions across the seam, insert it into all overlapping children, or use a loose quadtree.
• Static rebuild every frame. Cheap when n is small, ruinous at n = 100,000. For dynamic scenes, prefer a uniform grid or a tree that supports targeted updates.
• Forgetting to clear points on subdivide. Internal nodes that still hold their original points double-count during queries. After subdividing, redistribute and null out the parent's array.
• Coordinate system drift. If your world wraps (toroidal map) or extends past the initial bounds, points outside this.bounds are silently dropped. Always validate before insert and resize the root if needed.