Pattern Rect~jnition Vol. 17, No. 6. pp. 647 656, 1984. Prinled ill (;real i|ritain. 0031 3203/84 $3.00+ .00 Pergamon Press Lid ,I 1984 Pattern Recognition Society A GEOGRAPHIC INFORMATION SYSTEM USING QUADTREES* HANAN SAMET, f AZRIEL ROSENFELD, CLIFFORD A. SHAEFER and ROBERT E. WEBBER Computer Science Department and Center for Automation Research, University of Maryland, College Park, MD 20742, U.S.A. (Received 13 December 1983; in revised form 28 February 1984; received for publication 15 March 1984) Abstract--We describe the current status of an ongoing research effort to develop a geographic information system based on quadtrees. Quadtree encodings were constructed for area, point and line features for a small area in Northern California. The encoding used was a variant of the linear quadtree. The implementation used a B-tree to organize the list of leaves and allow management of trees too large to fit in core memory. Several database query functions have been implemented, including set operations, region property computations, map editing functions and map subset and windowing functions. A user of the system may access the database via an English-like query language. Quadtrees Geographic information systems Curve representation Image processing Region representation I. INTRODUCTION The quadtree representation of regions, first proposed by Kiinger, "~ has been the subject of intensive research over the past several years (for an overview, see the survey by Samet~2~). Numerous algorithms have been developed for constructing compact quadtree repre- sentations, converting between them and other region representations, computing region properties from them and computing the quadtree representations of Boolean combinations of regions from those of the given regions. Quadtrees have traditionally been im- plemented as trees which require space for the pointers from a node to its sons. Recently, there has been a considerable amount of interest in pointer-less quad- tree representations ~3"4~ termed linear quc~dtrees. In this case, the set of regions is treated as a collection of leaf nodes. Each leaf is represented by use of a locational code corresponding to a sequence of directional codes that locate the leaf along a path from the root of the tree. In this paper we describe the current status of an ongoing research effort to develop a geographic infor- mation system based on quadtrees. Quadtree encod- ings were constructed for area, point and line features from maps and overlays representing a small area of Northern California. The encoding used was a variant of the linear quadtree. A memory management system based on B-trees ~5~ was devised to organize the result- ing collection of leaf nodes, allowing for the use of arbitrary sized maps within a restricted amount of core * The support of the U.S. Army Engineer Topographic Laboratories under Contract DAAK70-81-C-0059 is grate- fully acknowledged. "t To whom correspondence should be addressed. 647 memory. Many database functions were implemented, including map editing capabilities, set operations and region property functions. Further details about this effort can be found in two earlier papers. ~6"7~ The system described in this paper is intended primarily to demonstrate the efficiency of quadtrees as data structures for handling geographical entities. I t is a contribution to geographic information system (GIS) design only on the level of the underlying data structures. Existing GIS's have been primarily based on polygon data structures, which do not lend them- Fig. 1. The landuse map.648 HANAN SAMET et al. •. ~ • . .~-~.~.._ ~__ :" . ;! : , , .... ." ~ ..... [.... , ~_, ..... ~'~ "... " ....~:..,.~ i" i~. !'~i . . " • . ,; :~-~.,~,h' !:., .. .~" "~ "'.~.. .. • y .¢...,..': ...,'. • .. . ..~-'.. Fig. 2. The topography map. : ".7 • -' " - ... / Fig. 4. The house map. t. selves as efficiently as quadtrees to the handling of many types of basic queries. Some recent examples of GIS's can be found in a journal special issue ~s~ and several individual papers. ~9-12) The database used in the study was supplied by the U.S. Army Engineer Topographic Laboratory, Ft. Belvoir, VA. The area data consisted of three registered map overlays representing landuse classes, terrain elevation contours and floodplain boundaries. The overlays were hand-digitized resulting in three arrays of size 400 x 450 pixels. Labels were associated with the pixels in each of the resulting regions, specifying the particular landuse class or elevation range. The regions were subsequently embedded within a 512 x 512 grid and quadtree encoded. The results are shown in Figs 1-3. We also made use of a geographic survey map for this area, from which we extracted point and line data. The house locations were digitized for a point map (Fig. 4), and four line maps were constructed cor- responding to a railroad line, a power line, a city boundary and the road network from the area (Figs 5-8). Fig. 3. The floodplain map. Fig. 5. The railroad map.A geographic information system 649 Fig. 6. The powerline map. The rest of this paper is organized as follows. Section 2 describes the quadtree memory management system for storing and manipulating large quadtrees in exter- nal storage. Section 3 contains an outline of the quadtree editor which enables the interactive con- struction and updating of maps stored as quadtrees. Section 4 discusses the representations that we use for points and linear features. Section 5 gives an outline of the type of operations which we are currently able to perform on our database, while Section 6 describes the query language which we use to interact with the database. Fig. 8. The road map. l THE QUADTREE MEMORY MANAGEMENT SYSTEM Prior to discussing the memory management sys- tem, it is appropriate to briefly review the definition of a region quadtree. Given a 2" x 2" array of pixels, a quadtree is constructed by repeatedly subdividing the array into quadrants, subquadrants .... until we obtain blocks (possibly single pixels) which consist of a single value (e.g. a color). This process is represented by a tree of out degree four in which the root node corresponds to the entire array, the four sons of the root node Fig. 7. The city border map. j=/- ~