论文部分内容阅读
针对复杂多边形裁剪中出现的多边形彼此间重点和重边现象,提出了一种能够处理交点退化现象的高效多边形裁剪算法.该算法利用单向链表实现多边形的存储,同时基于单调链的平面扫描法求解多边形间的交点,减少了多边形顶点的遍历次数和求交次数;对于重点和重边现象,通过交点关联的线段间的方向关系判别交点的进出性;最后更新多边形顶点序列,获取裁剪结果.实验结果表明,该算法能够完成对含内环多边形的裁剪,在交点退化情况下也能获得准确的裁剪结果.且该算法裁剪效率较Greiner-Hormann算法大幅提高,具有很高的执行效率和