Quadtrees and Octrees
Thursday, 09 December 2010
Article Index
Quadtrees and Octrees
Faster and smarter


Fast sorting

OK so now you understand the quadtree – what use is it?

The answer is that the different levels of the tree provide different resolutions of detail and this can be useful in many different ways. 

For example, if you have a two-dimensional data point, x,y, then this will fall in exactly one node at each level of the tree. You can use this fact to perform a fast search of a data set.

First sort the data into a quadtree and then when you want to see if a particular data value x,y is present you simply move down the tree via the correct node at each level until you reach the bottom and find the point or discover it isn’t present.

This is the two-dimensional equivalent of the binary search algorithm used to search a one-dimensional list.

Such algorithms have some surprising applications for example if you want to make Conway's Game of Life (The Meaning of Life ) go faster then use a quadtree.

The Octree

Once you have understood the quadtree, the octree is almost obvious.

In three dimensions the square is replaced by a cube and the division into four is replaced by a division into eight sub-cubes – hence oct–tree, since oct = eight.


cubesAn octree division divides each cube into eight sub-cubes.


Thus the octree is just a generalisation of the quadtree to 3D.

Each node corresponds to a single cube and has exactly eight sub-nodes.

Notice that all of the sub-node cubes are contained within the parent cube. As in the case of the quadtree, the octree can be used to find a data point, but this time a three-dimensional point, very quickly.

As before you can flatten out the octree and draw it as a standard tree structure.




The octree branches very rapidly and it doesn’t take very many levels to generate lots of nodes but apart from this implementing it as a data structure isn't difficult. What tends to be difficult is managing the geometry needed to divide the cubes and store the details at each node.

As in the case of the quadtree the octree is often built up dynamically as data become available. In this case dynamic construction often results in an unbalanced tree with areas of space being covered more finely than others.

As already mentioned octrees are useful when you have to search a 3D space. In particular they are often used in efficient collision detection but they also occur in algorithms that work in more abstract 3D space. For example the color space is generally considered to be 3D with dimensions Red, Green and Blue. Hence yo can use an octree to organise a the use of color by an image and perform color reduction or quantization.  


Related reading:

The custom color reduction project that prompted this theory article will be posted shortly

If you would like to be informed about new articles on I Programmer you can either follow us on Twitter, on Facebook , on Digg or you can subscribe to our weekly newsletter.







Last Updated ( Thursday, 30 December 2010 )

RSS feed of all content
I Programmer - full contents
Copyright © 2015 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.