Quadtrees

in reviewThis lesson is complete and being validated before release - details may still change.

Quadtree

Loading interactive demo…

A point quadtree over a field of seeded points. Each point is inserted in turn: the walk steps down from the root into the quadrant that holds the point until it reaches a leaf; a leaf with room stores it, and a full leaf splits into four quadrants first, handing its points down. Then a square range is queried: the search skips every node whose box misses the range and checks only the points stored in the boxes that touch it.Take the tour, or press and explore. Legend:

The panel beside the stage is the real Quadtree class from the published library executing in your browser, with the current line highlighted.

The node being walked, split, visited, or skipped, and the point being inserted or checked; the dashed square is the query range, with its handle.
The tree so far: every box the inserts have made, and the points stored.
Boxes the query found touching the range.
Boxes the query skipped, dashed; the faint boxes and points are the finished tree, still to come.
A point checked by the query.
A hit: a checked point inside the range.
A checked point outside the range: its box touched the range, it did not.

nodes counts the boxes made so far, depth how far down the deepest goes, checked how many points the query has looked at against the count brute force would, and hits how many it has found. Drag the square to query elsewhere.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A box that splits. A node of the tree owns a box and holds up to $c$ points, the capacity. Inserting a point walks down from the root: at a node with children, step into the quadrant the point falls in (east or west of the centre line, north or south); at a leaf with room, store it. A leaf already holding $c$ points splits first into four quadrants, each a box a quarter the size, and hands its points to the quadrants they fall in; then the walk goes on. A split can cascade: if every point lands in the same quadrant, that quadrant is full too and splits again.

Depth. Each level halves the box on both axes, so after $d$ levels a box is $2^{-d}$ of the field across. Points spread evenly reach a leaf in about $\log_4(n/c)$ steps, and the tree holds about $n/c$ leaves. Points that crowd go deeper where they crowd and nowhere else: that is the quadtree's whole point against a fixed grid. Set the spread to clustered and the open field stays a few big boxes while the clusters split to the depth cap. Two coincident points would split forever, so a leaf at the cap, depth $6$ here, never splits and simply holds more.

A range query. To find every point inside a range $R$ , start at the root and at each node test whether its box touches $R$ . A box that misses $R$ is skipped with everything beneath it; a box that touches it is searched: its stored points are checked one by one, then its children. Only points in boxes that touch $R$ are ever checked, so the work is the touching nodes plus the hits, far below the $n$ tests brute force makes, and the checked readout shows the gap. A box can touch $R$ while a point in it lies outside, so a checked point is not always a hit.

Against the spatial hash. The hash of the previous lesson sizes its cells once, by the query radius, and is unbeatable when the points are spread evenly and the radius is known: one hash per insert, a few cells per query. It suffers when the points pile into a few cells, where a query checks the whole pile, and when queries come in many sizes, where no one cell size fits. The tree pays a walk of $O(\log n)$ per insert and per leaf reached, and in return adapts to the points and answers a range of any size.

Boxes, not pairs. The tree here stores points. A tree of bodies with size stores each body in the deepest node whose box contains it whole, or, in the loose quadtree, in boxes grown by half so a body near a centre line still fits one node. Either way the query is the same walk.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Nodes live in one array and a node's children are four ids, allotted together when it splits, so a node id says which split made it and the stage can reveal the tree in order.
insert is one loop with two inner moves: walk down while the node has children, then either store or split. After a split the loop goes round again and the walk continues from the node that split, which is what makes a cascade fall out for free.
split redistributes silently: the points a full leaf hands down are moved without a trace event each, so a split is one event however many it moves, and moved says how many.
The centre lines go east and north: quadrant sends a point exactly on a centre line to the quadrant on the greater side, so no point is ever in two quadrants and none is in neither.
touches is closed, Rectangle.overlaps is open: a point on a node's edge belongs to that node and may be inside the range, so the search must not skip a box that only touches the range along an edge. The shared overlaps ignores edge contact, which is right for rooms and wrong here.
maxDepth is the guard against points that coincide after rounding: a leaf at the cap holds any number, so the loop always ends.

