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.
| 
Search