一个有效的多边形裁剪算法

• 作者: 刘勇奎 高云 黄有群
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 计算机图形学 凹多边形 多边形剪裁 交点计算 单链表结构
• 年，卷（期）: 2003,（4）
• 所属期刊栏目: 计算机图形学与计算机辅助设计
• 页码范围: 845-856
• 页数: 12页
• 分类号: TP391
• 字数: 9964字
• 语种: 中文

摘要

多边形裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的"交"(多边形裁剪),而且可以求多边形的"并"和"差".它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄有群	沈阳工业大学信息科学与工程学院	56	798	14.0	26.0
2	刘勇奎	大连民族学院计算机科学与工程系	52	566	11.0	22.0
3	高云	沈阳工业大学信息科学与工程学院	3	124	3.0	3.0