实验题目：实验二有效边表填充算法1.实验目的：设计有效边表结点和边表结点数据结构设计有效边表填充算法编程实现有效边表填充算法2.实验描述：下图1 所示多边形覆盖了12 条扫描线，共有7 个顶点和7 条边。

7 个顶点分别为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。

在1024×768 的显示分辩率下，将多边形顶点放大为P0（500,400），P1（350，600），P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。

请使用有效边表算法填充该多边形。

图1示例多边形图2 屏幕显示多边形3.算法设计：（1）建立AET和BUCKET类；（2）初始化桶，并在建立桶结点时为其表示的扫描线初始化为带头结点的链表；（3）对每个桶结点进行循环，将桶内每个结点的边表合并为有效边表，并进行有效边表循环；（4）按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按X值递增的顺序进行排序，配对，以确定填充区间；（5）用指定颜色点亮填充区间内的所有像素，即完成填充工作。

4.源程序：1)//AET.hclass AET{public:AET();virtual ~AET();double x;int yMax;double k;//代替1/kAET *next;};//AET..cppAET::AET(){}AET::~AET(){}2) //Bucket.h#include "AET.h"class Bucket{public:Bucket();virtual ~Bucket();int ScanLine;AET *p;//桶上的边表指针Bucket *next;};// Bucket.cppBucket::Bucket(){}Bucket::~Bucket(){}3)//TestView.h#include "AET.h"//包含有效边表类#include "Bucket.h"//包含桶类#define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView{。

public:void PolygonFill();//上闭下开填充多边形void CreatBucket();//建立桶结点桶void Et();//构造边表void AddEdge(AET *);//将边插入AET表void EdgeOrder();//对AET表进行排序。

