next up previous contents index Search
Next: Octree Source Code Up: 0.2 Data Searching and Previous: Source Code

0.2.10 Quadtrees and Octrees


A quadtree is a hierarchical data structure often used for image representation. Quadtrees encode two-dimensional images by placing subsections of the image into a tree structure much like a binary tree. Unlike a binary tree where every tree node has up to two children, in a quadtree every node can have up to four children. Each node stores a particular piece of the overall image.

Quadtrees operate by means of recursively decomposing space.   While several specialized types of quadtrees exist, the most common type are known as region quadtrees.   In such trees the image to be encoded and stored is partitioned into four quadrants. Each quadrent is then represented by a node in the tree. The root of the quadtree represents the entire stored image while each of it's four children represent a different fourth of the image. This process continues; each of the quadrants represented by the children of the root is again partitioned into four sub-quadrants and represented by the root's grandchildren nodes. This process continues until a region being stored is sufficiently simple that it can be wholly encoded in one node. Sometimes this means that we continue breaking the image down until every individual pixel is stored at some leaf node. Other times a region larger than a pixel is sufficiently homogeneous that it can be represented at a leaf node and requires no further decomposition. For example, if an entire quadrent is one color it does not make sense to continue to decompose it.

The regions represented by nodes in a quadtree are sometimes named after map directions (northwest, northeast, southwest, southeast).

An octree is essentially the same thing as a quadtree however each node in an octree has eight children instead of four. This makes octrees good candidates for representing three-dimensional objects in memory because instead of breaking the image into four quadrants the octree breaks the image into eight blocks. These blocks are then recursively decomposed into eight sub-blocks. This process, as in the quadtree, continues until a blocks is sufficiently homogenous that it can be represented by one node.

An interesting property of both quadtrees and octrees is that they support a form of data compression. By never traversing below a certain level of the tree structure it is possible to filter out the "details" of the image opting, instead, for a less-precise but smaller version of the data. Such a compression could be accomplished by means of a breadth-first traversal of the tree data structure.

Scott Gasch