上机实读验3：图形填充与裁剪算法的具体实现.doc

计算机图形学课程实验 报 告 实验题目 填充与裁剪算法的实现 班 级 计算091 姓 名 王姣 学 号 3090811002 指导教师 胡钢 日 期 2012-5-3 西安理工大学理学院应用数学系 二零零八年春季学期 (实验说明 试验目的： 掌握图形填充与裁剪算法的基本思想，并能上机编程实现相应的算法。。 试验地点： 教九楼401 数学系机房 实验要求(Direction): 1.每个学生单独完成；2.开发语言为TurboC或C++，也可使用其它语言；3.请在自己的实验报告上写明姓名、学号、班级；4.每次交的实验报告内容包括：题目、试验目的和意义、程序制作步骤、主程序、运行结果图以及参考文件；5. 自己保留一份可执行程序,考试前统一检查和上交。 (实验内容 (实验题一 1.1实验题目 上机编程序实现多边形区域填充算法。要求：(1)多边形要求采用顶点表示，且顶点的个数和顶点坐标可以随机输入；(2)要求先画出多边形，画出多边形的同时要求标明各顶点坐标；(3)水平扫描线的顺序和填充颜色可以自由选择。 1.2实验目的和意义 1.熟悉并掌握编程实现多边形的画法 2.学会画出多边形的同时要求标明各顶点坐标的算法如何在程序中实现 3.了解如何对多边形进行扫描变换 4.了解如何对多边形进行扫描区域填充 1.3程序制作步骤(包括算法的基本思想、流程图、设计步骤等) 算法思想： 多边形以n, x_array, y_array形式给出，其中x_array，y_array中存着多边形的n个顶点的x, y坐标。扫描线填色算法的基本思想是：用水平扫描线从上到下扫描由点线段构成的多段定义的多边形。每根扫描线与多边形各边产生一系列交点，将这些交点按照x坐标进行排序，将排序后的交点成对取出，作为两个端点，用所需填充的色彩画水平直线。多边形被扫描完毕，则填充结束 扫描线算法的实现思想： （1）根据给出的顶点坐标数据，按y递增顺序建立ET表。 （2）根据AET指针，使之为空。 （3）使yi=ymin（ymin为顶点坐标中最小y值）。 （4）反复做下述各步，直至yi=ymax(顶点坐标中y的最大值)或ET或AET为空。 1. 将ET表加入到AET中,并保持AET链中的记录按x值增大排序； 2. 对扫描线yi依次成对取出AET中xi值,并在每对xi之间填上所要 求的颜色或图案； 3. 从AET表中删去yi+1的边记录； 4. 对保留下来的AET中的每个边记录, x域中的值用xi+1/m代替 xi,并重新按x递增排序； 5. 使yi+1,以便进入下一轮循环。 多边形的填充过程,对于一条扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间； （4）填色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 1.4主程序 /*坐标系：屏幕左上角为原点，向下为纵坐标正方向*/ /*可修改多边形边数polydeflen和多边形按顺时针的顶点定义polydef来改变多边形*/ #includegraphics.h/*加入c图形库*/ #includestdio.h #includemath.h/*数学库*/ #includeconio.h/*键盘控制*/ #define MP 100/*多边形边数*/ #includestdlib.h #define false 0 void edge_mark(int arr[][2],int value,int polydeflen)/*多边形直线扫描变换*/ { int by,x,y,ax,ay;/*by为上点纵坐标，x、y当前点横、纵坐标，ax、ay下点横、纵坐标*/ int i,j; float k;/*k为直线斜率的倒数*/ by=arr[polydeflen-1][1]; for (i=0;ipolydeflen;i++) { if (i == polydeflen-1) { ax=arr[0][0]; ay=arr[0][1]; } else { ax=arr[i+1][0]; ay=arr[i+1][1]; } x=arr[i][0]; y=arr[i][1]; if((y-ay)!=0) k=(ax-x)/(float)(y-ay);/*向下为纵坐标正方向，所以为y-ay*/ if((