Quadtree Cheatsheet

In geospatial apps, quadtrees are widely used for streaming imagery, terrain, vectors, and other data. Here’s a cheatsheet for some common operations for a complete quadtree (all leaf tiles are at the same level). We use the term tile, instead of node, since tile is popular in the geospatial world, and use the term level to define the zero-based depth/scale/zoom-level/z of a tile. The root is at level zero, its children are at level one, and so on.

Number of tiles at a level

Each quadtree tile is split into four tiles by two axis-aligned splitting-planes so at a level n, there are 2^n by 2^n tiles in the level, or just 4^n.

function numberOfTiles(n) {
   return Math.pow(4, n);
}

// numberOfTiles(0) -> 1
// numberOfTiles(1) -> 4
// numberOfTiles(2) -> 16

Total number of tiles up to a level

Above, we compute the number of tiles at a level. Let’s extend this to also include all of the ancestor tiles up to and including the root. This is the sum of 4^n for n from zero to the maximum level, n.

function numberOfTotalTiles(n) {
   return (Math.pow(4, n + 1) - 1) / 3;
}

// numberOfTotalTiles(0) -> 1
// numberOfTotalTiles(1) -> 5 (4 + 1)
// numberOfTotalTiles(2) -> 21 (16 + 4 + 1)

Maximum level for a number of leaf tiles

To build a quadtree that will accommodate m leaf tiles (where m is greater than zero), take the ceiling of the log of m base 4.

function maximumLevel(m) {
   return Math.ceil(Math.log(m) / Math.log(4.0));
}

// maximumLevel(1)  -> 0
// maximumLevel(2)  -> 1
// maximumLevel(4)  -> 1
// maximumLevel(5)  -> 2
// maximumLevel(16) -> 2

Tile Map Service (TMS) Layout

In geospaital apps, Tile Map Service (TMS) and similar layouts are widely used for requesting quadtree tiles.

Generally, the quadtree is subdivided by lines of longitude (x) and latitude (y). The path for a quadtree tile is z/x/y.png (.png could be any extension), where z is the level, x increases from west to east, and y increases from south to north. For example, 0/0/0.png is the root tile; 1/0/0.png is the bottom-left tile at level 1; and 1/0/1.png is the top-left tile at level 1.