带圆弧的广义多边形布尔运算
Boolean operations on generalized polygons with arcs
-
摘要: 在实际应用中, 对带圆弧的广义多边形执行布尔运算是一类常见的问题. 一个自然的解决方案是: 先将圆弧段离散成一系列线段, 然后再利用传统多边形的布尔运算算法, 例如Vatti算法, 来获得布尔运算的结果. 然而, 这样的方案明显存在精度低、速度慢等问题. 本文采用另一解决思路: 直接对带圆弧的广义多边形执行布尔运算. 首先, 我们对圆弧进行分裂、积极边排序和环绕数计算, 通过奇偶填充规则确定输出区域. 然后, 基于扫描线算法对两个输入图形进行逐层处理. 在一个扫描区域内, 利用包围盒排序算法进行碰撞检测, 快速排除无交的情况(加速比为1.52), 完成交点计算. 最后, 执行交点检测、交点处理、扫描区域顶部处理等步骤, 得到布尔运算结果的广义多边形. 大量实验结果表明, 本文算法相较于现有算法, 不仅精度更高, 而且速度更快, 在500个测试案例中加速比为3.01.Abstract: In real applications, performing Boolean operations on generalized polygons with arcs is a common problem. A conventional solution is to discretize the arc segments into a sequence of line segments, and then apply traditional polygon Boolean operation algorithms, such as the Vatti algorithm, to obtain the Boolean operation results. Nevertheless, this method exhibits significant drawbacks in terms of reduced accuracy and diminished speed. This paper introduces an alternative solution: conducting Boolean operations directly on generalized polygons with arcs. Initially, we split the arcs, sort active edges, and compute winding numbers to determine the output area using the even-odd fill rule. Subsequently, we process the two input shapes in a layer by layer fashion based on the scanline algorithm. Within a scan region, we employ the bounding box sorting algorithm for collision detection to quickly eliminate non-intersecting cases (with a speedup of 1.52) and complete intersection point calculations. Finally, we perform intersection point detection, intersection point processing, and top-of-scan region handling steps to obtain the resulting generalized polygon. Comprehensive experimental results show that, in comparison to existing algorithms, the proposed algorithm not only has higher accuracy but also faster speed, with a speedup of 3.01 in 500 test cases.