Boolean operations on generalized polygons with arcs

 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.