Build a Quadtree

recursive spatial subdivision

Challenge 6 of Indexes & StructuresIntermediate~45 min

Index 2-D points so 'what's in this region?' is fast instead of a full scan. Build the bounding-box math, insert points, subdivide a node into four quadrants when it fills up, and answer rectangular range queries, the spatial tree behind collision detection, maps, and nearest-neighbor search.

4 steps

1. 1Bounding Boxes
2. 2Inserting Points
3. 3Subdividing
4. 4Range Queries