QUILT: a geographic information system based on quadtrees†

1 April 1990

journal article
research article
Published by Taylor & Francis in International Journal of Geographical Information Science

Vol. 4 (2) , 103-131
https://doi.org/10.1080/02693799008941534

Abstract

This paper describes QUILT, a prototype geographic information system (GIS) that uses the quadtree data structure as the underlying representation for 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.

Keywords

This publication has 17 references indexed in Scilit:

Set operations for unaligned linear quadtrees
Computer Vision, Graphics, and Image Processing, 1990
Optimal quadtree construction algorithms
Computer Vision, Graphics, and Image Processing, 1987
KBGIS-II A knowledge-based geographical information system
International Journal of Geographical Information Science, 1987
A consistent hierarchical representation for vector data
ACM SIGGRAPH Computer Graphics, 1986
Bintrees, CSG trees, and time
ACM SIGGRAPH Computer Graphics, 1985
Two-dimensional run-encoding for quadtree representation
Computer Vision, Graphics, and Image Processing, 1985
A B+-tree structure for large quadtrees
Computer Vision, Graphics, and Image Processing, 1984
A geographic information system using quadtrees
Pattern Recognition, 1984
A data structure and algorithm based on a linear key for a rectangle retrieval problem
Computer Vision, Graphics, and Image Processing, 1983
Ubiquitous B-Tree
ACM Computing Surveys, 1979