Quadtrees and where to find them

A quadtree? What’s a quadtree? We’re about to find out.

Do you remember the first day of our 12 days of Contentful?

You upload an image and see it reveal itself progressively, from a few colors to a final image, like this:

But it’s more advanced than just pixelation, which looks like this:

Underneath this is, you guessed it: A quadtree!

What’s a quadtree?

A quadtree is a tree data structure in which each node has exactly 4 children (hence quad tree). The 4 child nodes can also have children.

We use Quadtrees for spatial partitioning 🥱. It just means a way to divide a two-dimensional space into smaller regions, like tiling. Or, on a screen:

The idea is to then arbitrarily divide space using this structure. Using our previous example from the first day:

If you look closely, you can see each square splitting into 4, then into 4 again, and again.

Beyond obsure image art, there are other use cases for quadtrees, let’s have a look at one:

Collisions

Here’s an example scenario inspired by d3’s implementation, we have 1000 circles, and we want to find which ones lie within a 100px radius of the mouse.

The code to check which points are in the circle looks like this:

points.forEach((point) => {
  const dx = point.x - mouseX
  const dy = point.y - mouseY
  if (dx * dx + dy * dy <= 10000) {
    // 10000 = 100 * 100
    // This point is within a 100px radius of the mouse, so draw it in a different color
    point.color = '#f7be10'
  } else {
    point.color = 'seagreen'
  }

  ctx.beginPath()
  ctx.arc(point.x, point.y, point.r, 0, 2 * Math.PI)
  ctx.fillStyle = point.color
  ctx.fill()
  ctx.closePath()
})

You can see that we have to go through each point and calculate the distance to the mouse. That means 1000 collision checks per frame, 60 times per second.

What if we could divide space in a way that lets us do fewer checks? That’s where quadtrees come in.

By dividing the space into smaller and smaller regions, quadtrees can determine which objects are in a given area without having to search through the entire data set.

I could go on and on as there’s lots we can do with quadtrees, but that’s it for today! I hope you learned something new.