Quadtree Generator
An even grid is the wrong shape for uneven data: it wastes cells on empty space and still overloads the busy parts. A quadtree fixes that by splitting only where it needs to — a cell divides into four as soon as it holds more points than it should, and leaves the empty areas alone. The result adapts to whatever it is given, which is why it underpins so much spatial indexing and collision detection.
What this generator does
Scatters points in clusters so the subdivision has something to react to, then divides the region recursively: any cell holding more than the capacity splits into four, and the process repeats until every cell is within capacity or the depth limit is reached.
How to use this tool
- Choose how many points and how many each cell may hold.
- Look at where the grid goes fine and where it stays coarse.
- Lower the capacity to one and watch the subdivision deepen sharply.
- Note that the cells still tile the whole region exactly, however uneven they are.
Understanding the controls
- How many points
- Between 4 and 60, drawn around three cluster centres rather than uniformly, so the subdivision is visibly uneven.
- Points per cell
- A cell splits into four as soon as it holds more than this. A capacity of one produces the deepest tree and the clearest picture of where the data is.
- Seed
- Any word reproduces exactly the same points and the same subdivision.
Common use cases
- Understanding spatial indexing before implementing one
- Teaching recursive subdivision with visible, uneven data
- Generating test structures for collision detection or nearest-neighbour work
- Showing why an even grid is the wrong tool for clustered data
- Setting the same point set twice from a seed
How this generator works
Each split divides a cell into four equal quadrants, and the points inside are handed to whichever quadrant contains them. The check is that the leaf cells tile the region exactly — their areas summing to the whole — that every point sits in precisely one cell and inside its bounds, and that no cell exceeds capacity unless the depth limit stopped it splitting.
Randomness and fairness
The point positions are random, drawn in clusters; the subdivision is a deterministic consequence of where they land. A seed reproduces the same set exactly and is therefore explicitly not cryptographically secure. Without a seed the browser's cryptographically secure generator is used.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Depth is capped at six levels, so a very tight cluster can leave a cell over capacity — the tool reports that rather than subdividing forever.
- Points are clustered rather than drawn from real data.
- A fixed square region; quadtrees on arbitrary bounds work identically but are not offered here.
- No queries are demonstrated — this builds the structure rather than searching it.
- Structures are not stored between visits; seed one you want again.
Privacy and your data
The points and the subdivision are computed on your own device. Nothing about the structure or your seed leaves the browser.
Related generators
- Space-Filling Curve GeneratorHilbert and Z-order curves drawn across a grid, with every cell confirmed visited exactly once.
- Strip Packing GeneratorRectangles packed into a fixed-width strip with no overlaps, measured against the height no packing could beat.
- Poisson Disc Point GeneratorPoints with a guaranteed minimum separation, placed by Bridson's algorithm and measured against a uniform scatter of the same size.
- Clustered Dataset GeneratorPoints grouped around known centres with the true group recorded, so you can check what a clustering algorithm actually recovered.