Quadtree
debt(d7/e5/b5/t5)
Closest to 'only careful code review or runtime testing' (d7), because detection_hints.automated is no — you notice the missing quadtree via profiling O(n^2) spatial loops or code review spotting nested pairwise intersect/distance checks. No linter flags this.
Closest to 'touches multiple files / significant refactor in one component' (e5), because introducing a quadtree per quick_fix means adding the structure, insertion/query APIs, and rewriting the spatial-check call sites within the collision/spatial subsystem — not a one-line swap, but scoped to one component.
Closest to 'persistent productivity tax' (b5), because per applies_to (library/browser/game contexts) and common_mistakes, the quadtree becomes a load-bearing spatial index: leaf capacity tuning, rebuild-vs-update strategy, and boundary-straddling handling shape ongoing work in the spatial subsystem, though it doesn't define the whole system.
Closest to 'notable trap most devs eventually learn' (t5), grounded in the misconception that quadtrees are always faster than linear scans — with clustered data or small n, spatial hash grids or flat arrays win, and unbalanced degeneration to O(n) depth is a documented gotcha experienced devs learn.
Also Known As
TL;DR
Explanation
A quadtree recursively subdivides a 2D region into four equal quadrants (NW, NE, SW, SE) until each leaf holds at most a small number of points or a uniform value. This partitioning gives roughly O(log n) expected cost for point location and expected O(log n + k) for range queries returning k results on non-degenerate data; nearest-neighbor uses best-first traversal with a priority queue. Common variants include the point quadtree (partition at each inserted point), the point-region (PR) quadtree (partition at fixed midpoints), and the region quadtree used for images and occupancy grids. Insertion walks the tree, subdividing any leaf that exceeds capacity; deletion may collapse siblings back up. Range queries prune entire subtrees whose bounding box does not intersect the query region, which is the key performance win over scanning every point. Quadtrees shine in game engines for broad-phase collision detection and frustum culling, in GIS for spatial indexing of map features, in image processing for compression by merging uniform regions, and in physics simulations like the Barnes-Hut algorithm for N-body problems. The 3D analog is the octree (eight children per node). Trade-offs: quadtrees can become unbalanced with clustered data, degrading to O(n) queries in the worst case; k-d trees or R-trees may perform better for high-dimensional or rectangular data. Loose quadtrees relax boundaries to keep large objects from splitting across quadrants. For static datasets, a bulk-loaded quadtree with tuned capacity typically outperforms a grid; for highly dynamic scenes with uniform density, a spatial hash grid may be simpler and faster.
Common Misconception
Why It Matters
Common Mistakes
- Choosing too small a leaf capacity, causing excessive subdivision and pointer overhead that dwarfs any query speedup.
- Rebuilding the entire tree every frame instead of incrementally updating nodes for moving objects.
- Ignoring worst-case degeneration when all points cluster in one quadrant, producing an unbalanced O(n)-depth tree.
- Storing large objects that straddle quadrant boundaries in a single leaf, forcing duplicate insertions or bloated parent nodes.
- Using a quadtree for uniformly dense 2D data where a fixed-cell spatial hash grid would be simpler and faster.
Avoid When
- Data is uniformly dense across the space - a fixed-cell spatial hash grid is simpler and typically faster.
- Working in more than 2 dimensions - use octrees (3D), k-d trees, or R-trees instead.
- Object counts are small (under ~100) - the tree overhead exceeds a linear scan.
- Objects move every frame and rebuild cost dominates query savings.
When To Use
- 2D collision detection or frustum culling in games with thousands of entities.
- Range and nearest-neighbor queries on geographic or GIS point data.
- Image compression or occupancy grids where large uniform regions can collapse into single nodes.
- N-body simulations using Barnes-Hut approximation for gravitational or particle systems.
Code Examples
// O(n^2) collision check - compare every pair of objects:
function detectCollisions(array $objects): array {
$collisions = [];
$n = count($objects);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
if (intersects($objects[$i], $objects[$j])) {
$collisions[] = [$i, $j];
}
}
}
return $collisions;
}
// 10,000 objects = 50 million comparisons per frame// Quadtree broad-phase - O(n log n) collision detection:
class Quadtree {
private const CAPACITY = 4;
private array $points = [];
private ?array $children = null;
public function __construct(private array $bounds, private int $depth = 0) {}
public function insert(array $point): bool {
if (!$this->containsPoint($point)) return false;
if ($this->children === null && count($this->points) < self::CAPACITY) {
$this->points[] = $point;
return true;
}
if ($this->children === null) $this->subdivide();
foreach ($this->children as $child) {
if ($child->insert($point)) return true;
}
return false;
}
public function queryRange(array $range): array {
if (!$this->intersects($range)) return [];
$found = array_filter($this->points, fn($p) => $this->pointInRange($p, $range));
if ($this->children !== null) {
foreach ($this->children as $child) {
$found = array_merge($found, $child->queryRange($range));
}
}
return $found;
}
}