Storing a collection of polygons using quadtrees

ABSTRACT

An adaptation of the quadtree data structure that represents polygonal maps (i.e., collections of polygons, possibly containing holes) is described ina manner that is also useful for the manipulation of arbitrary collections of straight line segments. The gol is to store these maps without the loss of information that results from digitization, and to obtain a worst-case execution time that is not overly sensitive to the positioning of the map. A regular decomposition variant of the region quadtree is used to organize the vertices and edges of the maps. A number of related data organizations are proposed in an iterative manner until a method is obtained that meets the stated goals. The result is termed a PM (polygonal map) quadtree and is based on a regular decomposition point space quadtree (PR quadtree) that stores additional information about the edges at its terminal nodes. Algorithms are given for inserting and deleting line segments from a PM quadtree. Use of the PM quadtree to perform point location, dynamic line insertion, and map overlay is discussed. The PM quadtree is compared conceptually to the K-structure and the layered dag with respect to typical cartographic data. An empirical comparison of the PM quadtree with other quadtree-based representations for polygonal maps is also provided.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BENT, S. W., SLEATOR, D. D., AND TARJAN, R.E. Biased 2-3 trees. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (October, Syracuse, New York), IEEE, New York, 1980, pp. 248-254.
• 3: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 4: Herbert Edelsbrunner, Key-Problems and Key-Methods in Computational Geormetry, Proceedings of the Symposium of Theoretical Aspects of Computer Science, p.1-13, April 11-13, 1984
• 5: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 6: FINKEL, R. A., AND BENTLEY, J.L. Quad trees: A data structure for retrieval on composite keys. Acta Informatica 4, 1 (1974), 1-9.
• 7: HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 8: Stefan Hertel , Kurt Mehlhorn, Fast Triangulation of Simple Polygons, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.207-218, August 21-27, 1983
• 9: Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
• 10: HUNTER, G. M., AND STEIGLITZ, K. Operations on images using quad trees. IEEE Trans. Pattern Anal. and Mach. InteU. 1, 2 (Apr. 1979), 145-153.
• 11: KIRKPATRICK, D. Optimal search in planar subdivisions. SIAM J. Comput. 12, 1 (Feb. 1983), 28-35.
• 12: KLINGER, A. Patterns and search statistics. In Optimizing Methods in Statistics, J. S. Rustagi, Ed. Academic Press, New York, 1971, pp. 303-337.
• 13: MARTIN, J.J. Organization of geographical data with quad trees and least square approximation. In Proceedings of the IEEE Conference on Pattern Recognition and Image Processing (June, Las Vegas), IEEE, New York, 1982, pp. 458-463.
• 14: J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
• 15: ORENSTEIN, J.A. Multidimensional tries used for associative searching. Inf. Process. Lett. 14, 4 (June 1982), 150-157.
• 16: OVERMARS, J. H., AND VAN LEEUWEN, J. Dynamic multi-dimensional data structures based on quad- and k-d trees. Acta Informatica 17, (1982), 267-287.
• 17: SAMET, H., AND WEBBER, R.E. Using quadtrees to represent polygonal maps. In Proceedings of Computer Vision and Pattern Recognition 83 (June, Washington, D.C.), IEEE, New York, 1983, pp. 127-132 (also University of Maryland, Computer Science Dept. TR-1372).
• 18: SAMET, H., AND WEBBER, R.E. On encoding boundaries with quadtrees. IEEE Trans. Pattern Anal. and Mach. Intell. 6, 3 (May 1984), 365-369.
• 19: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 20: SAMET, H., ROSENFELD, A., SHAFFER, C. A., AND WEBBER, R.E. A geographic information system using quadtrees. Pattern Recog. 17, 6 (Nov./Dec. 1984), 647-656.
• 21: SHNEIER, M. Two hierarchical linear feature representations: Edge pyramids and edge quadtrees. Comput. Graph. and Image Process. 17, 3 (Nov. 1981), 211-224.
• 22: TAMMINEN, M. The EXCELL method for efficient geometric access to data. Acta Polytechnica Scandinavica, Mathematics and Computer Science Series No. 34, Helsinki, 1981.
• 23: Robert Edward Webber, Analysis of quadtree algorithms (graphics), 1983

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Modeling packages; Geometric algorithms, languages, and systems
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning
      I.4.7 Feature Measurement
          Subjects: Size and shape

General Terms:
Algorithms

Keywords:
geographic information, hierarchical data structures, line representations, map overlay, polygonal representations, quadtrees