An interactive explanation of quadtrees.

Here is a map of points in a space.

The space is divided into four rectangles. Each of those rectangles is divided such that it contains a maximum of four children. Each child is either a point or a smaller rectangle.

Click a rectangle and count its children to verify. None of them will contain more than four points or direct subrectangles.


Here is a graph of a quadtree representing the rectangles and points above.

 

1. Zoom out to see more of the tree.

Roll the mouse wheel inside of the tree view.

If you are on a touchscreen device, pinch out.

2. Pan around the tree.

Drag within the tree view.

What am I looking at here?

Why four children?

By definition, a quadtree is a tree in which each node has at most four children. Quadtree implementations — like D3's (source) — ensure that as points are added to the tree, nodes are rearranged such that none of them have more than four children.

Below are the graph of the quadtree and the map of the points and rectangles it represents again, side-by-side so that you can see how they relate to each other.

1. Look at how the map correlates to the tree.

Click on an rectangle or point in the map view (below on the left). The tree view (below on the right) will pan to the corresponding node in the tree.

Zoom out and pan around the tree view to see the node in context.

2. Look at how the tree correlates to the map.

Click on a tree node in the tree view. The map will highlight the area or point that it represents.

 



OK, so what is the point?

Quadtrees are a way of partitioning space so that it's easy to traverse and search. Some possible uses of that include:

Hit detection

Let's say you have a bunch of points in a space, like in the maps above. Someone asks you if some arbitrary point p is within your bunch of points. How can you find out if you have that point?

You could compare every single point you have to p, but if you had 1000 points, and none of them were p, you'd have to do 1000 comparisons to find that out. Alternatively, you could get very fast lookup by keeping a grid (a 2D array) of booleans for every single possible point in this space. However, if the space these points are on is 1,000,000 x 1,000,000, you need to store 1,000,000,000,000 variables.

Or you could set up a quadtree. When you have it search for p, it will find out which quadrant it is inside. Then, it will find out what quadrant within that quadrant it is inside. And so forth.

It will only have to do this at most seven times for a 100x100 space (assuming points can only have integer values), even if there are 1000 points in it. For a 1,000,000x1,000,000 space, it's a maximum of 20 times.

After it finds its way to that rectangle node, it merely needs to see if any of the four children equal p.

Finding the nearest neighbor

Again, let's say you have a bunch of points in a space. Rather than ask you whether any of them match a given point, someone asks you what the nearest point you have to an arbitrary point among your points.

With a quadtree, while searching, you can say, "OK, there's no way anything in this quadrant has any chance of being the nearest neighbor" and eliminate a lot of point comparisons that way. Patrick Surry has a good example of that.

…And more!

Really, quadtrees can help out any time you have sparse data that you need to search. A cellular automata simulation of a chemical reaction in which you want to save space by not storing data for cells containing inert substances? Sure. Just use quadtrees to map out the cells with the interesting data.

Wikipedia lists a bunch of other uses.

If you want to know more about using D3 quadtrees, check out the D3 API documentation. Perhaps the source of this document may be of help to you as well. Feel free to send me any requests for clarification or comments.