实验六 扫描线填充算法

1、实验六扫描线填充算法一、实验目的编写多边形的扫描线填充算法程序，加深对扫描线算法的理解，验证算法的正确性。二、实验任务（2学时）编写多边形的扫描线填充算法程序，利用数组实现AET，考虑与链表实现程序的不同。三、实验内容1、算法对一条扫描线的填充一般分为以下4个步骤：（1）求交：计算扫描线与多边形各边的交点；（2）排序：把扫描线上所有交点按递增顺序进行排序；（3）配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每 对交点代表扫描线与多边形的一个相交区间。（4）着色：把区间内的像素置为填充色。2、成员函数的关系主程序名为fill_area（count, x, y），其中参数x,

2、 y是两个一维数组，存放多边形顶点（共 count个）的x和y坐标。它调用8个子程序，彼此之间的调用关系图1所示为：fill_areasort_on_bigger_srput_in_sides_listfor扫描线update_first_aiid_lastpieces s_x_intersectionssort_on_xswapdraw_linesupdate_sides_list图1 fill_area的程序结构3、算法的程序设计步骤1：创建“S_L_Fill”工程文件；步骤 2：创建类 class： EACH_ENTRY”。在工作区 “S_L_Fill classes”单击右键-3 ne

3、w class” -3选择类型“Generic Class”名 称为 “EACH_ENTRY”，添加成员变量(添加至 “class EACH_ENTRY public:” 之内)： int y_top;float x_int;int delta_y;float x_change_per_scan;步骤3：包含头文件，同时初始化定义多边形顶点数目。在class CS_L_FillView : public Cview”之前添加代码#include EACH_ENTRY.h及“#define MAX_POINT 9”。#define MAX_POINT 9#include EACH_ENTRYh步

4、骤4：在类“class CS_L_FillView”中添加成员变量(鼠标双击工作区“CS_L_FillView”， 代码添加至“class CS_L_FillView : public Cview protected: public:之后”)：EACH_ENTRY sidesMAX_POINT;int xMAX_POINT,yMAX_POINT;int side_count,first_s,last_s,scan,bottomscan,x_int_count;步骤5：利用构造函数“CS_L_FillView:CS_L_FillView(”初始化顶点坐标(鼠标双击 工作区“CS_L_FillVi

5、ew”，代码添加至“CS_L_FillView ()之内”)：x0=200;y0=100;x1=240;y1=160;x=220;y =340;x3=330;y3=100;x4=400;y4=180;x5=300;y5=400;x6=170;y6=380;x7=120;y7=440;x8=100;y8=220;步骤6:在“ class CS_L_FillView”下添加实现不同功能的成员函数。在工作区 “CS_L_FillView”上单击鼠标右键，选择“Add Member Function”，分别完成以下成员函数 的添加：void put_in_sides_list(int entry,in

6、t x1,int y1,int x2,int y2,int next_y)函数说明：put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步 骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按Hy_top的大小在活性 边表中找到该点的合适位置，y值较大者，排在活性边表的靠前位置。void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y)/ entry 为易 U除水平边之后的 第entry条边，x1, y1,为起点，x2, y2为终点，next_y为终点相邻的下一个顶点y坐

7、标 int maxy;float x2_temp,x_change_temp;x_change_temp=(float)(x2-x1)/(float)(y2-y1);/计算 1/kx2_temp=float(x2);if(y2y1)&(y2next_y)/x2,y2 是左顶点，则(x2-1/m,y2-1)终点下缩y2-;x2_temp-=x_change_temp;elseif(y2next_y) /x2,y2 是右顶点，则(x2+1/m,y2+1)终点上缩y2+;x2_temp+=x_change_temp;maxy=(y1y2)?y1:y2;while(entry1)&(maxysides

8、entry-2.y_top)sidesentry-1=sidesentry-2;entry-;/ sides为边数组，边的y_top值越小，在数组中越靠后sidesentry-1.y_top=maxy;sidesentry-1.delta_y=abs(y2-y1)+1;if(y1y2)/ x2,y2为右顶点，扫描线与起点先求交sidesentry-1.x_int=float(x1);else/ x2,y2左顶点，扫描线与终点先求交sidesentry-1.x_int=x2_temp;sidesentry-1.x_change_per_scan=x_change_temp;void sort_o

