A consistent hierarchical representation for vector data

ABSTRACT

A consistent hierarchical data structure for the representation of vector data is presented. It makes use of a concept termed a line segment fragment to prevent data degradation under splitting or clipping of vector primitives. This means that the insertion and subsequent deletion (and vice versa) of a vector leaves the data unchanged. Vectors are represented exactly and not as digital approximations. The data is dynamically organized by use of simple probabilistic splitting and merging rules. The use of the structure for implementing a geographic information system is described. Algorithms for constructing and manipulating the structure are provided. Results of empirical tests comparing the structure to other representations in the literature are given.

REFERENCES

• 1: D. Ayala , P. Brunet , R. Juan , I. Navazo, Object representation by means of nonminimal division quadtrees and octrees, ACM Transactions on Graphics (TOG), v.4 n.1, p.41-59, Jan. 1985 [doi>10.1145/3973.3975]
• 2: Jon L Bentley, A survey of techniques for fixed radius near neighbor searching., Stanford University, Stanford, CA, 1975
• 3: {Carl85}- I. Carlbom, I. Chakravurty, and D. Vanderschel, A hierarchical data structure for representing the spatial decomposition of 3-D objects, IEEE Computer Graphics and Applicalions 5, 4(April 1985), 24-31.
• 4: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 5: {Fink74} - B.A. Finkel and J.L. Bentley, Quad trees: a data structure for retrievM on composite keys, Acta Information 4, 1(1974), 1-9.
• 6: {Fuji85} - K. Fujimura and T.L. Kunii, A hierarchical space indexing method, Proceedings of Computer Graphics '85, Tokyo, 1985, T1-4, 1-14.
• 7: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 8: {Hunt79} - G.M. Hunter and K. Steiglilz, Operations on images using quad trees, IEEE Transactions on Pattern Analysis and Machine Tntelligence 1, 2(April 1979), 145-153.
• 9: {Klin71}- A. Klinger, Patterns and Search Statistics, in Optimizing Methods in Statistics, J.S. Rustagi, Ed., Academic Press, New York, 1971, 303-337.
• 10: {Rose83} - A. Rosenfeld, H. Samet, C. Shaffer, and R.E. Webber, Application of hierarchical data structures to geographical information systems phase II, Computer Science TR 1327, University of Maryland, College Park, MD, September 1983.
• 11: {Same84a}- H. Samet and R.E. Webber, On encoding boundaries with quadtrees, IEEE Transactions on Pattern Analysis and Machine Intelligence 6,'3(May 1984), 365-369.
• 12: 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]
• 13: {Same85a} H. Samet and M. Tamminen, Efficient component, labeling of images of arbit, rary dimension, Computer Science TR-1480, University of Maryland, College Park, MD, February 1985.
• 14: {Same85b} H. Sumet., C.A. Shuffer, and R.E. Webber, The segment quadtree: a linear quadtree-based representation for linear features, Proceedings of Computer Vision and Pattern Recognition 85, San Francisco, June 1985, 385-389.
• 15: Hanan Samet , Robert E. Webber, Storing a collection of polygons using quadtrees, ACM Transactions on Graphics (TOG), v.4 n.3, p.182-222, July 1985 [doi>10.1145/282957.282966]
• 16: {Same85d}- H. Samet, A. Rosenfcld, C.A. Shaffer, B.C. Nelson, Y-G. Huang, and K. Fujimura, Appiication of hierrchical data structures to geographic information systems: phase IV, Computer Science TR-1578, University of Maryland, CoIlege Park, MD, December 1985.
• 17: {Shne81}- M. Shneier, Calculations of geometric properties using quadtrees, Computer Graphics and Image Processing 16, 3(July 1981), 296-302.
• 18: {Tamm83} - M. Tamminen, Performance analysis of cell based geometric file organizations, Computer Vision, Graphics, and Image Processing 24, 2(November 1983), 168-181.

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems; Curve, surface, solid, and object representations

General Terms:
Algorithms