计算机辅助设计与图形学学报

作者：赵启, 曾薇, 杨义军

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

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

来源：2023年第12期

《计算机辅助设计与图形学学报》期刊编辑部

查看计算机辅助设计与图形学学报杂志2023年第12期