World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Mitered Offsets and Skeletons for Circular Arc Polygons

    https://doi.org/10.1142/S0218195921500023Cited by:1 (Source: Crossref)

    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. T. Maekawa, An overview of offset curves and surfaces, Computer-Aided Design 31 (1999) 165. Crossref, Web of ScienceGoogle Scholar
    • 2. R. T. Farouki, Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable, Vol. 1 (Springer Science & Business Media, 2008). CrossrefGoogle Scholar
    • 3. Y.-L. Lai, J.-S. Wu, J.-P. Hung and J.-H. Chen, A simple method for invalid loops removal of planar offset curves, Int. J. Advanced Manufacturing Technology 27 (2006) 1153. Crossref, Web of ScienceGoogle Scholar
    • 4. J.-K. Seong, G. Elber and M.-S. Kim, Trimming local and global self-intersections in offset curves/surfaces using distance maps, Computer-Aided Design 38 (2006) 183. Crossref, Web of ScienceGoogle Scholar
    • 5. Y.-J. Kim, J. Lee, M.-S. Kim and G. Elber, Efficient offset trimming for planar rational curves using biarc trees, Computer Aided Geometric Design 29 (2012) 555. Crossref, Web of ScienceGoogle Scholar
    • 6. J. Lee, Y.-J. Kim, M.-S. Kim and G. Elber, Efficient offset trimming for deformable planar curves using a dynamic hierarchy of bounding circular arcs, Computer-Aided Design 58 (2015) 248. Crossref, Web of ScienceGoogle Scholar
    • 7. J. Xu, Y. Sun and L. Zhang, 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 ScienceGoogle Scholar
    • 8. H. Blum, 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. D.-T. Lee, Medial axis transformation of a planar shape, IEEE Transactions on Pattern Analysis and Machine Intelligence (1982) 363. Crossref, Web of ScienceGoogle Scholar
    • 10. T. K. Dey and W. Zhao, Approximate medial axis as a Voronoi subcomplex, Computer-Aided Design 36 (2004) 195. Crossref, Web of ScienceGoogle Scholar
    • 11. D. Meek and D. Walton, Spiral arc spline approximation to a planar spiral, J. Comput. Appl. Math. 107 (1999) 21. Crossref, Web of ScienceGoogle Scholar
    • 12. O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, E. Pilgerstorfer and M. Rabl, Divide-and-conquer for Voronoi diagrams revisited, Computational Geometry: Theory and Applications 8 (2010) 688. Crossref, Web of ScienceGoogle Scholar
    • 13. O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler and M. Rabl, Medial axis computation for planar free-form shapes, Computer-Aided Design 41 (2009) 339. Crossref, Web of ScienceGoogle Scholar
    • 14. Y. Zhu, F. Sun, Y.-K. Choi, B. Jüttler and W. Wang, Computing a compact spline representation of the medial axis transform of a 2D shape, Graphical Models 76 (2014) 252. Crossref, Web of ScienceGoogle Scholar
    • 15. O. Aichholzer, W. Aigner, F. Aurenhammer and B. Jüttler, Exact medial axis computation for triangulated solids with respect to piecewise linear metrics, Curves and Surfaces (2010) 1. Google Scholar
    • 16. D. Attali, J.-D. Boissonnat and H. Edelsbrunner, 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. F. Aurenhammer, R. Klein and D. T. Lee, Voronoi Diagrams and Delaunay Triangulations (World Scientific, 2013). LinkGoogle Scholar
    • 18. S. C. Park and Y. C. Chung, Mitered offset for profile machining, Computer-Aided Design 35 (2003) 501. Crossref, Web of ScienceGoogle Scholar
    • 19. O. Aichholzer, F. Aurenhammer, D. Alberts and B. Gärtner, A novel type of skeleton for polygons, J. Universal Computer Science (1996) 752. CrossrefGoogle Scholar
    • 20. O. Aichholzer and F. Aurenhammer, Straight skeletons for general polygonal figures in the plane, in International Computing and Combinatorics Conference (Springer, 1996), pp. 117–126. CrossrefGoogle Scholar
    • 21. T. Biedl, M. Held, S. Huber, D. Kaaser and P. Palfrader, Weighted straight skeletons in the plane, Computational Geometry 48 (2015) 120. Crossref, Web of ScienceGoogle Scholar
    • 22. M. Tanase and R. C. Veltkamp, A straight skeleton approximating the medial axis, Springer Lecture Notes in Computer Science (2004) 809. CrossrefGoogle Scholar
    • 23. F. Aurenhammer and G. Walzl, Straight skeletons and mitered offsets of nonconvex polytopes, Discr. Comput. Geom. 56 (2016) 743. Crossref, Web of ScienceGoogle Scholar
    • 24. O. Aichholzer, F. Aurenhammer, T. Hackl, B. Jüttler, M. Rabl and Z. Šír, Computational and structural advantages of circular boundary representation, Int. J. Comput. Geom. Appl. 21 (2011) 47. Link, Web of ScienceGoogle Scholar
    • 25. M. Steinkogler, F. Aurenhammer and R. Klein, On merging straight skeletons, in EuroCG (2018), pp. 263–268. Google Scholar
    • 26. M. De Berg, O. Cheong, M. Van Kreveld and M. Overmars, Computational Geometry: Introduction, 3rd edition (Springer, 2008). CrossrefGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these titles in image analysis!