Quadtree: The Zoom Lens

The Story: The Pixelated Map

Imagine you are drawing a map of the world.

• The Pacific Ocean is huge and mostly empty blue water.
• Tokyo is tiny but packed with millions of streets and buildings.

If you use a grid of equal-sized squares (a matrix) to store this map, you have a problem. To capture the details of Tokyo, your grid cells must be tiny (1 meter). But that means you need trillions of tiny blue squares just to store the empty Pacific Ocean. This is a massive waste of memory.

A Quadtree solves this by being smart. It looks at the ocean and says: “This whole 1000km area is just blue. I’ll store it as one big square.” Then it looks at Tokyo and says: “This is complex. I will split it into 4 smaller squares. Is that enough? No? I’ll split those into 4 again.”

It adapts its resolution to the density of the data.

Why do we need it?

• Collision Detection (Games): Instead of checking if a bullet hits every object in the game world, you only check objects in the same Quadtree leaf as the bullet.
• Image Compression: Storing an image by grouping large blocks of similar color (similar to how JPEG works conceptually).
• Location Services: “Find all Uber drivers within 1km of me.”

How the Algorithm “Thinks”

The algorithm is a Recursive Divider.

1. The Box: Every node represents a rectangular region (bounding box).
2. The Capacity: Every node has a maximum capacity (e.g., 4 points).
3. The Split:
   • Insert a point into the node.
   • If the node exceeds its capacity, it subdivides into 4 children: North-West, North-East, South-West, South-East.
   • It moves the existing points into the correct children.

Engineering Context: The Balance

• Depth Limit: If you have 100 points stacked on top of each other (exact duplicates), the Quadtree will try to split infinitely until it crashes (Stack Overflow). Real-world implementations set a “Max Depth” to stop this.
• Rebalancing: Quadtrees are great for static data. If objects move around constantly (like in a game), rebuilding the tree every frame can be slow. In those cases, a loose grid or dynamic B-Tree might be better.

Implementation (Python)

class Rectangle:
    def __init__(self, x, y, w, h):
        self.x, self.y, self.w, self.h = x, y, w, h
    
    def contains(self, point):
        return (self.x <= point.x < self.x + self.w and
                self.y <= point.y < self.y + self.h)

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

class Quadtree:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary # Rectangle
        self.capacity = capacity
        self.points = []
        self.divided = False
        self.nw = self.ne = self.sw = self.se = None

    def subdivide(self):
        x, y, w, h = self.boundary.x, self.boundary.y, self.boundary.w, self.boundary.h
        mw, mh = w/2, h/2
        
        self.nw = Quadtree(Rectangle(x, y, mw, mh), self.capacity)
        self.ne = Quadtree(Rectangle(x + mw, y, mw, mh), self.capacity)
        self.sw = Quadtree(Rectangle(x, y + mh, mw, mh), self.capacity)
        self.se = Quadtree(Rectangle(x + mw, y + mh, mw, mh), self.capacity)
        self.divided = True

    def insert(self, point):
        if not self.boundary.contains(point):
            return False

        if len(self.points) < self.capacity:
            self.points.append(point)
            return True

        if not self.divided:
            self.subdivide()

        return (self.nw.insert(point) or self.ne.insert(point) or
                self.sw.insert(point) or self.se.insert(point))

    def query(self, range_rect, found):
        # Find all points within range_rect
        if not self.boundary.intersects(range_rect): # Assume intersects() exists
            return
        
        for p in self.points:
            if range_rect.contains(p):
                found.append(p)
        
        if self.divided:
            self.nw.query(range_rect, found)
            self.ne.query(range_rect, found)
            self.sw.query(range_rect, found)
            self.se.query(range_rect, found)

Summary

The Quadtree teaches us that detail should be paid for. We shouldn’t spend memory describing empty space. By focusing our resources (nodes) only where the complexity lies, we can represent massive worlds with a fraction of the cost. It is the ultimate algorithm of “Level of Detail.”