Quad Tree: 2D Space Partitioning
Every game developer or graphics programmer eventually hits the same wall: you've got hundreds of objects on screen, and checking every pair for collisions turns your silky-smooth 60 FPS into a...
Key Insights
- Quad trees reduce collision detection and spatial queries from O(n²) to O(n log n) by recursively partitioning 2D space into four quadrants, allowing you to prune entire regions from consideration.
- The key design decision is your capacity threshold—too low and you waste memory on deep trees, too high and you lose the benefits of spatial partitioning.
- Quad trees excel for static or slowly-changing data; for highly dynamic scenes with constant object movement, consider spatial hashing or rebuilding the tree each frame instead of incremental updates.
Introduction to Spatial Partitioning
Every game developer or graphics programmer eventually hits the same wall: you’ve got hundreds of objects on screen, and checking every pair for collisions turns your silky-smooth 60 FPS into a slideshow. With 1,000 objects, that’s nearly 500,000 pair checks per frame. At 10,000 objects, you’re looking at 50 million checks. The naive O(n²) approach simply doesn’t scale.
Quad trees solve this by applying divide-and-conquer to 2D space itself. Instead of asking “does object A collide with object B?” for every possible pair, you first ask “which objects are even close enough to possibly collide?” By organizing objects spatially, you can eliminate vast swaths of candidates without examining them individually.
The concept is elegantly simple: recursively divide your 2D space into four quadrants until each region contains a manageable number of objects. Queries then traverse only the relevant branches, skipping entire subtrees that can’t possibly contain what you’re looking for.
Quad Tree Fundamentals
A quad tree is a tree where each internal node has exactly four children, representing the four quadrants of a rectangular region: northeast (NE), northwest (NW), southeast (SE), and southwest (SW). The root node represents the entire space you’re partitioning.
Each node maintains a list of points (or objects) within its bounds. When that list exceeds a capacity threshold, the node subdivides into four children and redistributes its contents. Leaf nodes contain the actual data; internal nodes exist purely to route queries to the correct region.
Here’s the basic structure:
from dataclasses import dataclass, field
from typing import List, Optional
@dataclass
class Point:
x: float
y: float
data: any = None # Attach arbitrary data to points
@dataclass
class Rectangle:
x: float # Center x
y: float # Center y
width: float # Half-width
height: float # Half-height
def contains(self, point: Point) -> bool:
return (self.x - self.width <= point.x <= self.x + self.width and
self.y - self.height <= point.y <= self.y + self.height)
def intersects(self, other: 'Rectangle') -> bool:
return not (other.x - other.width > self.x + self.width or
other.x + other.width < self.x - self.width or
other.y - other.height > self.y + self.height or
other.y + other.height < self.y - self.height)
@dataclass
class QuadTree:
boundary: Rectangle
capacity: int
points: List[Point] = field(default_factory=list)
divided: bool = False
northeast: Optional['QuadTree'] = None
northwest: Optional['QuadTree'] = None
southeast: Optional['QuadTree'] = None
southwest: Optional['QuadTree'] = None
The Rectangle class uses center-point representation with half-dimensions, which simplifies intersection math. The capacity parameter is crucial—it determines when nodes split. Values between 4 and 16 work well for most applications. Too low, and you create excessive tree depth. Too high, and you’re back to linear scans within nodes.
Core Operations: Insert and Subdivide
Insertion follows a simple recursive pattern: if the point falls within this node’s bounds and we have capacity, store it here. If we’re at capacity, subdivide first, then delegate to the appropriate child.
def insert(self, point: Point) -> bool:
# Ignore points outside our boundary
if not self.boundary.contains(point):
return False
# If we have room, add the point here
if len(self.points) < self.capacity:
self.points.append(point)
return True
# Otherwise, subdivide if we haven't already
if not self.divided:
self._subdivide()
# Delegate to children
if self.northeast.insert(point):
return True
if self.northwest.insert(point):
return True
if self.southeast.insert(point):
return True
if self.southwest.insert(point):
return True
# Should never reach here if boundary logic is correct
return False
def _subdivide(self):
x = self.boundary.x
y = self.boundary.y
w = self.boundary.width / 2
h = self.boundary.height / 2
ne_bounds = Rectangle(x + w, y - h, w, h)
nw_bounds = Rectangle(x - w, y - h, w, h)
se_bounds = Rectangle(x + w, y + h, w, h)
sw_bounds = Rectangle(x - w, y + h, w, h)
self.northeast = QuadTree(ne_bounds, self.capacity)
self.northwest = QuadTree(nw_bounds, self.capacity)
self.southeast = QuadTree(se_bounds, self.capacity)
self.southwest = QuadTree(sw_bounds, self.capacity)
self.divided = True
# Redistribute existing points to children
for point in self.points:
self.northeast.insert(point) or \
self.northwest.insert(point) or \
self.southeast.insert(point) or \
self.southwest.insert(point)
self.points = [] # Clear points from this node
Notice that after subdivision, we redistribute existing points to the appropriate children. This keeps all data at the leaf level, simplifying queries.
Querying the Tree
Range queries are where quad trees earn their keep. Given a rectangular search region, we return all points within that region—but we only examine nodes whose bounds intersect our search area.
def query_range(self, range_rect: Rectangle, found: List[Point] = None) -> List[Point]:
if found is None:
found = []
# Prune: if this node doesn't intersect the range, skip entirely
if not self.boundary.intersects(range_rect):
return found
# Check points in this node
for point in self.points:
if range_rect.contains(point):
found.append(point)
# If subdivided, recurse into children
if self.divided:
self.northeast.query_range(range_rect, found)
self.northwest.query_range(range_rect, found)
self.southeast.query_range(range_rect, found)
self.southwest.query_range(range_rect, found)
return found
The magic happens in the first intersection check. If our search rectangle doesn’t overlap this node’s boundary at all, we return immediately—potentially skipping thousands of points in that subtree. This transforms what would be a linear scan into a logarithmic traversal for reasonably distributed data.
Practical Application: Collision Detection
Let’s build a simple particle collision system. The quad tree handles “broad phase” detection—identifying which particles might collide. We then do precise distance checks only on those candidates.
import math
@dataclass
class Particle:
x: float
y: float
radius: float
vx: float = 0.0
vy: float = 0.0
def find_collisions(particles: List[Particle], world_bounds: Rectangle) -> List[tuple]:
# Build quad tree fresh each frame
qt = QuadTree(world_bounds, capacity=8)
for i, p in enumerate(particles):
point = Point(p.x, p.y, data=i) # Store index as data
qt.insert(point)
collisions = []
for i, p in enumerate(particles):
# Query region is particle position ± maximum collision distance
search_radius = p.radius * 2 # Assumes uniform particle sizes
search_rect = Rectangle(p.x, p.y, search_radius, search_radius)
candidates = qt.query_range(search_rect)
for candidate in candidates:
j = candidate.data
if j <= i: # Avoid duplicate pairs and self-collision
continue
other = particles[j]
# Narrow phase: precise distance check
dx = p.x - other.x
dy = p.y - other.y
distance = math.sqrt(dx * dx + dy * dy)
min_distance = p.radius + other.radius
if distance < min_distance:
collisions.append((i, j))
return collisions
# Usage
world = Rectangle(500, 500, 500, 500) # 1000x1000 world
particles = [Particle(random.uniform(0, 1000), random.uniform(0, 1000), 5)
for _ in range(1000)]
colliding_pairs = find_collisions(particles, world)
With 1,000 particles, this approach typically examines only 5-20 candidates per particle instead of 999. The speedup is dramatic.
Performance Analysis and Trade-offs
Average-case query complexity is O(log n) when points are reasonably distributed. Insertion is also O(log n) on average. However, these guarantees degrade with pathological data.
The worst case occurs when points cluster tightly. If all points occupy the same tiny region, the tree degenerates into a linked list with O(n) depth. Some implementations cap maximum depth to prevent this, accepting that deeply-nested nodes may exceed capacity.
Space overhead is modest—O(n) for the points themselves, plus O(n) for internal nodes in the worst case. In practice, internal node count is much smaller.
Quad trees struggle with highly dynamic scenes. If objects move every frame, you face a choice: rebuild the entire tree (simple but wasteful) or implement deletion and reinsertion (complex and often slower than rebuilding). For games with hundreds of fast-moving objects, rebuilding per frame is usually the pragmatic choice.
Variations and Alternatives
Point-region vs. region quad trees: The implementation above is a point-region (PR) quad tree, storing points at leaf nodes. Region quad trees instead subdivide based on homogeneous regions, useful for image compression or terrain representation.
Loose quad trees: These use overlapping boundaries, allowing objects to remain in a single node even when they straddle quadrant boundaries. This trades query precision for simpler updates with moving objects.
K-d trees: For higher dimensions or when you need nearest-neighbor queries, k-d trees often outperform quad trees. They partition along a single axis at each level, adapting better to non-uniform distributions.
Spatial hashing: For uniformly-sized objects in bounded worlds, spatial hashing offers O(1) insertion and query with less overhead. It’s often the better choice for real-time games with many moving entities.
Choose quad trees when you have 2D data with varying density, need range queries, and can tolerate occasional rebuilds. For static geographic data, quad trees are nearly ideal. For twitchy action games with thousands of bullets, spatial hashing will serve you better.