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

• 作者: 崇素文 王慧青
• 来源期刊: 东南大学学报（自然科学版）
• 学科: 工学
• 关键词: 多边形裁剪 交点退化 单向链表 方向关系
• 年，卷（期）: 2016,（4）
• 页码范围: 702-707
• 分类号: TP391
• 字数: 3783字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0505.2016.04.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王慧青	东南大学仪器科学与工程学院	30	187	6.0	12.0
2	崇素文		1	4	1.0	1.0