有效边表填充算法

１实验二有效边表填充算法实验题目：有效边表填充算法学号：姓名：班级：指导老师：完成日期：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.算法设计：多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。4.源程序：1）//AET.h和AET..cppclassAET{public:AET();virtual~AET();doublex;intyMax;doublek;//代替1/kAET*next;}2）//Bucket.h和Bucket.cppclassBucket３{public:Bucket();virtual~Bucket();intScanLine;AET*p;//桶上的边表指针Bucket*next;}3)//TestView.h#includeAET.h//包含有效边表类#includeBucket.h//包含桶类#defineNumber7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中classCTestView:publicCView{。。。。。。。。。public:voidPolygonFill();//上闭下开填充多边形voidCreatBucket();//建立桶结点桶voidEt();//构造边表voidAddEdge(AET*);//将边插入AET表voidEdgeOrder();//对AET表进行排序。。。。。。。。。。protected:COLORREFGetColor;//调色板CPointPoint[7];//定义多边形Bucket*HeadB,*CurrentB;//桶的头结点和当前结点AETE[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点4)//TestView.cppCTestView::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}voidCTestView::OnDraw(CDC*pDC){４CTestDoc*pDoc=GetDocument();ASSERT_VALID(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);}voidCTestView::OnMenuAET()//菜单函数{AfxGetMainWnd()-SetWindowText(多边形有效边表填充算法);//显示标题CColorDialogccd(GetColor);if(ccd.DoModal()==IDOK)//调用调色板选取前景色{GetColor=ccd.GetColor();}RedrawWindow();//刷新屏幕CreatBucket();//初始化桶Et();//建立边表PolygonFill();//多边形填充}voidCTestView::CreatBucket()//初始化桶{intScanMin,ScanMax;//确定扫描线的最小值和最大值ScanMax=ScanMin=Point[0].y;for(inti=1;iNumber;i++){if(Point[i].yScanMin){ScanMin=Point[i].y;//扫描线的最小值}if(Point[i].yScanMax){ScanMax=Point[i].y;//扫描线的最大值}}for(i=ScanMin;i=ScanMax;i++)//建立桶结点{５if(ScanMin==i)//桶头结点{HeadB=newBucket;//建立桶的头结点CurrentB=HeadB;//CurrentB为Bucket当前结点指针CurrentB-ScanLine=ScanMin;CurrentB-p=NULL;//没有连接边链表CurrentB-next=NULL;}else//建立桶的其它结点{CurrentB-next=newBucket;//新建一个桶结点CurrentB=CurrentB-next;//使CurrentB指向新建的桶结点CurrentB-ScanLine=i;CurrentB-p=NULL;//没有连接边链表CurrentB-next=NULL;}}}voidCTestView::Et()//构造边表{for(inti=0;iNumber;i++)//访问每个顶点{CurrentB=HeadB;//从桶链表的头结点开始循环intj=i+1;//边的第二个顶点，Point[i]和Point[j]构成边if(j==Number)j=0;//保证多边形的闭合if(Point[j].yPoint[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];//把当前边接上去}}if(Point[j].yPoint[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];}}}CurrentB=NULL;CurrentE=NULL;}voidCTestView::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;}}voidCTestView::EdgeOrder()//对边表进行排序函数{T1=HeadE;if(T1==NULL){return;}if(T1-next==NULL)//如果该边表没有再连边表{return;//桶结点只有一条边，不需要排序}else{if(T1-next-xT1-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-xT1-x){T2-next=T1-next;T1-next=T1-next-next;T2-next-next=T1;T2=T2-next;}８else{T2=T1;T1=T1-next;}}}}voidCTestView::PolygonFill()//多边形填充函数{HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB-next)//访问所有桶结点{for(CurrentE=CurrentB-p;CurrentE!=NULL;CurrentE=CurrentE-next)//访问桶中排序前的边结点{AET*TempEdge=newAET;TempEdge-x=CurrentE-x;TempEdge-yMax=CurrentE-yMax;TempEdge-k=CurrentE-k;TempEdge-next=NULL;AddEdge(TempEdge);//将该边插入临时Aet表}EdgeOrder();//使得边表按照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;}}BOOLIn=false;//设置一个BOOL变量In，初始值为假doublexb,xe;//扫描线的起点和终点for(T1=HeadE;T1!=NULL;T1=T1-next)//填充扫描线和多边形相交的区间{if(In==false){xb=T1-x;In=true;//每访问一个结点,把In值取反一