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

Algorithm for Removing Invalid Loop of Polygonal OFFSET

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

This paper present a sweep-line algorithm based on monotone chains to find intersections, at the meantime. A simple and effective method is proposed for identifying invalid loops. At the last, the time-complexity of the algorithm is analyzed. Empirical tests show that the proposed algorithm is effective and steady in disposing the loop of offsetting polygons.