Please use this identifier to cite or link to this item: `http://hdl.handle.net/10397/65644`
 Title: RE2L : an efficient output-sensitive algorithm for computing boolean operations on circular-arc polygons and its applications Authors: Wang, ZJLin, XFang, MEYao, BPeng, YGuan, HGuo, M Keywords: Appendix pointsBoolean operationsCircular-arc polygonsRelated edgesSequence lists Issue Date: 2017 Publisher: Elsevier Source: CAD computer aided design, 2017, v. 83, p. 1-14 How to cite? Journal: CAD computer aided design 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)logl) 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. URI: http://hdl.handle.net/10397/65644 ISSN: 0010-4485 DOI: 10.1016/j.cad.2016.07.004 Appears in Collections: Journal/Magazine Article

#### SCOPUSTM Citations

2
Last Week
0
Last month
Citations as of Feb 13, 2019

#### WEB OF SCIENCETM Citations

2
Last Week
0
Last month
Citations as of Feb 17, 2019

#### Page view(s)

50
Last Week
3
Last month
Citations as of Feb 19, 2019