Abstract
A splinegon is a polygon whose edges have been replaced by “well-behaved” curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Chazelle and D. P. Dobkin, Optimal convex decompositions, inMachine Intelligence and Pattern Recognition 2: Computational Geometry(G. T. Toussaint, ed.), Elsevier Science, North Holland, Amsterdam, 1985, pp. 63–133.
B. Chazelle and D. P. Dobkin, Intersection of convex objects in two and three dimensions,J. Assoc. Comput. Mach.,34 (1987), 1–27.
B. Chazelle and J. Incerpi, Triangulation and shape-complexity,ACM Trans. Graphics,3 (1984), 135–152.
J. Dugundji,Topology, Allyn and Bacon, Reading, MA, 1966.
H.-Y. F. Feng and T. Pavlidis, Decomposition of polygons into simpler components: feature generation for syntactic pattern recognition,IEEE Trans. Comput.,24 (1975), 636–650.
A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Trans. Graphics,3 (1984), 153–174.
D. H. Greene, The decomposition of polygons into convex parts, inAdvances in Computing Research (F. P. Preparata, ed.), Vol. 1, JAI Press, Greenwich, CT, 1983, pp. 235–259.
J. Hershberger, private communication.
J. G. Hocking and G. S. Young,Topology, Addison-Wesley, Reading, MA, 1961.
K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, Sorting Jordan sequences in linear time using level-linked search trees,Inform, and Control,68 (1986), 170–184.
J. M. Keil, Decomposing a polygon into simpler components,SIAM J. Comput.,14 (1985), 799–817.
J. M. Keil and J. R. Sack, Minimum decompositions of polygonal objects, inMachine Intelligence and Pattern Recognition 2: Computational Geometry (G. T. Toussaint, ed.), Elsevier Science, North Holland, Amsterdam, 1985, pp. 197–216.
D. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput.,12 (1983), 28–35.
D. T. Lee and F. P. Preparata, Location of a point in a planar subdivision and its applications,SIAM J. Comput.,6 (1977), 594–606.
D. T. Lee and F. P. Preparata, Computational geometry—a survey,IEEE Trans. Comput.,33 (1984), 1072–1101.
S. Lefschetz,Introduction to Topology, Princeton University Press, Princeton, NJ, 1949.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
B. Schachter, Decompositions of polygons into convex sets,IEEE Trans. Comput.,27 (1978), 1078–1082.
A. A. Schäffer and C. J. Van Wyk, Convex hulls of piecewise-smooth Jordan curves,J. Algorithms,8 (1987), 66–94.
M. I. Shamos and D. Hoey, Geometric intersection problems,Proceedings of the 17th Annual IEEE Symposium on Foundations of Computer Science, Houston, TX, 1976, pp. 208–215.
D. L. Souvaine, Computational geometry in a curved world, Ph.D. Dissertation, Princeton University, 1986.
R. E. Tarjan and C. J. Van Wyk, AnO(n log logn)-time algorithm for triangulating simple polygons,SIAM J. Comput. (to appear).
C. J. Van Wyk, Clipping to the boundary of a circular-arc polygon,Comput. Vision Graphics Image Process.,25 (1984), 383–392.
Author information
Authors and Affiliations
Additional information
Communicated by D. T. Lee.
Work on this paper by David A. Dobkin and Diane L. Souvaine was partially supported by National Science Foundation Grants MCS 83-03926 and DCR 85-05517. Diane L. Souvaine was also partially supported by an Exxon Foundation Fellowship.
Rights and permissions
About this article
Cite this article
Dobkin, D.P., Souvaine, D.L. & Van Wyk, C.J. Decomposition and intersection of simple splinegons. Algorithmica 3, 473–485 (1988). https://doi.org/10.1007/BF01762127
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01762127