区域划分在自相交多边形分解算法中的应用
Application of Region Division in Self Intersecting Polygon Decomposition Algorithm
-
摘要: 多边形分解在计算机图形学、CAD软件和路径规划等领域中得到广泛应用.其自相交多边形因存在交点导致后续计算和绘图操作中的错误和不准确性.自相交多边形分解算法是CAD应用中常见的难题之一,传统的自相交多边形分解算法主要基于三角剖分的方法,然而这种方法分解出的三角形数量较为庞大,增加了计算和存储的复杂度.针对自相交多边形的分解问题,提出了一种基于区域划分的分解算法.首先寻找多边形的所有交点;然后采用寻路方式遍历自相交多边形,将其划分为无重叠且无自相交的区域;最后通过判断每个区域是否属于多边形内部,并保留内部区域,舍弃外部区域,将自相交多边形分解成无重叠区域的简单多边形.在多个大型集成电路板上将文中算法和GluTess方法进行数值实验对比,实验结果表明,该算法相较于GluTess方法在时间效率上提高了约60%,同时在空间占用上也减少了约20%.Abstract: 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%.