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, ZJ
Lin, X
Fang, ME
Yao, B
Peng, Y
Guan, H
Guo, M
Keywords: Appendix points
Boolean operations
Circular-arc polygons
Related edges
Sequence 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

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

11
Last Week
1
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.