Application of Hierarchical Data Structures to Geographical Information Systems

摘要

The purposes of this investigation were twofold: (1) to construct a geographic information system based on the quadtree hierarchical data structure, and (2) to gather statistics to allow the evaluation of the usefulness of this approach in geographic information system organization. To accomplish the above objectives, in Phase I of the project was built that contained three maps supplied under the terms of the contract. These maps described the floodplain, elevation contours, and land use classes of a region in California. In Phase II, a quadtree-based Geographic Information System was partially implemented, allowing manipulation of images which store area, point, and line data. Phase III primarily dealt with enhancements and alterations to this information system package, an evaluation of some of the design decisions, and the collection of empirical results to indicate the utility of the software and to justify the indicated design decisions. Phase IV primarily dealt with developing new structures for storing linear feature data. The attribute attachment package was extended to point and linear feature data. Existing area map algorithms were improved to yield significant efficiency speedups by reducing node accesses. The efficiency of the linear quadtree was compared to that of the pixel array for computation of several important geographic functions. The particular tasks reported on in this document are: (a) Memory management improvements; (b) Database enhancements; (c) Attribute attachment; (d) New linear feature representation; (e) Quadtree/array comparisons.