Quadtree Spatial Partitioning

Efficient 2D spatial queries using recursive subdivision

Basic Quadtree
Range Query
Collision Detection

What is a Quadtree?

A quadtree is a tree data structure where each node has exactly four children. It recursively subdivides 2D space into quadrants (NE, NW, SE, SW) to efficiently organize spatial data.

  • Insertion: O(log n) average case
  • Range Query: O(log n + k) where k is results
  • Use Cases: Game engines, image compression, GIS systems
0
Total Points
1
Tree Nodes
0
Max Depth

Range Queries

Click and drag to define a rectangular query region. The quadtree quickly finds all points within this region by pruning entire branches that don't intersect.

Algorithm: For each node, if the query region doesn't intersect the node's boundary, skip that entire subtree. This dramatically reduces the search space.

0
Total Points
0
Points in Range
0
Nodes Checked

Brute Force

0.00ms

Checks every point

Quadtree

0.00ms

Prunes irrelevant branches

Optimized Collision Detection

Watch particles move and collide. The quadtree dramatically reduces collision checks from O(n²) to O(n log n).

  • Without quadtree: Every particle checks against every other particle
  • With quadtree: Only check particles in nearby cells
  • Speedup: 10-100x faster for hundreds of particles
100
Particles
0
Collision Checks
0
Active Collisions
60
FPS