一种处理交点退化现象的高效多边形裁剪算法

摘要：

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

关键词：多边形裁剪、交点退化、单向链表、方向关系

所属期刊栏目：46

分类号：TP391(计算技术、计算机技术)

资助基金：“十二五”国家科技支撑计划资助项目2013BAJ13B01.

在线出版日期：2016-09-28（万方平台首次上网日期，不代表论文的发表时间）

页码：702-707