全文总字数：3127字

1. 研究目的与意义及国内外研究现状

线段裁剪是计算机图形学的基本问题之一，裁剪的原理虽然比较简单，但是对裁剪的速度有非常高的要求。例如，一条线段的裁剪需要5毫秒，那么裁剪10条线段所需要的时间，就超过了人眼的容忍度，因此在复杂的图形显示中，人眼就会察觉到扭曲变形的问题，因此，提高裁剪算法的效率都极为重要。裁剪算法的效率关键在于：尽量有效地识别裁剪线段是否与窗口边界相交，以减少求交运算。

裁剪算法是计算机图形学中的基本算法，经过了几十年的讨论和探索，尽管现有的裁剪和直线生成算法越来越完善，但有些算法仍待改进。任意多边形窗口的线段裁剪和圆裁剪在计算机图形学裁剪中具有重要的地位，提高其裁剪的效率具有重要的意义。本课题主要研究任意多边形窗口的线段裁剪和圆裁剪算法，以及在处理海量被裁剪线段和圆时，对算法进行改进，以提高了算法的执行效率。

线段裁剪部分采用坐标系转换的思想来求取被裁剪线段与多边形窗口的交点以及基于数组赋值的方法进行绘图来提高效率。它无需将多边形分解，也不需进行窗口的凹凸性检查。即该算法对于矩形、凸多边形窗口是通用的。此算法对共边的处理十分简单、方便，从而保证了算法的快速、高效。

2. 研究的基本内容

在计算机图形学中，为了描述图形对象，我们必须存储它的全部信息，但有时为了达到分区描述或重点描述某一部分的目的，往往将要描述的部分置于一个窗口内，而将窗口外的部分“剪掉”，这个处理过程叫做裁剪，裁剪在计算机图形处理中具有十分重要的意义。

具体研究内容如下：

实现一个可执行程序，该程序能实时高效地实现百万级线段与圆在任意多边形边界中的快速裁剪显示

3. 实施方案、进度安排及预期效果

2015年11月：资料收集，学习和掌握计算机图形学裁剪与绘图的相关基本知识、完成任务书和开题报告；

2015年12月~2016年1月：改进任意多边形窗口的线裁剪和圆裁剪算法，并对原算法进行改进，以提高算法在海量数据条件下的执行效率

2016年2月~3月：完成算法实现与性能测试；

4. 参考文献

[1]刘勇奎.一般多边形窗口的线裁剪.计算机辅助设计与图形学学报,1993,5(4):269-274

[2]刘勇奎.一个有效的多边形窗口的线裁剪算法.计算机学报，1999，22(ll):1209-1214

[3]蔡志杰.一般多边形的切割.计算机辅助设计与图形学学报，1998，10(3):248-252