Quadtree - 2D spatial partitioning with range and nearest-neighbor search
Build a point quadtree interactively and watch the canvas subdivide only where density increases. Switch between insert, range query, and nearest-neighbor modes to see how spatial pruning avoids visiting most quadrants.
A point quadtree stores points in axis-aligned rectangles. Each node holds up to capacity points. When another point would overflow the leaf, the node subdivides into four equal quadrants, and its points are redistributed downward.
For a range query, the algorithm first tests rectangle intersection. If a quadrant does not intersect the query box, the entire subtree is skipped. For nearest-neighbor search, the tree explores the child that contains the query first, then only visits other children when their bounding boxes could still contain a closer point.