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

作     者：赵启 曾薇 杨义军 Zhao Qi;Zeng Wei;Yang Yijun

作者机构：西安交通大学数学与统计学院西安710049 西安交通大学计算机科学与技术学院西安710049 

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

出 版 物：《计算机辅助设计与图形学学报》 (Journal of Computer-Aided Design & Computer Graphics)

年 卷 期：2023年第35卷第12期

页      码：1910-1919页

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

主 题 词：自相交多边形 多边形分解 凸多边形 区域划分 

学科分类：08[工学] 080203[080203] 0802[工学-机械学] 

核心收录：

D　O　I：10.3724/SP.J.1089.2023.2023-00040

馆 藏 号：203125205...