Quadtree

From VoroWiki

To solve the problem with massive raster files, hierarchical tessellations can be used. A commonly used structure in two dimensions is the region quadtree, which indexes and merges adjacent grid cells to save space. As shown in the figure on the right, it recursively subdivides the space into four squares of equal size, until every square contains one homogeneous region (based on the attribute of every grid cell).

Example of a raster representation (left), and its compression with the region quadtree (right).

A quadtree is a generic term for a family of tessellations that recursively subdivide the plane into four quadrants, labelled NE, NW, SW and SE (NE being north-east, SW being south-west, and so on). It is easily implemented in a computer because it is a tree, where each node has exactly four children, if any. Different variant of quadtree have been proposed (see Samet (1984)^[1] for an excellent survey), but we focus here on the most relevant type for modelling fields, the PR quadtree (P stands for point, and R for region). This assumes that the quadtree is based on a set of points, e.g. the samples collected to study a field. A PR quadtree recursively subdivides the plane into squares of equal size until each square contains a maximum of one point, and each node of the tree therefore corresponds to a square (see the figure). Notice that some squares do not contain any points, and also that a quadtree offers an adaptive solution as more squares are present to capture more details where there are more points. The quadtree easily generalises to higher dimensions. For instance, in three dimensions, the space is recursively subdivided into eight octants, and thus the tree is called an octree for each node has eight children.

Quadtree of a set of points in the plane.

Voxel.

The main advantage of using the structure -- saving memory space -- is actually true only when the distribution of the points is more or less regular. Indeed, the size and depth of an octree is not dependent on the number n of points it stores, but rather on their distribution in space (see de Berg et al. (2000)^[2] for an analysis). When the point distribution is irregular (e.g. contains clusters), the tree can be unbalanced (and have arbitrary depth), and therefore the query and the manipulation (insertion or deletion of points) of an octree can be extremely slow. The compressed quad/octree improves this situation by eliminating all the non-leaf node having only one non-empty child, but the depth of an octree can still be O(n) in the worst case.

References

1. ↑ Samet, H. (1984), The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys 16(2), 187-260.
2. ↑ de Berg, M.; van Kreveld, M.; Overmars, M. & Schwarzkopf, O. (2000), Computational Geometry: Algorithms and Applications, Springer-Verlag, Berlin.