Boolean Operations on Generalized Polygons with Arcs

Traditional approaches to Boolean operations on polygons with arcs typically involve discretizing the arcs, leading to issues such as low precision and slow computation speeds. To improve both efficiency and accuracy, this paper proposes a method based on the scanline algorithm to directly perform Boolean operations on generalized polygons with arcs. Initially, we insert split points at the highest (or lowest) points of 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. Experimental tests conducted on 500 industrial machining parts demonstrate that the proposed algorithm achieves not only higher accuracy but also faster computation speeds compared to existing methods, with an average speedup of 3.01 in 500 test cases.