计算机图形学论文.doc.docVIP

学号： 20145101108 图形学课程设计 学 院 计算机与信息技术学院 专 业 计算机科学与技术 年 级 2014级计科（1）班 姓 名 焦安楠 论文（设计）题目 多边形裁剪算法 指导教师 李然 职称 讲师 2017 年 6 月 1 日 目 录 1．引言 ..................................................................3 2．基本概念与定义........................................................ 4 2.1 多边形的边的方向与内外区域的关系................................. 4 2.2 进点和出点的定义..................................................4 2.3 进点和出点的判定..................................................4 3．算法的数据结构.........................................................4 4．算法描述 ..............................................................5 5.焦点的计算和判断 .......................................................8 6．结论 .................................................................10 参考文献.................................................................11 多边形裁剪算法 学生姓名：焦安楠 学号：20145101108 计算机与信息技术学院 计算机科学与技术专业 指导教师：李然 职称：讲师 摘 要：,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,也可以是凹多边形。该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,占用的空间小特点。其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法。结果表明,新算法具有最简单的结构。 关键词：计算机图形学;凹多边形;多边形剪裁;交点计算;单链表结构 1．引言 在图形系统中,二维裁剪是最为基础、最为常用的操作之一.其典型的应用是在图形的消隐处理等处理求交操作之中.对裁剪算法的研究主要集中在裁剪直线和裁剪多边形两方面.在实用中,多边形裁剪与线剪裁相比具有更高的使用率,因此它是目前裁剪研究的主要课题.多边形裁剪用于裁剪掉被裁剪多边形(又称为实体多边形)位于窗口(又称为裁剪多边形)之外的部分.多边形愈复杂,其裁剪算法就愈难以实现.现有的解决方案或者局限于某一类多边形,或者结构复杂、时间消耗大. 本文提出了一个新的多边形裁剪多边形的有效算法.其中的裁剪多边形和被裁剪多边形都可以是一般多边形,也可以是凹多边形.该算法只使用单线性链表数据结构,所以具有数据结构简单、占用空间少的特点,而且无须事先规定以什么方向输入图形的顶点.另外,该算法使用了一个新的具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.算法最终通过简单的遍历线性链表,可以得到每一个输出多边形. 2．基本概念与定义 为了便于下面对算法的讲解,本节首先介绍有关多边形裁剪的一些基本概念及术语. 2.1 多边形的边的方向与内外区域的关系. 如果多边形的边的方向是顺时针的(即多边形的顶点是以顺时针的顺序输入的),则在沿着多边形的边走时,右侧区域为多边形的内部;相反,如果多边形的边的方向是逆时针的,则在沿着多边形的边走时,左侧区域为多边形的内部. 2.2 进点和出点的定义. 设I是多边形S和C的一个交点,如果S沿着C的边界的方向在I点从C的外部进