Below are four C++ implementations of the region quadtree (the kind used for image compression, for example). The different implementations were made in an attempt to optimise construction of quadtrees. (For a tutorial on implementing region quadtrees, see Issue 26 [6.39 MB zip] of Dev.Mag).

• NaiveQuadtree is the straightforward implementation.
• AreaSumTableQuadtree uses a summed area table to perform fast calculations of the mean and variance of regions in the data grid.
• AugmentedAreaSumTableQuadtree is the same, except that the area sum table has an extra row and column of zeros to prevents if-then logic that slows it down and makes it tricky to understand.
• SimpleQuadtree is the same as AugmentedAreaSumTableQuadtree , except that no distinction is made (at a class level) between different node types.

The code below implements some quadtree extensions, as discussed in another Dev.Mag tutorial about quadtrees (see Issue 27). The tutorial covers the following topics:

• what to consider in choosing whether to use a quadtree or not;
• how to handle discrete data; and
• some modifications to the basic algorithm.

## Handling Discrete Data

When it comes to discrete data, the “average” of a number of pixels doesn’t make sense. However, we can give it meaning and still use it to get good approximations of the original data, as illustrated in the images below.

 The original grid of discrete data. The grid contains integers from 0 to 4. Every integer is mapped to a colour in this image. (If this grid represented a tile map, every integer would be mapped to a different tile). Here we allowed floating point numbers in the quadtree. Results of queries into the quadtree are rounded before mapping them to colours. Here we used the floating point part of queries to bias a randomly selected integer. For example, a result of 1.25 will result in a 75% chance of yielding 2. Here we use a quadtree with interpolation. The result is rounded before it is mapped. Here we use a quadtree with interpolation, and use the floating point part of the number to bias a randomly selected tile, as above.