18-Geom-A7 Geospatial Information Systems · December 2018
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Paper format. National Exams, December 2018 — 04-Geom-A7, Geospatial Information Systems. Closed book (one approved Casio or Sharp calculator permitted); duration 3 hours. Fifteen (15) questions are provided and any ten (10) constitute a complete paper; each question is of equal value (10 marks), so a complete paper totals 100 marks. Most answers are essay-format; clarity and organization count. All fifteen questions are solved below for completeness.
Longley, Goodchild, Maguire & Rhind, Geographic Information Systems and Science (4th ed.); P. Bolstad, GIS Fundamentals (5th ed.); Worboys & Duckham, GIS: A Computing Perspective (2nd ed.); Burrough, McDonnell & Lloyd, Principles of Geographical Information Systems (3rd ed.); de Smith, Goodchild & Longley, Geospatial Analysis; OGC Simple Feature Access (ISO 19125); ISO 19157 Geographic information — Data quality; ISO 19115 Metadata.
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.
What a region quadtree does. A region quadtree recursively subdivides a 2n×2n raster into four equal quadrants — NW, NE, SW, SE. If a quadrant is homogeneous (all cells share one class) it is stored as a single leaf node carrying that class; otherwise it becomes an internal node and is subdivided again, repeating until every branch reaches a homogeneous block or an individual cell. Here the grid is 16×16 = 24, so the tree has at most four levels of subdivision below the root.
Applying it to this map. The whole 16×16 root is mixed, so it splits into four 8×8 quadrants. The north-west 8×8 quadrant is entirely Sea, so it collapses to a single level-1 leaf — the big compression win. The other three 8×8 quadrants are mixed and subdivide further; homogeneous 4×4 and 2×2 blocks become leaves, and only the stepped class boundaries (sea/urban, urban/forest, lake/urban, lake/forest) force subdivision all the way down to 1×1 cells. The decomposition is shown below (heavy outlines = quadtree leaves).
Counting the leaves gives a compact index: 31 leaf nodes replace the 256 individual cells. They occur at four sizes: one 8×8 leaf (level 1), nine 4×4 leaves (level 2), nine 2×2 leaves (level 3) and twelve 1×1 leaves (level 4, only along the stepped boundaries). By class the leaves are 3 Sea, 14 Urban, 8 Lake and 6 Forest, and their areas tile the grid exactly (verified: Σ sizes² = 256, cell tally s 96 / u 89 / l 17 / f 54).
| Quadtree property | Value |
|---|---|
| Grid size | 16 × 16 = 256 cells (24) |
| Total leaf nodes | 31 (vs 256 cells) |
| Leaves by level (size) | 1 × 8×8, 9 × 4×4, 9 × 2×2, 12 × 1×1 |
| Leaves by class | Sea 3, Urban 14, Lake 8, Forest 6 |
| Cell tally | s 96, u 89, l 17, f 54 (Σ = 256) |
