block by mbostock 87fbdfc4533df2ffa02b5bb62bfb5cb6

Animated Quadtree

Full Screen

This animation shows how successively adding points to a quadtree changes its structure. Each red dot represents a point; each gray rectangle represents a leaf node in the quadtree; black lines separate internal nodes. Assuming no coincident points, each gray leaf contains exactly one point. (If some points are coincident, the leaf node contains a linked list of the coincident points.)