An Efficient Algorithm for Boolean Operation on Circular-arc Polygons
Zhi Jie Wang, Xiao Lin, Bin Yao, Yongxi Gong, Meie Fang · arXiv (Cornell University) · 2012
In this paper, we investigate the problem of Boolean operation on circular-arc polygons. We present a concise and efficient method, in which the concept of related edges is introduced. Given two circular-arc polygons with M and N edges, respectively, the proposed method only takes O((l+k)∗ log l+M +N) time, where k is the number of intersection points, l is the number of related edges. The proposed method can be easily extended to deal with Boolean operation on traditional polygons.