The Quadtree and Related Hierarchical Data Structures HANAN $AMET Computer Science Department, University of Maryland, College Park, Maryland 20742 A tutorial survey is presented of the quadtree and related hierarchical data structures. They are based on the principle of recursive decomposition. The emphasis is on the representation of data used in applications in image processing, computer graphics, geographic information systems, and robotics. There is a greater emphasis on region data {i.e., two-dimensional shapes) and to a lesser extent on point, curvilinear, and three- dimensional data. A number of operations in which such data structures find use are examined in greater detail. Categories and Subject Descriptors: E.1 [Data]: Data Structures--trees; H.3.2 [Information Storage and Retrieval]: Information Storage--file organization; 1.2.1 [Artificial Intelligence]: Applications and Expert Systems--cartography; 1.2.10 [Artificial Intelligence]: Vision and Scene Understanding--representations, data structures, and transforms; 1.3.3 [Computer Graphics]: Picture/Image Generation-- display algorithms; viewing algorithms; 1.3.5 [Computer Graphics]: Computational Geometry and Object Modeling--curve, surface, solid, and object representations; geometric algorithms, languages, and systems; 1.4.2 [Image Processing]: Compression ( Coding)--approximate methods; exact coding; 1.4.7 [Image Processing]: Feature Measurement--moments; projections; size and shape; J.6 [Computer-Aided Engineering]: Computer-Aided Design {CAD) General Terms: Algorithms Additional Key Words and Phrases: Geographic information systems, hierarchical data structures, image databases, multiattribute data, multidimensional data structures, octrees, pattern recognition, point data, quadtrees, robotics INTRODUCTION Hierarchical data structures are becoming increasingly important representation tech- niques in the domains of computer graph- ics, image processing, computational geom- etry, geographic information systems, and robotics. They are based on the principle of recursive decomposition (similar to divide and conquer methods [Aho et al. 1974]). One such data structure is the quadtree. As we shall see, the term quadtree has taken on a generic meaning. In this survey it is our goal to show how a number of data structures used in different domains are related to each other and to quadtrees. This presentation concentrates on these differ- ent representations and illustrates how a number of basic operations that use them are performed. Hierarchical data structures are useful because of their ability to focus on the interesting subsets of the data. This focus- ing results in an efficient representation and improved execution times and is thus particularly useful for performing set op- erations. Many of the operations that we describe can often be performed equally as Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1984 ACM 0360-0300/84/0600-0187 $00.75 Computing Surveys, Voi. 16, No. 2, June 1984188 * Hanan Samet CONTENTS INTRODUCTION 1. OVERVIEW OF QUADTREES 2. REGION DATA 2.1 Neighbor-Finding Techniques 2.2 Alternative Ways to Represent Quadtrees 2.3 Conversion 2.4 Set Operations 2.5 Transformations 2.6 Areas and Moments 2.7 Connected Component Labeling 2.8 Perimeter 2.9 Component Counting 2.10 Space Requirements 2.11 Skeletons and Medial Axis Transforms 2.12 Pyramids 2.13 Quadtree Approximation Methods 2.14 Volume Data 3. POINT DATA 3.1 Point Quadtrees and k-d Trees 3.2 Region-Based Qualities 3.3 Comparison of Point Quadtrees and Region-Based Quadtrees 3.4 CIF Quadtrees 3.5 Bucket Methods 4. CURVILINEAR DATA 4.1 Strip Trees 4.2 Methods Based on a Regular Decomposition 4.3 Comparison 5. CONCLUSIONS ACKNOWLEDGMENTS REFERENCES A v efficiently, or more so, with other data structures. However, hierarchical data structures are attractive because of their conceptual clarity and ease of implemen- tation. As an example of the type of problems to which the techniques described in this sur- vey are applicable, consider a cartographic database consisting of a number of maps and some typical queries. The database contains a contour map, say at 50-foot ele- vation intervals, and a land use map clas- sifying areas according to crop growth. Our wish is to determine all regions between 400- and 600-foot elevation levels where wheat is grown. This will require an inter- section operation on the two maps. Such an analysis could be rather costly, depend- ing on the way the data are represented. For example, areas where corn is grown are of no interest, and we wish to spend a minimal amount of effort searching such regions. Yet, traditional region representa- tions such as the boundary code [Freeman 1974] are very local in application, making it difficult to avoid examining a corn-grow- ing area that meets the desired elevation criterion. In contrast, hierarchical methods such as the region quadtree are more global in nature and enable the elimination of larger areas from consideration. Another query might be to determine whether two roads intersect within a given area. We could check them point by point, but a more efficient method of analysis would be to represent them by a hierarchical sequence of enclosing rectangles and to discover whether in fact the rectangles do overlap. If they do not, then the search is termi- nated, but if an intersection is possible, then more work may have to be done, de- pending on which method of representation is used. A similar query can be constructed for point data--for example, to determine all cities within 50 miles of St. Louis that have a population in excess of 20,000 peo- ple. Again, we could check each city indi- vidually, but using a representation that decomposes the United States into square areas having sides of length 100 miles would mean that at most four squares need to be examined. Thus California and its adjacent states can be safely ignored. Finally,
View Full Document
Unlocking...