Application of Region Division in Self Intersecting Polygon Decomposition Algorithm

Polygon decomposition has been widely employed in the fields of computer graphics, CAD software, and path planning. The presence of self-intersections in polygons introduces errors and inaccuracies in subsequent computations and drawing operations. Decomposing self-intersecting polygons poses a common challenge in CAD applications. Traditional algorithms rely on triangulation techniques. However, this approach yields a substantial number of triangles, significantly elevating both computational and storage complexities. In response to the issue of self-intersecting polygon decomposition, a decomposition algorithm based on region partitioning is proposed. The approach begins by identifying all intersection points within the polygon. Then, a pathfinding technique is employed to traverse the self-intersecting polygon, partitioning it into non-overlapping and self-intersection-free regions. Finally, by discerning the inclusion of each region, internal areas are preserved, while external ones are discarded. This process results in a decomposition of the self-intersecting polygon into non-overlapping simple polygons. Comparative experiments with the GluTess method on large integrated circuit boards reveal that our algorithm improves time efficiency by around 60% and reduces spatial occupancy by about 20%. © 2023 Institute of Computing Technology. All rights reserved.