A GEOGRAPHIC INFORMATION SYSTEM USING QUADTREES (10 pages)

Previewing pages 1, 2, 3 of 10 page document View the full content.
View Full Document

A GEOGRAPHIC INFORMATION SYSTEM USING QUADTREES



Previewing pages 1, 2, 3 of actual document.

View the full content.
View Full Document
View Full Document

19 views

Unformatted text preview:

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 H A N A N SAMET f A Z R I E L ROSENFELD CLIFFORD A SHAEFER a n d ROBERT E WEBBER Computer ScienceDepartment and Center for Automation Research Universityof Maryland College Park MD 20742 U S A Received 13 December 1983 in revisedform 28 February 1984 receivedfor 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 I I N T R O D U C T I O N 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 representations 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 implemented 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 quadtree 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 information system based on quadtrees Quadtree encodings 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 resulting collection of leaf nodes allowing for the use of arbitrary sized maps within a restricted amount of core Image processing Region representation 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 The support of the U S Army Engineer Topographic Laboratories under Contract DAAK70 81 C 0059is gratefully acknowledged tTo whom correspondence should be addressed Fig 1 The landuse map 647 648 HANAN SAMET et al i i i y h 7 Fig 3 The floodplain map t Fig 4 The house map Fig 2 The topography map 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 corresponding to a railroad line a power line a city boundary and the road network from the area Figs 5 8 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 external storage Section 3 contains an outline of the quadtree editor which enables the interactive construction 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 QUADTREEMEMORY MANAGEMENT SYSTEM Prior to discussing the memory management system it is appropriate to briefly review the definition o f 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 F G j Iolololoi I I I I oloo1 o M i Sr o o o o p 0 0 I Reglon I o I O0 b Binaray array A 0 U 0 C Block decomposition of he region in 0 8Locks in the image re shaded N W s S E C D 37 38 39 40 E 57 58 59 60 d Ouadtree representation of he bl ocks in C Fig 7 The city border map PR17 8 E Fig 9 A region its binary array its maximal blocks and the corresponding quadtree 650 HANAN SAMET et al o 7 222 223 232 233 322 323 332 333 6 22G 221 230 231 32G 321 330 331 5 202 203 212 213 302 303 312 313 4 20 201 2 0 211 30C 301 310311 3 022 D23 032 033 122 123 132 133 2 02C 021 030 031 120 121 130 131 I 002 00 3 I 012


Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view A GEOGRAPHIC INFORMATION SYSTEM USING QUADTREES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A GEOGRAPHIC INFORMATION SYSTEM USING QUADTREES and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?