Raphael Finkel and Jon Bentley described the quadtree in 1974, in a paper on retrieving records by composite keys: a point in the plane is a two-part key, and a binary search tree generalises to a tree whose every node splits the plane into four. The year after, Bentley published the k-d tree, which splits one axis at a time instead, and the two became the standard ways to index points in space. Hanan Samet's 1984 survey gathered the variants, region quadtrees over images among them, and made the quadtree the common vocabulary of spatial data structures in graphics, maps, and games.

1974Raphael Finkel and Jon Bentley - Publish 'Quad Trees: A Data Structure for Retrieval on Composite Keys' in Acta Informatica, the point quadtree.source
1975Jon Bentley - Publishes the k-d tree in Communications of the ACM, splitting one coordinate at a time instead of all at once.source
1984Hanan Samet - Surveys 'The Quadtree and Related Hierarchical Data Structures' in ACM Computing Surveys, collecting point, region, and edge quadtrees and the octree.source
1986Josh Barnes and Piet Hut - Publish the Barnes-Hut simulation in Nature: an octree over the bodies of an N-body problem lets distant clusters be treated as one mass, cutting the work from quadratic to n log n.source

Used today

Collision broad phase - A game inserts its bodies into a quadtree each frame and asks each body for the ones in its box, so only nearby pairs reach the narrow phase.
Image regions - A region quadtree splits a picture until each box is one colour; uniform areas stay one leaf, which is a compression and a fast way to find edges.
Maps and GIS - Geographic systems index points and tiles with quadtrees; map tile schemes are quadtrees over the globe, each zoom level one depth down.
N-body simulation - Barnes-Hut and its kin sum gravity or charge over an octree, treating far-away leaves as single bodies.

points32

capacity4

spread

range6

nodes: 25
depth: 3
checked: 3 of 32
hits: 1

quadtree.ts

