Region Quadtree

A region quadtree is a spatial data structure that represents a two-dimensional image or region by recursively subdividing it into four quadrants. Unlike the point quadtree, which stores points at nodes, the region quadtree stores information about homogeneous regions at its leaves: each leaf is either entirely inside a region, entirely outside, or a mixed region requiring further subdivision. This makes the region quadtree particularly efficient for binary images and for spatial data with large homogeneous areas.

The region quadtree is widely used in geographic information systems for raster data compression, in computer graphics for collision detection, and in image databases for content-based retrieval. Its compression ratio depends on the homogeneity of the data: images with large uniform regions compress dramatically; noisy images compress poorly.

The region quadtree's efficiency is a function of the world's regularity, not of the structure's intelligence. A landscape with straight boundaries and uniform fields compresses beautifully; a coastline or a forest does not. The region quadtree is therefore a measure of how much we have simplified the world before encoding it — and the compression ratio is a confession of that simplification.