9、n_bigger_y(int n,CDC* pDC)函数说明：sort_on_bigger_y子程序的主要功能是按照输入的多边形，建立起活性边表。 操作步骤是：对每条边加以判断：如非水平边则调用put_in_side_list子程序放入活性边来; 如是水平边则直接画出。void sort_on_bigger_y(int n,CDC* pDC)/按照输入的多边形建立活性链表int k,x1,y1;side_count=0;/全局变量，记录所有非水平边数目y1=yn-1;x1=xn-1;/(Pn-1,P0)为第一条边，开始建表bottomscan=yn-1;for(k=0;kn;k+)/sides

10、数组存放所有非水平边，并且按照y值的由大到小顺序if(y1!=yk&(k+1)SelectObject(&myPen);pDC-MoveTo(short)x1,(short)y1);pDC-LineTo(short)xk,(short)yk);if(yk当前扫描线scan，last_s下移while(sideslast_s+1.y_top=scan)&(last_s+1)y_top;a-y_top=b-y_top;b-y_top=i_temp;/y_top 交换f_temp=a-x_int;a-x_int=b-x_int;b-x_int=f_temp;/x_int 交换 i_temp=a-de

11、lta_y;a-delta_y=b-delta_y;b-delta_y=i_temp;/delta_y 交换 f_temp=a-x_change_per_scan;a-x_change_per_scan=b-x_change_per_scan;b-x_change_per_scan=f_temp;/x_change_per_scan 交换void sort_on_x(int entry,int first_s)函数说明：sort_on_x子程序主要功能是将一条边sidesretry在活性表边的first到entry 之间按照x_int大小，递增排序。操作步骤是:检查位于entry的边的x_in

12、t是否小于位置entry-1 的边的x_int，如是，调用swap子程序交换两条边的彼此位置。void sort_on_x(int entry,int first_s)int ent1=entry;int ent2=entry;while(1)ent1-;if(sidesent2.x_int 0的边)按照x_int的大小排序。操作步骤是：从first 到last，对每一根delta_y 0的边，调用sort_on_x子程序排入活性边表中合适位置。void process_x_intersections(int scan,int first_s,int last_s)int k;x_int_co

13、unt=0;/该值表示扫描线与图形交点的个数for(k=first_s+1;k0)x_int_count+; /first_s+1 到 last 之间的边数目为交点数目 x_int_count sort_on_x(k,first_s);/与同一扫描线相交的所有边按照x_int递增排序void draw_lines(int scan,int x_int_count,int index,CDC* pDC)函数说明：draw_lines子程序的主要功能是在一条扫描线位于多边形内的部分，填上指 定的色彩。操作步骤是：在活性边表的激活边范围内，依次取出delta _y!=0两边的x_int， 作为两个端

14、点(x1, scan)， (x2, scan)，画一条水平线。void draw_lines(int scan,int x_int_count,int index,CDC* pDC)/填上指定颜色int k,x1,x2;int x=index;/ index 为主函数中的 first_sCPen myPen(PS_SOLID,2,RGB(255,0,0);pDC-SelectObject(&myPen);for(k=0;kMoveTo(short)x1,(short)scan);pDC-LineTo(short)x2,(short)scan);x+;/此行功能是越过不在图形内的线段，直接跳到下

15、一线段。void update_sides_list()函数说明：update_sides_list子程序的主要功能是刷新活性边表内激活边的值：delta_y=delta_y-1 ； x_int=x_int_x_chang_per_scan。void update_sides_list()int k;for(k=first_s;k0)sidesk.delta_y-;sidesk.x_int-=sidesk.x_change_per_scan;void fill_area(int count,int x,int y,CDC* pDC)函数说明：对含有count个顶点，其坐标值存放在x和y数组中的

16、多边形区域利用扫描 线算法填充。void fill_area(int count,int x,int y,CDC* pDC)/主程序sort_on_bigger_y(count,pDC);first_s=0;last_s=1;for(scan=sides0.y_top;scan=bottomscan;scan-)update_first_and_last(MAX_POINT,scan);process_x_intersections(scan,first_s,last_s);draw_lines（scan,x_int_count,first_s,pDC）;update_sides_list（）;步骤7：在OnDraw （）中添加代码：fill_area（MAX_POINT,x, y, pDC）;步骤8：编译、调试，查看运行结果。四、思考总结1、程序对多边形的特殊顶点如何处理？2、程序中的“first_s”和“last_s”是真正的指针变量吗？3、总结各子程序的具体功能，理解其中的各个变量的涵义和作用。4、与采用链表的数据结构相比，本实验程序有何优点和缺点？5、本实验程序中扫描线的扫描次序（按照y值）是递增还是递减进行?6、修改顶点参数（个数及坐标），观察、分析实验结果。（1）五角星（注意修改“ MAX_POINT”为“10”）：