Introduction to Quad Trees

Sometimes great ideas are also the simplest ones. This perfectly describes QuadTrees: a data structure fundamental to computer graphics, compression, and game development, yet built on an elegantly straightforward concept. Over the past weeks, I’ve explored their many applications and uncovered fascinating connections between seemingly distant domains. Ever wondered how the same recursive principle can optimize your video game performance, compress your satellite imagery, and power your map navigation? The humble QuadTree holds the answer. Let’s learn how dividing space can multiply possibilities.

The problem

Let’s begin with a practical challenge: quickly locating nearby objects in a 2D environment. Imagine you’re developing a game and need to detect potential collisions. The naive approach checks every possible pair of objects - a method that quickly becomes impractical with O(n²) comparisons.

This brute-force solution might work for a handful of objects, but it fails with larger numbers. We need something smarter. Consider this: why compare objects on opposite sides of your game world when they couldn’t possibly interact? What we need is a structure that organizes elements based on their spatial location.

Enter the QuadTree - an elegant recursive data structure that divides space into manageable regions. When any region becomes too crowded, it splits into exactly four equal subregions (hence “quad”). These subregions typically follow compass directions: NorthWest, NorthEast, SouthWest, and SouthEast (or alternatively, TopLeft, TopRight, BottomLeft, and BottomRight).

What makes QuadTrees truly brilliant is how they adapt to your data. Areas with many objects get split into smaller and smaller regions, while empty areas stay as larger chunks, saving resources by focusing detail only where needed. This creates a natural tree-like structure that grows deeper only in busy areas. The following visualization demonstrates this smart partitioning in action.

Quad Trees Use Cases

Implementation

Now that we understand the theory and real-world applications of QuadTrees, let’s implement one ourselves. We’ll use TypeScript to create a visualization that you can run in any modern browser. While the core QuadTree implementation is surprisingly simple, we’ll first define a couple of helper classes to represent basic 2D primitives like points and rectangles. These will make our code more readable and intuitive as we build our spatial structure.

export class Point {
  constructor(public readonly x: number, public readonly y: number) { }
  midpoint(other: Point) {
    return this.add(this.diff(other).div(2))
  }

  div(d: number) {
    return new Point(this.x / d, this.y / d)
  }

  mult(d: number) {
    return new Point(this.x * d, this.y * d)
  }

  diff(other: Point) {
    return new Point(Math.abs(other.x - this.x), Math.abs(other.y - this.y))
  }

  add(diff: Point) {
    return new Point(this.x + diff.x, this.y + diff.y)
  }

  distance(p: Point) {
    const dx = p.x - this.x;
    const dy = p.y - this.y;
    return Math.sqrt(dx * dx + dy * dy);
  }
}

export class Rect {
  constructor(public readonly p1: Point, public readonly p2: Point) { }

  contains(p: Point) {
    return this.p1.x <= p.x && this.p2.x >= p.x &&
      this.p1.y <= p.y && this.p2.y >= p.y
  }

  get size() {
    return this.p2.diff(this.p1)
  }
  move(v: Point) {
    return new Rect(this.p1.add(v), this.p2.add(v))
  }

  intersects(r2: Rect) {
    return (this.p2.x >= r2.p1.x && this.p1.x <= r2.p2.x && this.p2.y >= r2.p1.y && this.p1.y <= r2.p2.y)
  }

  distanceToPoint(point: Point) {
    const px = point.x;
    const py = point.y;

    let closestX = Math.max(this.p1.x, Math.min(px, this.p2.x));
    let closestY = Math.max(this.p1.y, Math.min(py, this.p2.y));
    const dx = px - closestX;
    const dy = py - closestY;

    return Math.sqrt(dx * dx + dy * dy);
  }
}

With that out of the way, let’s create our quad-tree class.

export class QuadTree {
    constructor(public readonly area: Rect, private readonly threshold: number = 4) {
    }

    zones: QuadTree[] = []
    elements: Point[] = []
}

Our QuadTree class needs two key parameters: a rectangle defining its spatial boundaries and a threshold value. This threshold determines when a node becomes too crowded and needs to split. Once the number of elements exceeds this value, the quadtree divides itself and redistributes its elements among the new subdivisions. For internal state management, we’ll maintain two important collections: an array to store the elements currently assigned to this quadrant, and an array for the four child quadtrees that will be created if splitting occurs. Let’s now implement the essential functionality of our QuadTree with the insert method. This function handles adding new points to our spatial structure while maintaining its organizational efficiency:

    insert(element: Point) {
        if (this.zones.length) {
            const intersecting = this.zones.find(z => z.area.contains(element))
            if (intersecting) {
                intersecting.insert(element)
            }
            return
        }

        this.elements.push(element)
        if (this.elements.length >= this.threshold && this.area.size.x > 1 && this.area.size.y > 1) {
            const halfSize = this.area.size.div(2)
            const rect = new Rect(this.area.p1, this.area.p1.add(halfSize))
            this.zones = [
                new QuadTree(rect, this.threshold), // NW
                new QuadTree(rect.move(new Point(halfSize.x, 0)), this.threshold), // NE
                new QuadTree(rect.move(new Point(0, halfSize.y)), this.threshold), // SW
                new QuadTree(rect.move(halfSize), this.threshold) // SE
            ]
            this.elements.forEach(e => {
                this.insert(e)
            })
            this.elements = []
        }
    }

If our node has already been subdivided, we’ll identify which child quadrant should contain the new point and recursively call insert on that subtree. Otherwise, we add the element directly to the current node’s collection.

This addition could push us over our threshold capacity. When that happens, we’ll split this node into four child quadtrees and redistribute all existing elements to their appropriate quadrants based on their spatial locations.

With these core operations in place, we now have a functioning QuadTree implementation! When we insert elements, they automatically cascade to the appropriate depth and location in our spatial hierarchy. You can check and interact with it below:

To fully utilize the capabilities of this data structure, we need to learn how to quickly query elements inside of it.

In the next article, you’ll learn how to efficiently find elements within a given region. After that, we’ll explore techniques for finding the nearest neighbor of any element, which requires smart traversal of the tree structure:

Quad Trees: Find in the area

Part 2: Searching quad tree to find all elements in a region

Also check out my previous article where I describe in details how I’ve built a game with infinite generative map in 13KB in JavaScript for JS13KGames comptetition. I used QuadTrees there too!

How I created a GameBoy-like game in 13kb

History of Gravepassing — my entry for js13kgames 2022.

Make sure to subscribe to my newsletter below to get notified as soon as new articles come out. You can also join my Discord community to discuss these concepts with fellow enthusiasts.

Subscribe to Newsletter