实验二 有效边表填充算法

《实验二 有效边表填充算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二有效边表填充算法20091104091计算机科学与技术师范汉班丁仕钰1.实验目的：(1)设计有效边表结点和边表结点数据结构(2)设计有效边表填充算法(3)编程实现有效边表填充算法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（80

2、0，450）。请使用有效边表算法填充该多边形。图1示例多边形图2屏幕显示多边形3.算法设计：4.源程序：(1)classAET{public:AET*next;doublek;intyMax;doublex;AET();virtual~AET();};(2)#include"AET.h"classBucket{public:Bucket*next;AET*p;intScanline;Bucket();virtual~Bucket();};(3)voidCShiyan1View::AddEdge(AET*NewEdge){T1=HeadE;if(T1==NULL)//边表为空，将边表置

3、为TempEdge{T1=NewEdge;HeadE=T1;}else{while(T1->next!=NULL)//边表不为空，将TempEdge连在该边之后{T1=T1->next;}T1->next=NewEdge;}}(4)voidCShiyan1View::PolygonFill(){HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)//访问所有的桶节点{for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)//桶

4、中所有边节点{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->n

5、ext;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)//

6、填充扫描线和多边形相交的区间{if(In==false){xb=T1->x;In=true;//每访问一个节点，把In值取反一次}else//如果In值为真，则填充从当前节点的x值开始到下一个节点的x值结束的区间{xe=T1->x-1;//左闭右开CClientDCdc(this);for(doublex=xb;x<=xe;x++)dc.SetPixel(ROUND(x),CurrentB->Scanline,GetColor);//填充Sleep(1);//延时ms，提高填充过程的可视性In=false;}}for(T1=HeadE;T1!=NULL;T1=T1->next)//边

7、连贯性{T1->x=T1->x+T1->k;}}deleteHeadB;deleteHeadE;deleteCurrentB;deleteCurrentE;}(5)voidCShiyan1View::EdgeOrder(){AET*F,*T;T1=HeadE;if(T1==NULL){return;}if(T1->next==NULL)//如果该边表没有再连接边{return;}else{F=HeadE->next;HeadE->next=NULL;whi