Re2l: An efficient output-sensitive algorithm for computing Boolean operations on circular-arc polygons and its applications

详细信息    查看全文

• 作者：Zhi-Jie Wang^a ; ^b ; ^{cszhijwang@comp.polyu.edu.hk} ; Xiao Lin^c ; ^{lin6008@126.com} ; Mei-E Fang^d ; ^{fme@hdu.edu.cn} ; Bin Yao^a ; ^{yaobin@cs.sjtu.edu.cn} ; Yong Peng^d ; ^{standy.peng@gmail.com} ; Haibing Guan^a ; ^{hbguan@cs.sjtu.edu.cn} ; Minyi Guo^a ; ^{guo-my@cs.sjtu.edu.cn}
• 关键词：Boolean operations ; Circular-arc polygons ; Related edges ; Sequence lists ; Appendix points
• 刊名：Computer-Aided Design
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：83
• 期：Complete
• 页码：1-14
• 全文大小：913 K
• 卷排序：83

文摘

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.