A Geographic Information System Based on Quadtrees

Clifford A. Shafer, Hanan Samet, and Randal C. Nelson
University of Maryland, Department of Computer Science TR 1885
July 1987.

Abstract: This paper describes the current version of QUILT, a prototype Geographic Information System that uses the quadtree data structure as the underlying representation for the cartographic data. In this system, region data is represented by the region quadtree; point data is represented by the PR quadtree; and linear data is represented by th PMR quadtree. All three quadtree variants are implemented by use of the linear quadtree, organized on disk by a B-tree. QUILT provides a simple attribute attachment system which allows the association of non-spatial data with geographic objects. The user views QUILT as an augmented LISP environment. QUILT's geographic functions include conversion of rasters to and from quadtrees; subset operations to select specified geographic objects from maps; map editing; map intersection, and union operations; map display; map windowing; polygon expansion; and computation of geographic object properties such as the centroid, area, perimeter, and bounding rectangle for sets of geographic objects.