A self-intersecting polygon decomposition algorithm based on region partition

Polygon decomposition has been widely employed in the fields of computer graphics, CAD software, and path planning. In particular, self-intersecting polygons pose a challenge in CAD applications due to the presence of intersection points, which can lead to errors and inaccuracies in subsequent calculations and rendering operations. Traditional algorithms for decomposing self-intersecting polygons primarily rely on triangulation, dividing the self-intersecting polygon into multiple non-overlapping triangles and subsequently merging them into simple polygons. However, this approach results in a substantial number of triangles, increasing the complexity of computation and storage. In this paper, we propose a novel algorithm for decomposing self-intersecting polygons into non-overlapping regions of simple polygons. In contrast to conventional methods, our approach extends the triangulation-based decomposition algorithm to convex polygons. The advantage of this algorithm lies in its ability to preserve the convexity of the original polygon, thereby better retaining the information of the original shape. Additionally, the algorithm reduces the number of generated triangles, thereby lowering the complexity of computation and storage.