Re2l: An efficient output-sensitive algorithm for computing Boolean operations on circular-arc polygons and its applications. (February 2017)

• Record Type: Journal Article
• Authors: Wang, Zhi-Jie; Lin, Xiao; Fang, Mei-E; Yao, Bin; Peng, Yong; Guan, Haibing; Guo, Minyi
• Is Part Of: Computer aided design. Volume 83(2017)
• Page Start: 1
• Page End: 14
• Publication Date: 2017-02
• Subjects: Boolean operations -- Circular-arc polygons -- Related edges -- Sequence lists -- Appendix points; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2016.07.004
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: The boundaries of conic polygons consist of conic segments or second degree curves. The conic polygon has two degenerate or special cases: the linear polygon and the circular-arc polygon. The natural problem–Boolean operations on linear polygons–has been extensively studied. Surprisingly, (almost) no article focuses on the problem of Boolean operations on circular-arc polygons, yet this potentially has many applications. This implies that if there is a targeted solution for Boolean operations on circular-arc polygons, it should be favourable for potential users. In this article, we close the gap by devising a concise data structure and then developing a targeted algorithm called Re2l . Our method is simple, easy-to-implement, but without loss of efficiency. Given two circular-arc polygons with m and n edges respectively, our method runs in O ( m + n + ( l + k ) log l ) time, using O ( m + n + k ) space, where k is the number of intersections, and l is the number of related edges (defined in Section 5 ). Our algorithm has the power to approximate to linear complexity when k and l are small. The superiority of the proposed algorithm is also validated through empirical study. In particular, our method is of independent interest and we show that it can be easily extended to compute Boolean operations of other types of polygons. Highlights: We highlight the circular-arc polygon is one of special cases of the conic polygon, and Boolean operation on circular-arc polygons also has many applications. We devise a concise and easy-to-operate data structure, and develop a targeted algorithm for Boolean operations on circular-arc polygons. While this paper focuses on Boolean operations of circular-arc polygons, we show our techniques can be easily extended to compute Boolean operations of other types of polygons. We provide the rigorous and detailed theoretical analysis for our algorithm. We conduct extensive experiments to demonstrate the efficiency and effectiveness of our solution.