A Geographic Information System Based on Quadtrees

Clifford A. Shafer, Hanan Samet, and Randal C. Nelson
Department of Computer Science
University of Maryland, University of Rochester
Rochester, NY 14627

Abstract: This paper describes QUILT, a prototype Geographic Information System that uses the quadtree data structure as the underlying representation for the cartographic data. While QUILT contains many features typically available in a GIS, its primary purpose is to serve as a testbed for the design and testing of new data structures and algorithms for use in computer cartography. Quadtree variants for region, point, and line data are implemented using the linear quadtree, organized on disk by a B-tree. QUILT provides a simple attribute attachment system which associates 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; map editing, display, windowing, intersection, and union operations; polygon expansion; and computation of geographic object properties such as the centroid, area, perimeter, and bounding rectangle for sets of geographic objects.