Quad-tree of the land-use map: 18-Geom-A7 Geospatial Information Systems, May 2017, Q15

Question 15: Quad-tree of the land-use map (5 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A 16 × 16 (= 2⁴ × 2⁴) land-use raster with four classes — s (Sea), u (Urban), l (Lake), f (Forest). Cell tally (verified): s = 96, u = 89, f = 54, l = 17 (256 cells total). Find. The region quad-tree that indexes this raster.

Approach. A region quad-tree recursively subdivides the square array into four equal quadrants (NW, NE, SW, SE); any quadrant that is homogeneous (all one class) becomes a leaf node holding that class, otherwise it is split again, down to single cells. Because the array is 2⁴, subdivision is exact and needs at most four levels.

Figure — region quad-tree decomposition of the 16 × 16 land-use raster. Each block is a leaf node; the block size shows the level (208 px = 8×8, 104 px = 4×4, 52 px = 2×2, 26 px = 1×1 cells). Colours: blue = Sea (s), grey = Urban (u), light-green = Lake (l), olive = Forest (f).

Root split (level 1). Divide the 16 × 16 array into four 8 × 8 quadrants. The NW quadrant is entirely Sea, so it becomes a single leaf (one node stands for 64 cells) — the key economy of a quad-tree. The NE, SW and SE quadrants are mixed and must be split again.
Second split (level 2, 4 × 4 blocks). Each mixed 8 × 8 quadrant divides into four 4 × 4 blocks. Homogeneous 4 × 4 blocks become leaves (e.g., in NE: two Sea blocks over two Urban blocks; in SE: three Forest blocks). This level yields 9 leaves.
Third and fourth splits (levels 3–4, 2 × 2 and 1 × 1). Blocks that straddle the stepped Sea/Urban, Urban/Lake and Urban/Forest boundaries keep subdividing into 2 × 2 blocks (9 leaves) and finally 1 × 1 single cells (12 leaves) where classes still differ.
Collect the tree. Recombining, the raster is indexed by 31 leaf nodes instead of 256 cells: 1 leaf at level 1, 9 at level 2, 9 at level 3 and 12 at level 4 — a large compression driven by the big homogeneous Sea and Forest regions.

Quad-tree property	Value
Array size	16 × 16 = 256 cells (2⁴, max depth 4)
Total leaf nodes	31 (vs 256 cells)
Leaves by level (1 / 2 / 3 / 4)	1 / 9 / 9 / 12
Leaves by class (s / u / l / f)	3 / 14 / 8 / 6
Largest single leaf	NW 8 × 8 = Sea (64 cells in one node)

Concept & Theory

Topic. Region quad-tree — a hierarchical raster indexing / compression structure.

Key relations. Recursively split a 2ⁿ × 2ⁿ array into four quadrants until each is homogeneous; a homogeneous block → one leaf node. Storage ∝ number of leaves, not cells; also serves as a spatial index (Morton/Z-order addressing).

Why this works. Real land-cover maps have large uniform regions; representing each uniform block by a single node collapses many identical cells, so the tree is compact when the map is "blocky" and only refines along class boundaries.

Common pitfall. Applying it to a non-power-of-two array (must be padded to 2ⁿ), or expecting compression on a noisy/salt-and-pepper raster where almost every block subdivides to single cells.

Source. H. Samet, The Design and Analysis of Spatial Data Structures, ch. 1–2; Bolstad, GIS Fundamentals, ch. 2 (raster compression: RLE & quad-tree).

Question 15 of 15: Quad-tree of the land-use map

Question 15: Quad-tree of the land-use map (5 marks)