protected:COLORREF GetColor;//调色板CPoint Point[7];//定义多边形Bucket *HeadB,*CurrentB;//桶的头结点和当前结点AET E[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点}(4) TestView.cpp#define ROUND(a) int(a+0.5) //四舍五入CTestView::CTestView(){//设置多边形的7个顶点Point[0]=CPoint(550,400);//P0Point[1]=CPoint(350,600);//P1Point[2]=CPoint(250,350);//P2Point[3]=CPoint(350,50);//P3Point[4]=CPoint(500,250);//P4Point[5]=CPoint(600,50);//P5Point[6]=CPoint(800,450);//P6}void CTestView::OnDraw(CDC* pDC){CTestDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);pDC->Polygon(Point,7);//绘制多边形//输出多边形的顶点编号pDC->TextOut(550,410,"P0");pDC->TextOut(350,600,"P1");pDC->TextOut(230,340,"P2");pDC->TextOut(350,30,"P3");pDC->TextOut(490,220,"P4");pDC->TextOut(600,30,"P5");pDC->TextOut(805,450,"P6");}void CTestView::OnMenuAET() //菜单函数{AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");//显示标题CColorDialog ccd(GetColor);if(ccd.DoModal()==IDOK)//调用调色板选取前景色{GetColor=ccd.GetColor();}RedrawWindow();//刷新屏幕CreatBucket();//初始化桶Et();//建立边表PolygonFill();//多边形填充}void CTestView::CreatBucket()//初始化桶{int ScanMin,ScanMax;//确定扫描线的最小值和最大值ScanMax=ScanMin=Point[0].y;for(int i=1;i<Number;i++){if(Point[i].y<ScanMin){ScanMin=Point[i].y;//扫描线的最小值}if(Point[i].y>ScanMax){ScanMax=Point[i].y;//扫描线的最大值}}for(i=ScanMin;i<=ScanMax;i++)//建立桶结点{if(ScanMin==i)//桶头结点{HeadB=new Bucket;//建立桶的头结点CurrentB=HeadB;//CurrentB为Bucket当前结点指针CurrentB->ScanLine=ScanMin;CurrentB->p=NULL;//没有连接边链表CurrentB->next=NULL;}else//建立桶的其它结点{CurrentB->next=new Bucket;//新建一个桶结点CurrentB=CurrentB->next;//使CurrentB指向新建的桶结点CurrentB->ScanLine=i;CurrentB->p=NULL;//没有连接边链表CurrentB->next=NULL;}}}void CTestView::Et()//构造边表{for(int i=0;i<Number;i++)//访问每个顶点{CurrentB=HeadB;//从桶链表的头结点开始循环int j=i+1;//边的第二个顶点，Point[i]和Point[j]构成边if(j==Number) j=0;//保证多边形的闭合if(Point[j].y>Point[i].y) //终点比起点高{while(CurrentB->ScanLine!=Point[i].y)//在桶内寻找该边的yMin CurrentB=CurrentB->next;//移到下一个桶结点E[i].x=Point[i].x;//计算AET表的值E[i].yMax=Point[j].y;E[i].k=double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y);//代表1/kE[i].next=NULL;CurrentE=CurrentB->p;//获得桶上链接边表的地址if(CurrentB->p==NULL)//当前桶结点上没有链接边结点{CurrentE=&E[i];//赋边的起始地址CurrentB->p=CurrentE;//第一个边结点直接连接到对应的桶中}else{while(CurrentE->next!=NULL)//如果当前边已连有边结点CurrentE=CurrentE->next;//移动指针到当前边的最后一个结点CurrentE->next=&E[i];//把当前边接上去}} //ifif(Point[j].y<Point[i].y)//终点比起点低{while(CurrentB->ScanLine!=Point[j].y)CurrentB=CurrentB->next;E[i].x=Point[j].x;E[i].yMax=Point[i].y;E[i].k=double((Point[i].x-Point[j].x))/(Point[i].y-Point[j].y);E[i].next=NULL;CurrentE=CurrentB->p;if(CurrentE==NULL){CurrentE=&E[i];CurrentB->p=CurrentE;}else{while(CurrentE->next!=NULL)CurrentE=CurrentE->next;CurrentE->next=&E[i];}}//if} //forCurrentB=NULL;CurrentE=NULL;}void CTestView::AddEdge(AET *NewEdge)//插入临时边表函数{T1=HeadE;if(T1==NULL)//边表为空，将边表置为TempEdge{T1=NewEdge;HeadE=T1;}else {while(T1->next!=NULL)//边表不为空,将TempEdge连在该边之后T1=T1->next;T1->next=NewEdge;}}void CTestView::EdgeOrder()//对边表进行排序函数{T1=HeadE;if(T1==NULL) return;if(T1->next==NULL)//如果该边表没有再连边表{return;//桶结点只有一条边，不需要排序}else{if(T1->next->x<T1->x)//边表按x值排序{T2=T1->next;T1->next=T2->next;T2->next=T1;HeadE=T2;}T2=HeadE;T1=HeadE->next;while(T1->next!=NULL)//继续两两比较相连的边表的x 值,进行排序{if(T1->next->x<T1->x){T2->next=T1->next;T1->next=T1->next->next;T2->next->next=T1;T2=T2->next;}else{T2=T1;T1=T1->next;}}}}void CTestView::PolygonFill()//多边形填充函数{HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)//访问所有桶结点{for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)//桶中所有边结点{AET *TempEdge=new AET;TempEdge->x=CurrentE->x;TempEdge->yMax=CurrentE->yMax;TempEdge->k=CurrentE->k;TempEdge->next=NULL;AddEdge(TempEdge);//将该边插入临时Aet 表}//forEdgeOrder();//边表按照x递增的顺序存放T1=HeadE;//根据yMax抛弃扫描完的边结点if(T1==NULL) return;while(CurrentB->ScanLine>=T1->yMax) //放弃该结点，Aet表指针后移，下闭上开{T1=T1->next;HeadE=T1;if(HeadE==NULL)return;}if(T1->next!=NULL){T2=T1;T1=T2->next;}while(T1!=NULL){if(CurrentB->ScanLine>=T1->yMax)//跳过一个结点{T2->next=T1->next;T1->next=NULL;T1=T2->next;}else{T2=T1;T1=T2->next;}}BOOL In=false;//设置一个BOOL变量In，初始值为假double xb,xe;//扫描线的起点和终点for(T1=HeadE;T1!=NULL;T1=T1->next)//填充扫描线和多边形相交的区间{if(In==false){xb=T1->x;In=true;//每访问一个结点,把In值取反一次}else//如果In 值为真，则填充从当前结点的x值开始到下一结点的x 值结束的区间{xe=T1->x-1;//左闭右开CClientDC dc(this);for(double x=xb;x<=xe;x++)dc.SetPixel(ROUND(x),CurrentB->ScanLine,GetColor);//填充Sleep(1); //延时1ms,提高填充过程的可视性In=FALSE;}}//forfor(T1=HeadE;T1!=NULL;T1=T1->next)//边连贯性T1->x=T1->x+T1->k; //x=x+1/k}delete HeadB;delete CurrentB;delete CurrentE;delete HeadE;}5.运行结果：。