多边形OFFSET中无效环的去除算法

对于多边形OFFSET后产生的自交环现象,提出一种求解自交点的基于单调链的平面扫描算法,并对环的判别提出了一种简便而有效的方法。最后,对算法的时间复杂度进行了分析。实验表明,该算法高效而稳定地处理多边形OFFSET后产生的自交环。

一个多边形快速等距偏移方法

多边形的等距偏移是CAD/CAM领域中的一个基础性问题 ,是型腔环切加工刀具轨迹生成的关键。根据无效环在原始多边形上的对应连续线段必有一凸或凹点 ,从多边形的凸点和干涉凹点出发 ,利用干涉边的连贯性逐步确定无效环 ,最后对多边形中的非干涉区域作等距偏移 ,实现多边形的等距偏移。该方法利用干涉区域的连贯性避免了大量不必要的求交计算 ,同时支持带有孤岛的多边形等距偏移。其算法复杂度接近于O(n) ,其中n为多边形顶点个数。