Mitered Offsets and Skeletons for Circular Arc Polygons
Abstract
The offsetting process that defines straight skeletons of polygons is generalized to arc polygons, i.e., to planar shapes with piecewise circular boundaries. The offsets are obtained by shrinking or expanding the circular arcs on the boundary in a co-circular manner, and tracing the paths of their endpoints. These paths define the associated shape-preserving skeleton, which decomposes the input object into patches. While the skeleton forms a forest of trees, the patches of the decomposition have a radial monotonicity property. Analyzing the events that occur during the offsetting process is non-trivial; the boundary of the offsetting object may get into self-contact and may even splice. This leads us to an event-driven algorithm for offset and skeleton computation. Several examples (both manually created ones and approximations of planar free-form shapes by arc spline curves) are analyzed to study the practical performance of our algorithm.
References
- 1. , An overview of offset curves and surfaces, Computer-Aided Design 31 (1999) 165. Crossref, Web of Science, Google Scholar
- 2. , Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable, Vol. 1 (Springer Science & Business Media, 2008). Crossref, Google Scholar
- 3. , A simple method for invalid loops removal of planar offset curves, Int. J. Advanced Manufacturing Technology 27 (2006) 1153. Crossref, Web of Science, Google Scholar
- 4. , Trimming local and global self-intersections in offset curves/surfaces using distance maps, Computer-Aided Design 38 (2006) 183. Crossref, Web of Science, Google Scholar
- 5. , Efficient offset trimming for planar rational curves using biarc trees, Computer Aided Geometric Design 29 (2012) 555. Crossref, Web of Science, Google Scholar
- 6. , Efficient offset trimming for deformable planar curves using a dynamic hierarchy of bounding circular arcs, Computer-Aided Design 58 (2015) 248. Crossref, Web of Science, Google Scholar
- 7. , A mapping-based approach to eliminating self-intersection of offset paths on mesh surfaces for CNC machining, Computer Aided Design 62 (2015) 131. Crossref, Web of Science, Google Scholar
- 8. ,
A transformation for extracting new descriptors of shape , in Models for the Perception of Speech and Visual Form, ed. W. Wathen-Dunn (MIT Press, Cambridge, 1967), pp. 362–380. Google Scholar - 9. , Medial axis transformation of a planar shape, IEEE Transactions on Pattern Analysis and Machine Intelligence (1982) 363. Crossref, Web of Science, Google Scholar
- 10. , Approximate medial axis as a Voronoi subcomplex, Computer-Aided Design 36 (2004) 195. Crossref, Web of Science, Google Scholar
- 11. , Spiral arc spline approximation to a planar spiral, J. Comput. Appl. Math. 107 (1999) 21. Crossref, Web of Science, Google Scholar
- 12. , Divide-and-conquer for Voronoi diagrams revisited, Computational Geometry: Theory and Applications 8 (2010) 688. Crossref, Web of Science, Google Scholar
- 13. , Medial axis computation for planar free-form shapes, Computer-Aided Design 41 (2009) 339. Crossref, Web of Science, Google Scholar
- 14. , Computing a compact spline representation of the medial axis transform of a 2D shape, Graphical Models 76 (2014) 252. Crossref, Web of Science, Google Scholar
- 15. , Exact medial axis computation for triangulated solids with respect to piecewise linear metrics, Curves and Surfaces (2010) 1. Google Scholar
- 16. ,
Stability and computation of medial axes — A state-of-the-art report , in Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, eds. B. R. T. Müller and B. Hamann (Springer Series on Mathematics and Visualization, 2008), pp. 109–125. Google Scholar - 17. , Voronoi Diagrams and Delaunay Triangulations (World Scientific, 2013). Link, Google Scholar
- 18. , Mitered offset for profile machining, Computer-Aided Design 35 (2003) 501. Crossref, Web of Science, Google Scholar
- 19. , A novel type of skeleton for polygons, J. Universal Computer Science (1996) 752. Crossref, Google Scholar
- 20. , Straight skeletons for general polygonal figures in the plane, in International Computing and Combinatorics Conference (Springer, 1996), pp. 117–126. Crossref, Google Scholar
- 21. , Weighted straight skeletons in the plane, Computational Geometry 48 (2015) 120. Crossref, Web of Science, Google Scholar
- 22. , A straight skeleton approximating the medial axis, Springer Lecture Notes in Computer Science (2004) 809. Crossref, Google Scholar
- 23. , Straight skeletons and mitered offsets of nonconvex polytopes, Discr. Comput. Geom. 56 (2016) 743. Crossref, Web of Science, Google Scholar
- 24. , Computational and structural advantages of circular boundary representation, Int. J. Comput. Geom. Appl. 21 (2011) 47. Link, Web of Science, Google Scholar
- 25. , On merging straight skeletons, in EuroCG (2018), pp. 263–268. Google Scholar
- 26. , Computational Geometry: Introduction, 3rd edition (Springer, 2008). Crossref, Google Scholar
Remember to check out the Most Cited Articles! |
---|
Check out these titles in image analysis! |