Introduction

Imagine dropping a million GPS pins on a map and then asking: "which pins are inside this rectangle?" The brute-force answer checks all one million. But real maps respond in milliseconds. The secret is a quadtree.

A quadtree is a tree in which every internal node represents a square region of 2-D space and has exactly four children — one for each quadrant: NW, NE, SW, SE. When a region contains too many points it gets subdivided, splitting into four smaller squares. Regions that are empty or sparse stay as leaves and are never touched during a search.

The result is a tree that mirrors the density of your data: crowded cities are represented by deep chains of tiny cells; empty oceans are a single leaf node. A spatial query descends only the branches that overlap the query region, skipping everything else.

Extending the idea to three dimensions gives an octree: each node splits a cube into eight sub-cubes (octants). The logic is identical; the branching factor doubles. Octrees are the workhorse of 3-D rendering, LiDAR point clouds, and physics engines.

Both structures trace back to Raphael Finkel and Jon Bentley (1974), who introduced the quad-tree for efficient 2-D range searching. They are now so ubiquitous that every major game engine, GIS platform, and graphics library ships them as a built-in primitive.

Build One Live

Click anywhere on the canvas to drop a point. The quadtree will subdivide that region as soon as it holds more than 4 points. Drag the orange query rectangle to highlight which cells the tree must visit — notice how it skips every cell that doesn't overlap.

<p class="hint">Click the canvas to drop points. The quadtree <b>subdivides</b> a cell when it holds more than 4 points. Drag the orange rectangle to run a range query and see which cells get searched (green = visited, rest = pruned).</p>
<canvas id="qt" width="380" height="320"></canvas>
<div class="info" id="info">0 points · 0 cells · drag the orange box to query</div>
<div class="btns">
  <button id="clear" type="button" class="ghost">Clear</button>
  <button id="rain" type="button">Drop 50 random points</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1.5px solid #cdd9e3; border-radius: 8px; cursor: crosshair;
         background: #f7fafc; touch-action: none; max-width: 100%; }
