# Quadtree Cheatsheet

##
by
**
Patrick Cozzi
**

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`

.

## 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`

.

## 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`

.

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