实验六扫描线填充算法一、实验目的编写多边形的扫描线填充算法程序，加深对扫描线算法的理解，验证算法的正确性。

二、实验任务（2学时）编写多边形的扫描线填充算法程序，利用数组实现AET，考虑与链表实现程序的不同。

三、实验内容1、算法对一条扫描线的填充一般分为以下4个步骤：（1）求交：计算扫描线与多边形各边的交点；（2）排序：把扫描线上所有交点按递增顺序进行排序；（3）配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。

（4）着色：把区间内的像素置为填充色。

2、成员函数的关系主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共c ount个）的x和y坐标。

它调用8个子程序，彼此之间的调用关系图1所示为：图1 fill_area的程序结构3、算法的程序设计步骤1：创建“S_L_Fill”工程文件；步骤2：创建类class：“EACH_ENTRY”。

在工作区“S_L_Fill classes”单击右键-→“new class”-→选择类型“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_ENTRY.h"步骤4：在类“class CS_L_FillView”中添加成员变量（鼠标双击工作区“CS_L_FillView”，代码添加至“class CS_L_FillView : public Cview {protected: ……public:之后”）：EACH_ENTRY sides[MAX_POINT];int x[MAX_POINT],y[MAX_POINT];int side_count,first_s,last_s,scan,bottomscan,x_int_count;步骤5：利用构造函数“CS_L_FillView::CS_L_FillView()”初始化顶点坐标（鼠标双击工作区“CS_L_FillView”，代码添加至“CS_L_FillView（）之内”）：x[0]=200;y[0]=100;x[1]=240;y[1]=160;x[2]=220;y[2]=340;x[3]=330;y[3]=100;x[4]=400;y[4]=180;x[5]=300;y[5]=400;x[6]=170;y[6]=380;x[7]=120;y[7]=440;x[8]=100;y[8]=220;步骤6：在“class CS_L_FillView”下添加实现不同功能的成员函数。

在工作区“CS_L_FillView”上单击鼠标右键，选择“Add Member Function”，分别完成以下成员函数的添加：（1）void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y)函数说明：put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。

操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，y值较大者，排在活性边表的靠前位置。

void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y)// entry为剔除水平边之后的第entry条边，x1, y1,为起点，x2, y2为终点，next_y为终点相邻的下一个顶点y坐标{int maxy;float x2_temp,x_change_temp;x_change_temp=(float)(x2-x1)/(float)(y2-y1);//计算1/kx2_temp=float(x2);if((y2>y1)&&(y2<next_y))//x2,y2是左顶点，则（x2-1/m,y2-1）终点下缩{y2--;x2_temp-=x_change_temp;}else{if((y2<y1)&&(y2>next_y)) //x2,y2是右顶点，则（x2+1/m,y2+1）终点上缩{y2++;x2_temp+=x_change_temp;}}maxy=(y1>y2)?y1:y2;while((entry>1)&&(maxy>sides[entry-2].y_top)){sides[entry-1]=sides[entry-2];entry--;}// sides[]为边数组，边的y_top值越小，在数组中越靠后sides[entry-1].y_top=maxy;sides[entry-1].delta_y=abs(y2-y1)+1;if(y1>y2)// x2,y2为右顶点，扫描线与起点先求交sides[entry-1].x_int=float(x1);else// x2,y2左顶点，扫描线与终点先求交sides[entry-1].x_int=x2_temp;sides[entry-1].x_change_per_scan=x_change_temp;}（2）void sort_on_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=y[n-1];x1=x[n-1];//(Pn-1,P0)为第一条边，开始建表bottomscan=y[n-1];for(k=0;k<n;k++)//sides数组存放所有非水平边，并且按照y值的由大到小顺序{if(y1!=y[k]&&(k+1)<=(n-1)){side_count++;put_in_sides_list(side_count,x1,y1,x[k],y[k],y[k+1]);}if(y1!=y[k]&&(k+1)==n)//当前边非水平边{side_count++;put_in_sides_list(side_count,x1,y1,x[k],y[k],y[0]);}if(y1==y[k])//如果平行就直接画出直线{side_count++;CPen myPen(PS_DASH,2,RGB(255,0,0));pDC->SelectObject(&myPen);pDC->MoveTo((short)x1,(short)y1);pDC->LineTo((short)x[k],(short)y[k]);}if(y[k]<bottomscan)// bottomscan为全局变量，为所有顶点的最小y值bottomscan=y[k];y1=y[k];x1=x[k];} //end for}（3）void update_first_and_last(int count,int scan)函数说明：update_first_and_last子程序的主要功能是刷新活性边表的first和last两根指针的所指位置，以保证指针指出激活边的范围。

void update_first_and_last(int count,int scan){//下一条边的y_top>当前扫描线scan，last_s下移while((sides[last_s+1].y_top>=scan)&&((last_s+1)<count))last_s++;while(sides[first_s].delta_y==0)first_s++;}（4）void swap(EACH_ENTRY *a,EACH_ENTRY *b)函数说明：swap子程序的主要功能是交换活性边表中两条相邻位置边的彼此位置。

void swap(EACH_ENTRY *a,EACH_ENTRY *b)//为使交换成功，需用引用或者指针。

{int i_temp;float f_temp;i_temp=a->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->delta_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交换}（5）void sort_on_x(int entry,int first_s)函数说明：sort_on_x子程序主要功能是将一条边sides[retry]在活性表边的first到entry 之间按照x_int大小，递增排序。

操作步骤是：检查位于entry的边的x_int是否小于位置entry-1的边的x_int，如是，调用swap子程序交换两条边的彼此位置。

void sort_on_x(int entry,int first_s){int ent1=entry;int ent2=entry;while(1){ent1--;if((sides[ent2].x_int<sides[ent1].x_int)&&(sides[ent1].delta_y!=0))//如果两个的x_int需要交换则交换之{swap(&sides[ent2],&sides[ent1]);ent2=ent1;}if(ent1==first_s-1)break;}}（6）void process_x_intersections(int scan,int first_s,int last_s)函数说明：process_x_intersections子程序的主要功能是对活性边表中的激活边（即位于first和last之间的，并且delta_y> 0的边）按照x_int的大小排序。