.info { font-size: .88rem; color: #555; margin: .5rem 0 .4rem; min-height: 1.3em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui,sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Quadtree demo — point insertion + range query with visual pruning feedback.
// The tree splits a node when it has > CAPACITY points and depth < MAX_DEPTH.
// A range query descends only branches that intersect the query rectangle.
const canvas = document.getElementById('qt');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const CAPACITY = 4;
const MAX_DEPTH = 8;

// --- Quadtree implementation ---
class QTNode {
  constructor(x, y, w, h, depth) {
    this.x = x; this.y = y; this.w = w; this.h = h; this.depth = depth;
    this.points = [];
    this.children = null; // null = leaf
  }
  subdivide() {
    const hw = this.w / 2, hh = this.h / 2, d = this.depth + 1;
    this.children = [
      new QTNode(this.x,      this.y,      hw, hh, d), // NW
      new QTNode(this.x + hw, this.y,      hw, hh, d), // NE
      new QTNode(this.x,      this.y + hh, hw, hh, d), // SW
      new QTNode(this.x + hw, this.y + hh, hw, hh, d), // SE
    ];
    // redistribute current points into children
    for (const p of this.points) this._insertIntoChildren(p);
    this.points = [];
  }
  _insertIntoChildren(p) {
    for (const c of this.children) {
      if (p.x >= c.x && p.x < c.x + c.w && p.y >= c.y && p.y < c.y + c.h) {
        c.insert(p); return;
      }
    }
    // Edge: point on right/bottom boundary falls in last child
    this.children[3].insert(p);
  }
  insert(p) {
    if (this.children) { this._insertIntoChildren(p); return; }
    this.points.push(p);
    if (this.points.length > CAPACITY && this.depth < MAX_DEPTH) this.subdivide();
  }
  // Returns {visited, matched} counts; draws visited cells green
  query(rx, ry, rw, rh, visited, matched) {
    // Does this node's box overlap the query rect?
    if (rx + rw <= this.x || rx >= this.x + this.w ||
        ry + rh <= this.y || ry >= this.y + this.h) return; // prune
    visited.count++;
    if (this.children) {
      for (const c of this.children) c.query(rx, ry, rw, rh, visited, matched);
    } else {
      // leaf — highlight it and count matching points
      ctx.fillStyle = 'rgba(0,160,80,0.18)';
      ctx.fillRect(this.x + 1, this.y + 1, this.w - 2, this.h - 2);
      for (const p of this.points) {
        if (p.x >= rx && p.x <= rx + rw && p.y >= ry && p.y <= ry + rh)
          matched.count++;
      }
    }
  }
  // Count total leaf nodes
  countCells() {
    if (!this.children) return 1;
    return this.children.reduce((s, c) => s + c.countCells(), 0);
  }
  // Draw all cell borders
  draw() {
    ctx.strokeStyle = '#b0c4d8';
    ctx.lineWidth = 0.8;
    ctx.strokeRect(this.x, this.y, this.w, this.h);
    if (this.children) for (const c of this.children) c.draw();
  }
  // Draw points
  drawPoints(highlight) {
    for (const p of this.points) {
      ctx.beginPath(); ctx.arc(p.x, p.y, 3.5, 0, Math.PI * 2);
      if (highlight && p.x >= highlight.rx && p.x <= highlight.rx + highlight.rw &&
          p.y >= highlight.ry && p.y <= highlight.ry + highlight.rh)
        ctx.fillStyle = '#e63946';
      else ctx.fillStyle = '#1d3557';
      ctx.fill();
    }
    if (this.children) for (const c of this.children) c.drawPoints(highlight);
  }
}

let root = new QTNode(0, 0, W, H, 0);
let points = [];

// --- Query rectangle (draggable) ---
let qr = { rx: 80, ry: 80, rw: 120, rh: 100 };
let drag = null; // { type:'move'|'resize', ox, oy }

function hitHandle(mx, my) {
  const ex = qr.rx + qr.rw, ey = qr.ry + qr.rh;
  if (Math.abs(mx - ex) < 10 && Math.abs(my - ey) < 10) return 'resize';
  if (mx >= qr.rx && mx <= ex && my >= qr.ry && my <= ey) return 'move';
  return null;
}

// --- Render ---
function render() {
  ctx.clearRect(0, 0, W, H);
  // Draw cells
  root.draw();
  // Query — highlight visited leaves (green fill drawn inside query())
  const vis = { count: 0 }, mat = { count: 0 };
  root.query(qr.rx, qr.ry, qr.rw, qr.rh, vis, mat);
  // Draw points (red if inside query rect)
  root.drawPoints({ rx: qr.rx, ry: qr.ry, rw: qr.rw, rh: qr.rh });
  // Draw query rect
  ctx.strokeStyle = '#e67e22'; ctx.lineWidth = 2;
  ctx.setLineDash([5, 3]);
  ctx.strokeRect(qr.rx, qr.ry, qr.rw, qr.rh);
  ctx.setLineDash([]);
  // Resize handle
  ctx.fillStyle = '#e67e22';
  ctx.fillRect(qr.rx + qr.rw - 5, qr.ry + qr.rh - 5, 10, 10);
  // Info
  const cells = root.countCells();
  document.getElementById('info').textContent =
    fmt('%length% %v% · %cells% %v2% · query visited %count% %v3%, found %count2% %v4%', { length: points.length, v: points.length !== 1 ? 'points' : 'point', cells: cells, v2: cells !== 1 ? 'cells' : 'cell', count: vis.count, v3: vis.count !== 1 ? 'cells' : 'cell', count2: mat.count, v4: mat.count !== 1 ? 'points' : 'point' });
}

// --- Events ---
function getPos(e) {
  const r = canvas.getBoundingClientRect();
  const sc = W / r.width;
  const cx = e.touches ? e.touches[0].clientX : e.clientX;
  const cy = e.touches ? e.touches[0].clientY : e.clientY;
  return { x: (cx - r.left) * sc, y: (cy - r.top) * sc };
}

canvas.addEventListener('mousedown', onDown);
canvas.addEventListener('touchstart', onDown, { passive: false });
function onDown(e) {
  e.preventDefault();
  const { x, y } = getPos(e);
  const h = hitHandle(x, y);
  if (h) { drag = { type: h, ox: x - qr.rx, oy: y - qr.ry, ex: x - (qr.rx + qr.rw), ey: y - (qr.ry + qr.rh) }; return; }
  // drop point
  const p = { x, y };
  points.push(p);
  root.insert(p);
  render();
}
window.addEventListener('mousemove', onMove);
window.addEventListener('touchmove', onMove, { passive: false });
function onMove(e) {
  if (!drag) return; e.preventDefault();
  const { x, y } = getPos(e);
  if (drag.type === 'move') {
    qr.rx = Math.max(0, Math.min(W - qr.rw, x - drag.ox));
    qr.ry = Math.max(0, Math.min(H - qr.rh, y - drag.oy));
  } else {
    qr.rw = Math.max(20, Math.min(W - qr.rx, x - drag.ex - qr.rx));
    qr.rh = Math.max(20, Math.min(H - qr.ry, y - drag.ey - qr.ry));
  }
  render();
}
window.addEventListener('mouseup', () => { drag = null; });
window.addEventListener('touchend', () => { drag = null; });

document.getElementById('clear').addEventListener('click', () => {
  root = new QTNode(0, 0, W, H, 0); points = []; render();
});
document.getElementById('rain').addEventListener('click', () => {
  for (let i = 0; i < 50; i++) {
    const p = { x: Math.random() * (W - 10) + 5, y: Math.random() * (H - 10) + 5 };
    points.push(p); root.insert(p);
  }
  render();
});

render();
Result
Console

The green cells are leaves the query touches; the rest are pruned entirely. With a uniform cloud of points you'll need O(log⁡n)O(\log n) cell visits for a small query — far fewer than the n points themselves. Cluster all your points in one corner and the tree grows deep there, staying flat everywhere else.

The Real Complexity

Quadtrees are a solved, efficient algorithm — no open-problem status here. Their complexity is well-understood:

  • Construction: inserting n points one by one costs O(nlog⁡n)O(n \log n) expected time on uniformly distributed data. Each insertion descends the tree in O(depth) time, and depth averages O(log⁡n)O(\log n).
  • Range query: given a rectangular query window, the tree visits only the cells that overlap it. On n uniformly distributed points, a window enclosing k points touches O(n+k)O(\sqrt{n} + k) leaf cells — dramatically less than n. In the worst case (adversarial clustering) depth can reach O(n)O(n) and the whole advantage disappears.
  • Depth guarantee: if the smallest pairwise distance between any two points is δ and the root spans a region of diameter D, the maximum depth is O(log(D/δ)) — depends on the spread of the data, not just its count.
  • Nearest-neighbor search: find the closest point to a query in O(log⁡n)O(\log n) expected time by pruning branches whose minimum distance to the query exceeds the current best.
  • Octrees share the same asymptotic bounds in 3-D; the branching factor 8 versus 4 adds only a constant.

The practical takeaway: quadtrees excel on spatially coherent, moderately clustered data. For highly skewed or adversarial point sets, a k-d tree or R-tree often performs better. For uniformly random data they are nearly optimal.

Where It Matters

The "divide space, skip the empties" idea turns up in an extraordinary range of fields:

  • Collision detection in games: every physics engine partitions the world into cells. Objects that occupy different cells can't collide — test only pairs that share a cell. Quadtrees (2-D) and octrees (3-D) cut the O(n2)O(n^{2}) naive check to near-linear for typical scenes.
  • Map tiles and GIS: web maps store geographic features in a quadtree so that a pan or zoom only fetches the relevant tiles. The famous Google Maps tile scheme is essentially a quadtree of the Earth.
  • Image compression: quadtree image coding recursively splits a region until each leaf is "uniform enough," storing one color per leaf instead of every pixel. The classic QTVQ (quadtree vector quantization) algorithm exploits this.
  • LiDAR and 3-D point clouds: autonomous vehicles collect hundreds of millions of 3-D points per second. Octrees index them so that object detection queries run in milliseconds rather than hours.
  • Mesh generation: finite-element solvers use quadtrees/octrees to generate adaptive meshes — fine cells where geometry is complex, coarse cells where it's flat.
  • Barnes-Hut galaxy simulation: the famous O(nlog⁡n)O(n \log n) gravity algorithm stores stars in an octree and approximates distant clusters as single masses, making million-body simulations tractable.

Any time you need to answer "what's near here?" efficiently, you're likely looking for a quadtree or its 3-D sibling. They are the unsung backbone of closest-pair algorithms and spatial reasoning everywhere.

Conclusion

Quadtrees and octrees embody one of the most powerful ideas in algorithm design: don't look where you don't have to. By mirroring the density of data in the structure of the tree, they convert hopeless O(n)O(n) spatial searches into efficient O(log⁡n)O(\log n) or O(n)O(\sqrt{n}) ones.

The construction is elegant, the guarantees are solid, and the applications span games, maps, robotics, graphics, and simulation. Every map you pan, every collision your game prevents, every LiDAR scan a self-driving car processes — there is a quadtree or an octree quietly doing the heavy lifting.

If you want to go deeper, look at how these structures relate to the closest-pair problem or how Barnes-Hut simulation turns the same idea into an O(nlog⁡n)O(n \log n) gravity solver. Recursive space subdivision is a lens that sharpens almost any spatial problem you point it at.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quadtree-octree/Content licensed under CC BY-NC 4.0.