区域划分在自相交多边形分解算法中的应用  

Application of Region Division in Self Intersecting Polygon Decomposition Algorithm

作　　者：赵启 曾薇 杨义军 Zhao Qi;Zeng Wei;Yang Yijun(School of Mathematics and Statistics,Xi’an Jiaotong University,Xi’an 710049;School of Computer Science and Technology,Xi’an Jiaotong University,Xi’an 710049)

机构地区：[1]西安交通大学数学与统计学院,西安710049 [2]西安交通大学计算机科学与技术学院,西安710049

出　　处：《计算机辅助设计与图形学学报》2023年第12期1910-1919,共10页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家重点研发计划(2021YFA1003002);国家自然科学基金(12090021,61872224)。

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

关 键 词：自相交多边形 多边形分解 凸多边形 区域划分 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]