(Original image by GoAwayStupidAI).
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.
Recent Comments