Page 1 of 2
If you do any advanced work in graphics sooner or later you will meet the Quadtree or its 3D relation the Octree. For this reason alone they are worth knowing about but they are also something you should have in your armoury of data structures.
The Quadtree and its three-dimensional brother the Octree are two fundamental data types that are well worth knowing about.
They have lots of applications but the reason I am writing about them now is that I've been working on a number of implementations of graphics algorithms that need both data structures. In particular I've been working on custom color reduction.
However, the theory of these two data structures is well worth knowing even if color reduction isn’t something that interests you. Also, for reasons that I’m not at all sure of, both the quadtree and the octree are often ignored or forgotten when they could be really useful.
It makes sense to start with the quadtree because it is simpler to explain – and draw!
A quadtree derives from the idea of dividing a square area into smaller squares. This connection with squares and refinement also determines where it tends to be useful, i.e. in 2D search or optimisation algorithms.
Start with a unit square as the root of the tree. Now divide the square into four smaller squares.
Each of the new smaller squares is a child node of the root.
The next step is to repeat the process on the small squares generating four more sub-squares and hence four children at the next level of the tree for each of them.
As you move down the quadtree each square is divided into four smaller squares.
At first it can be difficult to see the tree for the squares but the diagrams should help.
You can see how the tree idea fits into the picture a little better by drawing lines showing the children of each node. If you concentrate on the black lines you can see that they form a branching tree structure with four branches at each level.
We can make the view of the tree more abstract and closer to the data structure we use to represent it by flattening the tree part of the diagram into a 2D tree diagram.
The most abstract view emphasises the tree, but remember where the squares come from.
You can now see that a quadtree isn't really very special as a data structure - its just a tree where each node has four child nodes. The key idea however is that each child node represents a subdivision of the square that its parent node represents. Most of the work in implementing a quadtree goes into representing and implementing the division of the geometry rather than in building a sophisticated data structure.
There are other potential complications that you can encounter in practice. For example, it is usually the case that a quadtree is built up dynamically as the data becomes available. In this case the division of a square at one level may become necessary before some or any of the others have been divided. The result is an unbalanced quadtree the covers some areas more finely than others.