一种凹多边形凸分解的全局剖分算法

贺怀清，杨 鹏

（中国民航大学计算机科学与技术学院，天津 300300）

在现有的较为成熟的扫描算法当中，轮廓偏置扫描算法[1]由于不需要频繁开关激光器，且扫描中不断改变方向，能够获得较好的精度。但是由于在偏置的过程中，要不断地检查环自交、环相交等情况，因此算法效率不高。对此，不少学者提出结合计算几何当中的凹多边形凸分解算法[2-5]将多边形[6]分解为多个凸多边形，再分别对每个凸多边形进行轮廓偏置的算法。

文献[2]中通过对凹点进行分类及编码，有效地减少了简单多边形的个数，但是编码较为复杂；文献[3]对文献[2]进行了改进，提出了在凹点的可视点对之间通过权函数来进行剖分；文献[4]在Rogers.F.David提出的经典算法之上提出了基于顶点可见性的剖分算法，根据当前凹点的权函数来进行剖分，结果不够全面；文献[5]提出了一种较为简化的可视点串求取算法，并在改进了的权函数基础之上进行剖分，效果较好。

本文首先对局部剖分算法的原理及存在的问题进行了阐述，并对基于正负法搜索可视点串的算法进行了更正和改进，然后利用改进的权函数从全局剖分的角度选择最优的剖分点进行剖分，优化了简单多边形的形态质量。通过在各个子轮廓上进行轮廓偏置扫描，得到了较好的实验结果。

1 基本概念与定义

定义2 若多边形P的顶点序列p1，p2，…，pn按照逆时针方向排列，并且点pi+1在pi-1pi的左（右）侧，则称点pi为凸（凹）点[6]。以凸（凹）点为顶点的内角≤π（＞π）。

定义3 可视点[7]：对于多边形的任意顶点s来说，多边形中所有顶点与s连线形成的线段，若全部在多边形内部或者边上面，则称s为可视点。……