Today I’m going to introduce an interesting data structure for graphical applications: The Quad Tree.

Imaging a game with many more or less rectangular objects, with huge levels, in which only a small part actually has to be drawn – the rectangular screen. The naive idea of checking all objects if they intersect with the screen is nice – you don’t have to draw all objects, but that can be quite difficult to compute if you have thousands of rectangles.

The question the quad tree tries to answer is the following: Given this set of rectangles, is there a faster way to find all the rectangles that intersect with this one, than to iterate over all of them? Lets call that rectangles.allIntersecting(R)

The basic idea behind the Quad Tree (QT) is to sort out parts of the picture, that can not possibly contain any rectangles hitting R.

Take the rectangle [[0,0],[1,1]] as an example. Can R=[[0.1,0.1],[0.25,0.25]] hit the top right quadrant? Nope, so never mind even checking if there are rectangles in there, that hit R.

The quadtree only checks part of the subtrees for intersections.

Every QT is either a leaf or has exactly four subtrees. Because of the ease of computation, the subtrees divide their bounds in four equal parts. The rectangles are stored in the trees, not the leaves, which are essentially nil.

Let’s start with

tree.allIntersecting(R):=
    hits := rects in self.items that hit R
    for all subtrees s overlapping with R:
        hits.addAll(s.allIntersecting(R))
    return hits

What happens, when a new rectangle is added to the tree? Let’s call that

tree.addRect(rect):=
   if rect hits all subtrees
       self.items.add(rect)
    else
        for all subtrees s getting hit by rect
            s.addRect(rect)

By this, the rect possibly gets stored in multiple places, but that can’t be helped, else one couldn’t be sure, there is no rectangle lingering in another quadrant, that intersects with the screen, but wouldn’t been found.

Adding a tiny rectangle leads to many steps down the tree.

Does that solve the problem? That – as always – depends: The worst case for allIntersecting is the bounds of the tree, thus recursing all the way down. That makes it O(n*4^maxdepth), which is worse than the O(n) of the naive approach. Even worse: there is no upper bound to inserting a rectangle: Imagine adding a very small rectangle [[0,0][epsilon,epsilon]] to the tree. Now it takes O(log₂(1/epsilon)) steps until the rectangle hits a tree’s centre. And that function approaches infinity as epsilon gets small. That’s why QT’s should implement a maximal recursion depth, after which all pending rectangles are just inserted into the tree, no matter if they hit the centre.

However in the average case, there is a fixed size screen that is much smaller than the initial tree. Let’s assume the size of the screen is 2^k times smaller than the tree’s bounds, now we can discard 2-3 trees each step down until the bounds of the next trees are as big as the screen (that is after k steps). We get O(2^-kn4^(maxdepth-k)) runtime – a huge improvement to the naive approach. If we set the maxdepth so that maxdepth=k, we don’t get to feel the problems of the tree at all!

Next time, I’ll show you how I implemented it in Clojure, so stay tuned!

zombiecalypse