NivaarExam PrepOfficial exam papers ↗

18-Geom-A7 Geospatial Information Systems · May 2014

Question 17 of 23: Quad-tree and Run-length Encoding

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Exams — May 2014 — 04-Geom-A7 Geospatial Information Systems. Closed-book; no calculator permitted. Format: twenty-three short-answer questions of equal value (5 marks each); a candidate answers any twenty, but all twenty-three are solved in full below. Datum and coordinate conventions follow the Canadian spatial reference framework — NAD83(CSRS) horizontally and CGVD2013 vertically.

Reference texts: P. A. Longley, M. F. Goodchild, D. J. Maguire & D. W. Rhind, Geographic Information Systems and Science (4th ed., Wiley, 2015); P. Bolstad, GIS Fundamentals: A First Text on Geographic Information Systems (6th ed., XanEdu, 2019); P. A. Burrough, R. A. McDonnell & C. D. Lloyd, Principles of Geographical Information Systems (3rd ed., Oxford, 2015); M. Worboys & M. Duckham, GIS: A Computing Perspective (2nd ed., CRC, 2004); ISO 19115 Geographic information — Metadata.

Question 17: Quad-tree and Run-length Encoding (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.

Both are raster data-compression and indexing techniques that exploit the fact that neighbouring cells often share the same value. A quad-tree recursively subdivides a raster into four equal quadrants, and each quadrant into four again, continuing only where a block is not homogeneous; subdivision stops as soon as a block contains a single value. The result is a tree in which large uniform areas are stored as a single large leaf and only heterogeneous areas are refined to small cells, giving efficient storage for clustered/sparse data and a natural spatial index (variable resolution) that speeds search and overlay.

quad-tree: refine only mixed blocksrow: A A A B B ARLE: (A,3)(B,2)(A,1)store runs, not cells
Figure — Quad-tree refines only heterogeneous quadrants; run-length encoding stores each row as (value, run-length) pairs.

Run-length encoding (RLE) compresses a raster by scanning it row by row and storing each consecutive run of identical cell values as a single (value, run-length) pair instead of repeating the value for every cell — for example a row "A A A B B A" is stored as (A,3)(B,2)(A,1). It is lossless and highly effective when the raster has large homogeneous areas (thematic maps, classified imagery), but gives little benefit on "busy" rasters where values change every cell. Both techniques reduce the storage cost of the raster model's chief weakness — redundant repetition of values — while the quad-tree additionally provides a hierarchical spatial index for faster query.