import { Rectangle, type Point } from "../navigation/geometry";import type { Tracer } from "../trace";/** The four quadrants of a node, by index: the x bit is 1 for east, the y bit is 2 for north (y up). */export const QUADTREE_QUADRANTS = ["sw", "se", "nw", "ne"] as const;export type Quadrant = (typeof QUADTREE_QUADRANTS)[number];export interface QuadtreeOptions {  /** How many points a leaf holds before it splits. */  capacity: number;  /** A leaf this deep never splits, so coincident points have somewhere to live (default 8). */  maxDepth?: number;}/** A node of the tree: its box, the points it stores (indices into the tree's points), and its four children once split. */export interface QuadNode {  readonly id: number;  readonly depth: number;  readonly parent: number;  readonly bounds: Rectangle;  readonly points: readonly number[];  /** The children by quadrant index, or null while the node is a leaf. */  readonly children: readonly [number, number, number, number] | null;}interface MutableNode {  id: number;  depth: number;  parent: number;  bounds: Rectangle;  points: number[];  children: [number, number, number, number] | null;}/** * A point quadtree: a box that holds a few points, and splits into * four quadrants when it holds one too many, each quadrant a box that * does the same. Inserting a point walks down from the root to the * leaf whose box holds it; a leaf that is full splits first, handing * its points to the quadrants they fall in, and the walk goes on. * Querying a range walks the same tree, but skips every node whose * box misses the range, so only the points in nearby leaves are ever * checked. Where a spatial hash sizes its cells once, the tree sizes * them as the points demand: dense where the points crowd, coarse * where they are sparse. * * Time: O(log n) to insert or to reach one leaf on well-spread points, * O(k + visited nodes) for a query returning k points; the depth cap * keeps coincident points from splitting forever. */export class Quadtree {  private readonly tree: MutableNode[] = [];  private readonly stored: Point[] = [];  readonly capacity: number;  readonly maxDepth: number;  constructor(    readonly bounds: Rectangle,    options: QuadtreeOptions,    private readonly tracer?: Tracer,  ) {    if (!Number.isInteger(options.capacity) || options.capacity < 1) throw new RangeError(`capacity must be a positive integer, got ${options.capacity}`);    const maxDepth = options.maxDepth ?? 8;    if (!Number.isInteger(maxDepth) || maxDepth < 1) throw new RangeError(`maxDepth must be a positive integer, got ${maxDepth}`);    this.capacity = options.capacity;    this.maxDepth = maxDepth;    this.tree.push({ id: 0, depth: 0, parent: -1, bounds, points: [], children: null });  }  /** The nodes in the order they were made: the root first, each split's four children together. */  get nodes(): readonly QuadNode[] {    return this.tree;  }  /** The points inserted so far, in order. */  get points(): readonly Point[] {    return this.stored;  }  /** How deep the tree goes, the root being depth 0. */  get depth(): number {    return this.tree.reduce((deepest, node) => Math.max(deepest, node.depth), 0);  }  /** Which quadrant of a box a point falls in: on the centre lines it goes east and north. */  static quadrant(bounds: Rectangle, p: Point): number {    const { x, y } = bounds.centroid;    return (p.x >= x ? 1 : 0) + (p.y >= y ? 2 : 0);  }  /** The box of one quadrant of a node's box. */  static quadrantBounds(bounds: Rectangle, q: number): Rectangle {  static quadrantBounds(bounds: Rectangle, quadrantIndex: number): Rectangle {    const w = bounds.width / 2;    const h = bounds.height / 2;    return new Rectangle(bounds.x + (q & 1 ? w : 0), bounds.y + (q & 2 ? h : 0), w, h);    return new Rectangle(bounds.x + (quadrantIndex & 1 ? w : 0), bounds.y + (quadrantIndex & 2 ? h : 0), w, h);  }  /** Every point inside the range, by index, checking them all: what the tree saves. */  static bruteForce(points: readonly Point[], range: Rectangle): number[] {    const hits: number[] = [];    points.forEach((p, i) => {      if (range.contains(p)) hits.push(i);    });    return hits;  }  /** Inserts a point and returns the index it is stored under; a point outside the root's box is refused. */  insert(point: Point): number {    if (!Number.isFinite(point.x) || !Number.isFinite(point.y)) throw new RangeError("a point needs finite coordinates");    if (!this.bounds.contains(point)) throw new RangeError(`(${point.x}, ${point.y}) lies outside the tree's box`);    const idx = this.stored.length;    const pointIndex = this.stored.length;    this.stored.push({ x: point.x, y: point.y });    let node = this.tree[0]!;    for (;;) {      while (node.children) {        const q = Quadtree.quadrant(node.bounds, point);        const quadrantIndex = Quadtree.quadrant(node.bounds, point);        const child = this.tree[node.children[q]!]!;        const child = this.tree[node.children[quadrantIndex]!]!;        // ▸ the node has children: step into the quadrant the point falls in        this.tracer?.emit("descend", { point: idx, from: node.id, to: child.id, depth: child.depth, quadrant: QUADTREE_QUADRANTS[q] });        this.tracer?.emit("descend", { point: pointIndex, from: node.id, to: child.id, depth: child.depth, quadrant: QUADTREE_QUADRANTS[quadrantIndex] });        node = child;      }      if (node.points.length < this.capacity || node.depth >= this.maxDepth) {        node.points.push(idx);        node.points.push(pointIndex);        // ▸ a leaf with room, or one at the depth cap: the point lives here        this.tracer?.emit("store", { point: idx, node: node.id, depth: node.depth, count: node.points.length });        this.tracer?.emit("store", { point: pointIndex, node: node.id, depth: node.depth, count: node.points.length });        return idx;        return pointIndex;      }      this.split(node);    }  }  /** Every stored point inside the range, by index, visiting only the nodes whose box overlaps it. */  query(range: Rectangle): number[] {    const hits: number[] = [];    this.search(this.tree[0]!, range, hits);    return hits;  }  /** A full leaf becomes four quadrants, each taking the points that fall in it. */  private split(node: MutableNode): void {    const kids: number[] = [];    const childIds: number[] = [];    for (let q = 0; q < 4; q++) {    for (let quadrantIndex = 0; quadrantIndex < 4; quadrantIndex++) {      const id = this.tree.length;      kids.push(id);      childIds.push(id);      this.tree.push({ id, depth: node.depth + 1, parent: node.id, bounds: Quadtree.quadrantBounds(node.bounds, q), points: [], children: null });      this.tree.push({ id, depth: node.depth + 1, parent: node.id, bounds: Quadtree.quadrantBounds(node.bounds, quadrantIndex), points: [], children: null });    }    const children: [number, number, number, number] = [kids[0]!, kids[1]!, kids[2]!, kids[3]!];    const children: [number, number, number, number] = [childIds[0]!, childIds[1]!, childIds[2]!, childIds[3]!];    for (const idx of node.points) {    for (const pointIndex of node.points) {      const q = Quadtree.quadrant(node.bounds, this.stored[idx]!);      const quadrantIndex = Quadtree.quadrant(node.bounds, this.stored[pointIndex]!);      this.tree[children[q]!]!.points.push(idx);      this.tree[children[quadrantIndex]!]!.points.push(pointIndex);    }    const moved = node.points.length;    node.points = [];    node.children = children;    // ▸ a full leaf becomes four quadrants, each taking the points that fall in it    this.tracer?.emit("split", { node: node.id, depth: node.depth, children, moved });  }  /** Whether two boxes share any point, edges included: a point on a node's edge is in that node and may be in the range. */  static touches(a: Rectangle, b: Rectangle): boolean {    return a.x <= b.right && b.x <= a.right && a.y <= b.top && b.y <= a.top;  }  private search(node: MutableNode, range: Rectangle, hits: number[]): void {    if (!Quadtree.touches(node.bounds, range)) {      // ▸ the node's box misses the range: nothing in it can be a hit      this.tracer?.emit("skip", { node: node.id, depth: node.depth });      return;    }    // ▸ the box touches the range: look at what is stored here, then at the children    this.tracer?.emit("visit", { node: node.id, depth: node.depth, leaf: node.children === null, points: node.points.length });    for (const idx of node.points) {    for (const pointIndex of node.points) {      const p = this.stored[idx]!;      const p = this.stored[pointIndex]!;      const inside = range.contains(p);      // ▸ a point in a touching box: is it actually inside the range?      this.tracer?.emit("candidate", { point: idx, node: node.id, x: p.x, y: p.y, inside });      this.tracer?.emit("candidate", { point: pointIndex, node: node.id, x: p.x, y: p.y, inside });      if (!inside) continue;      hits.push(idx);      hits.push(pointIndex);      // ▸ it is: one more hit      this.tracer?.emit("hit", { point: idx, x: p.x, y: p.y, hits: hits.length });      this.tracer?.emit("hit", { point: pointIndex, x: p.x, y: p.y, hits: hits.length });    }    if (node.children) for (const id of node.children) this.search(this.tree[id]!, range, hits);  }}

nodes =: 25
depth =: 3
checked =: 3 of 32
hits =: 1

Done: 25 nodes to depth 3; the query checked 3 of 32 points and found 1 hit. Brute force would have checked all 32.

import { Rectangle, type Point } from "../navigation/geometry";import type { Tracer } from "../trace";/** The four quadrants of a node, by index: the x bit is 1 for east, the y bit is 2 for north (y up). */export const QUADTREE_QUADRANTS = ["sw", "se", "nw", "ne"] as const;export type Quadrant = (typeof QUADTREE_QUADRANTS)[number];export interface QuadtreeOptions { /** How many points a leaf holds before it splits. */ capacity: number; /** A leaf this deep never splits, so coincident points have somewhere to live (default 8). */ maxDepth?: number;}/** A node of the tree: its box, the points it stores (indices into the tree's points), and its four children once split. */export interface QuadNode { readonly id: number; readonly depth: number; readonly parent: number; readonly bounds: Rectangle; readonly points: readonly number[]; /** The children by quadrant index, or null while the node is a leaf. */ readonly children: readonly [number, number, number, number] | null;}interface MutableNode { id: number; depth: number; parent: number; bounds: Rectangle; points: number[]; children: [number, number, number, number] | null;}/** * A point quadtree: a box that holds a few points, and splits into * four quadrants when it holds one too many, each quadrant a box that * does the same. Inserting a point walks down from the root to the * leaf whose box holds it; a leaf that is full splits first, handing * its points to the quadrants they fall in, and the walk goes on. * Querying a range walks the same tree, but skips every node whose * box misses the range, so only the points in nearby leaves are ever * checked. Where a spatial hash sizes its cells once, the tree sizes * them as the points demand: dense where the points crowd, coarse * where they are sparse. * * Time: O(log n) to insert or to reach one leaf on well-spread points, * O(k + visited nodes) for a query returning k points; the depth cap * keeps coincident points from splitting forever. */export class Quadtree { private readonly tree: MutableNode[] = []; private readonly stored: Point[] = []; readonly capacity: number; readonly maxDepth: number; constructor( readonly bounds: Rectangle, options: QuadtreeOptions, private readonly tracer?: Tracer, ) { if (!Number.isInteger(options.capacity) || options.capacity < 1) throw new RangeError(`capacity must be a positive integer, got ${options.capacity}`); const maxDepth = options.maxDepth ?? 8; if (!Number.isInteger(maxDepth) || maxDepth < 1) throw new RangeError(`maxDepth must be a positive integer, got ${maxDepth}`); this.capacity = options.capacity; this.maxDepth = maxDepth; this.tree.push({ id: 0, depth: 0, parent: -1, bounds, points: [], children: null }); } /** The nodes in the order they were made: the root first, each split's four children together. */ get nodes(): readonly QuadNode[] { return this.tree; } /** The points inserted so far, in order. */ get points(): readonly Point[] { return this.stored; } /** How deep the tree goes, the root being depth 0. */ get depth(): number { return this.tree.reduce((deepest, node) => Math.max(deepest, node.depth), 0); } /** Which quadrant of a box a point falls in: on the centre lines it goes east and north. */ static quadrant(bounds: Rectangle, p: Point): number { const { x, y } = bounds.centroid; return (p.x >= x ? 1 : 0) + (p.y >= y ? 2 : 0); } /** The box of one quadrant of a node's box. */ static quadrantBounds(bounds: Rectangle, q: number): Rectangle { static quadrantBounds(bounds: Rectangle, quadrantIndex: number): Rectangle { const w = bounds.width / 2; const h = bounds.height / 2; return new Rectangle(bounds.x + (q & 1 ? w : 0), bounds.y + (q & 2 ? h : 0), w, h); return new Rectangle(bounds.x + (quadrantIndex & 1 ? w : 0), bounds.y + (quadrantIndex & 2 ? h : 0), w, h); } /** Every point inside the range, by index, checking them all: what the tree saves. */ static bruteForce(points: readonly Point[], range: Rectangle): number[] { const hits: number[] = []; points.forEach((p, i) => { if (range.contains(p)) hits.push(i); }); return hits; } /** Inserts a point and returns the index it is stored under; a point outside the root's box is refused. */ insert(point: Point): number { if (!Number.isFinite(point.x) || !Number.isFinite(point.y)) throw new RangeError("a point needs finite coordinates"); if (!this.bounds.contains(point)) throw new RangeError(`(${point.x}, ${point.y}) lies outside the tree's box`); const idx = this.stored.length; const pointIndex = this.stored.length; this.stored.push({ x: point.x, y: point.y }); let node = this.tree[0]!; for (;;) { while (node.children) { const q = Quadtree.quadrant(node.bounds, point); const quadrantIndex = Quadtree.quadrant(node.bounds, point); const child = this.tree[node.children[q]!]!; const child = this.tree[node.children[quadrantIndex]!]!; // ▸ the node has children: step into the quadrant the point falls in this.tracer?.emit("descend", { point: idx, from: node.id, to: child.id, depth: child.depth, quadrant: QUADTREE_QUADRANTS[q] }); this.tracer?.emit("descend", { point: pointIndex, from: node.id, to: child.id, depth: child.depth, quadrant: QUADTREE_QUADRANTS[quadrantIndex] }); node = child; } if (node.points.length < this.capacity || node.depth >= this.maxDepth) { node.points.push(idx); node.points.push(pointIndex); // ▸ a leaf with room, or one at the depth cap: the point lives here this.tracer?.emit("store", { point: idx, node: node.id, depth: node.depth, count: node.points.length }); this.tracer?.emit("store", { point: pointIndex, node: node.id, depth: node.depth, count: node.points.length }); return idx; return pointIndex; } this.split(node); } } /** Every stored point inside the range, by index, visiting only the nodes whose box overlaps it. */ query(range: Rectangle): number[] { const hits: number[] = []; this.search(this.tree[0]!, range, hits); return hits; } /** A full leaf becomes four quadrants, each taking the points that fall in it. */ private split(node: MutableNode): void { const kids: number[] = []; const childIds: number[] = []; for (let q = 0; q < 4; q++) { for (let quadrantIndex = 0; quadrantIndex < 4; quadrantIndex++) { const id = this.tree.length; kids.push(id); childIds.push(id); this.tree.push({ id, depth: node.depth + 1, parent: node.id, bounds: Quadtree.quadrantBounds(node.bounds, q), points: [], children: null }); this.tree.push({ id, depth: node.depth + 1, parent: node.id, bounds: Quadtree.quadrantBounds(node.bounds, quadrantIndex), points: [], children: null }); } const children: [number, number, number, number] = [kids[0]!, kids[1]!, kids[2]!, kids[3]!]; const children: [number, number, number, number] = [childIds[0]!, childIds[1]!, childIds[2]!, childIds[3]!]; for (const idx of node.points) { for (const pointIndex of node.points) { const q = Quadtree.quadrant(node.bounds, this.stored[idx]!); const quadrantIndex = Quadtree.quadrant(node.bounds, this.stored[pointIndex]!); this.tree[children[q]!]!.points.push(idx); this.tree[children[quadrantIndex]!]!.points.push(pointIndex); } const moved = node.points.length; node.points = []; node.children = children; // ▸ a full leaf becomes four quadrants, each taking the points that fall in it this.tracer?.emit("split", { node: node.id, depth: node.depth, children, moved }); } /** Whether two boxes share any point, edges included: a point on a node's edge is in that node and may be in the range. */ static touches(a: Rectangle, b: Rectangle): boolean { return a.x <= b.right && b.x <= a.right && a.y <= b.top && b.y <= a.top; } private search(node: MutableNode, range: Rectangle, hits: number[]): void { if (!Quadtree.touches(node.bounds, range)) { // ▸ the node's box misses the range: nothing in it can be a hit this.tracer?.emit("skip", { node: node.id, depth: node.depth }); return; } // ▸ the box touches the range: look at what is stored here, then at the children this.tracer?.emit("visit", { node: node.id, depth: node.depth, leaf: node.children === null, points: node.points.length }); for (const idx of node.points) { for (const pointIndex of node.points) { const p = this.stored[idx]!; const p = this.stored[pointIndex]!; const inside = range.contains(p); // ▸ a point in a touching box: is it actually inside the range? this.tracer?.emit("candidate", { point: idx, node: node.id, x: p.x, y: p.y, inside }); this.tracer?.emit("candidate", { point: pointIndex, node: node.id, x: p.x, y: p.y, inside }); if (!inside) continue; hits.push(idx); hits.push(pointIndex); // ▸ it is: one more hit this.tracer?.emit("hit", { point: idx, x: p.x, y: p.y, hits: hits.length }); this.tracer?.emit("hit", { point: pointIndex, x: p.x, y: p.y, hits: hits.length }); } if (node.children) for (const id of node.children) this.search(this.tree[id]!, range, hits); }}