多边形的有效边表填充算法-

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

1、实验三多边形的有效边表填充算法一、实验目的与要求1、理解多边形的扫描转换原理、方法；2、掌握有效边表填充算法；3、掌握链表的建立、添加结点、删除节点的基本方法；3、掌握基于链表的排序操作。二、实验内容在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类CMyGL中。1、C++实现有效边表算法进行多边形扫描转换2、利用1进行多边形扫描转换和区域填充的实现；三、实验原理请同学们根据教材及上课的PPT独立完成。四、实验步骤（程序实现）。1、建立并选择工程项目。打开VC6.0->菜单File的New项,在projects属性页选择MFCAppWizard(exe)项，在Project

2、name中输入一个工程名,如“Sample”。单文档。2、新建一个图形类。选择菜单InsertNewclass，Classtype选择“GenericClass”，Name输入类名，如“CMyCG。3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。在工作区中直接鼠标右键单击，选择“AddMemberFunction…”项，添加绘制圆的成员函数。voidPolygonFill(intnumber,CPoint*p,COLORREFcolor,CDC*pDC)添加其他成员函数：CreatBucket();CreatET();AddEdge();Edge

3、Order();4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。参考实现：多边形的有效边表填充算法的基本过程为：1、定义多边形：2、初始化桶3、建立边表4、多边形填充1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE.2)对临时AET表排序，按照x递增的顺序存放。3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline4)扫描AET表，填充扫描线和多边形相交的区间。1)根据的边连贯性，更新AET表。0、构造桶结点的数据结构和有效边表的数据结构：有效边表的数据结构：类AETclassAET{public:AET()

4、;virtual~AET();doublex;intyMax;doublek;//代替1/kAET*next;}桶结点的数据结构:类BucketclassBucket{public:Bucket();virtual~Bucket();intScanLine;AET*p;//桶上的边表指针Bucket*next;}1、定义多边形：CPointPoint[7];//定义多边形//设置多边形的7个顶点Point[0]=CPoint(550,400);//P0Point[1]=CPoint(350,600);//P1Point[2]=CPoint(250,350);//P2Point[3]=

5、CPoint(350,50);//P3Point[4]=CPoint(500,250);//P4Point[5]=CPoint(600,50);//P5Point[6]=CPoint(800,450);//P62、初始化桶Bucket*CreatBucket(intnumber,CPoint*Point){intScanMin,ScanMax;Bucket*HeadB,*CurrentB;ScanMin=ScanMax=Point[0].y;for(inti=1;i

6、=ScanMin)//桶头结点{HeadB=newBucket();//建立桶的头结点CurrentB=HeadB;//CurrentB为Bucket当前结点指针CurrentB->ScanLine=i;CurrentB->p=NULL;//没有连接边链表CurrentB->next=NULL;}Else//建立桶的其它结点{}}returnHeadB;}3、建立边表Bucket*CreatET(intnumber,CPoint*Point){Bucket*HeadB;Bucket*CurrentB;AET*CurrentE,*Edge;HeadB=CreateBucket(numb

7、er,Point);for(inti=0;iCurrentB.ScanLine)//在桶内寻找该边的