《多边形的有效边表填充算法.docx》由会员分享，可在线阅读，更多相关《多边形的有效边表填充算法.docx（7页珍藏版）》请在三一办公上搜索。
1、多边形的有效边表填充算法实验三 多边形的有效边表填充算法 一、实验目的与要求 1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法； 3、掌握链表的建立、添加结点、删除节点的基本方法； 3、掌握基于链表的排序操作。 二、实验内容 在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类CMyGL 中。 1、C+实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。 四、实验步骤。 1、建立并选择工程项目。打开VC6.0-菜单File 的New 项,在projects 属性页选择MFC AppWiz
2、ard(exe)项，在Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。选择菜单Insert New class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数。在工作区中直接鼠标右键单击，选择“Add Member Function”项，添加绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数： CreatBucket; CreatET; AddEdge
3、; EdgeOrder; 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。 参考实现： 多边形的有效边表填充算法的基本过程为： 1、定义多边形： 2、初始化桶 3、建立边表 4、多边形填充 1) 对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE. 2) 对临时AET表排序，按照x递增的顺序存放。 3) 根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax=scanline 4) 扫描AET表，填充扫描线和多边形相交的区间。 5) 根据的边连贯性，更新AET表。 0、构造桶结点的数据结构和有效边表的数据结构： 有效边表的数据结构：类AET cla
4、ss AET public: AET; virtual AET; double x; int yMax; double k;/代替1/k AET *next; 桶结点的数据结构:类Bucket class Bucket public: Bucket; virtual Bucket; int ScanLine; AET *p;/桶上的边表指针 Bucket *next; 1、定义多边形： CPoint Point7;/定义多边形 /设置多边形的7个顶点 Point0=CPoint(550,400);/P0 Point1=CPoint(350,600);/P1 Point2=CPoint(250,
5、350);/P2 Point3=CPoint(350,50);/P3 Point4=CPoint(500,250);/P4 Point5=CPoint(600,50);/P5 Point6=CPoint(800,450);/P6 2、初始化桶 Bucket* CreatBucket(int number,CPoint *Point) int ScanMin,ScanMax; Bucket *HeadB,*CurrentB; ScanMin = ScanMax = Point0.y; for(int i = 1;inumber;i+) /找最低和最高扫描线 for(i = ScanMin;iSc
6、anLine = i; CurrentB-p = NULL; /没有连接边链表 CurrentB-next = NULL; Else/建立桶的其它结点 return HeadB; 3、建立边表 Bucket * CreatET(int number,CPoint *Point) Bucket *HeadB; Bucket *CurrentB; AET *CurrentE,*Edge; HeadB = CreateBucket(number,Point); for (int i = 0;inumber;i+) /访问每个顶点 int j = i + 1; /边的第二个顶点，Pointi和Poin
7、tj构成边 if (j = number) /保证多边形的闭合 j = 0; CurrentB = HeadB; /从桶链表的头结点开始搜索边放入哪个桶 if(Pointi.yCurrentB.ScanLine) /在桶内寻找该边的yMin CurrentB = CrrentB-next; /移到下一个桶结点 Edge = new AET; /构造有效边表结点，计算AET表的值 Edge-x = Pointi.x; Edge-ymax = Pointj.y; Edge-k = double(Pointj.x-Pointi.x)/(Pointj.y-Pointi.y);/代表1/k if(Cur
8、rentB-p = NULL) /当前桶结点上没有链接边结点 Current-p = Edge; /第一个边结点直接连接到对应的桶中 else /如果当前边已连有边结点 CurrentE = CurrentB-p; /移动指针到当前边的最后一个边结点 /把当前边接上去 if(Pointj.y=scanline 4) 扫描AET表，填充扫描线和多边形相交的区间。 5) 根据的边连贯性，更新AET表。 void PolygonFill (int number,CPoint *p,COLORREF fillcolor,CDC *pDC)/多边形填充 HeadE=NULL; for(CurrentB=
9、HeadB;CurrentB!=NULL;CurrentB=CurrentB-next)/访问所有桶结点 1) 对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE 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(TempEdg
10、e);/将该边插入临时Aet表 2) 对临时AET表排序，按照x递增的顺序存放。 EdgeOrder;/使得边表按照x递增的顺序存放 3) 根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax=scanline 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!=NUL
11、L)/ /根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax=ScanLine 4) 扫描AET表，填充扫描线和多边形相交的区间。 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;/左闭右开 /填充 Sleep(1);/延时
12、1ms,提高填充过程的可视性 In=FALSE; delete HeadB; delete CurrentB; delete CurrentE; delete HeadE; 5) 根据的边连贯性，更新AET表。 /利用边的连贯性，更新交点信息 5、图形类的使用 、图形类对象的定义。首先在“C*View”类的头文件中加入图形类的头文件，使图形类能在C*View 中被辨识和使用；然后，在C*View 类头文件中实例化图形类，即定义一个图形类的对象。 在public属性区加入： CmyCG m_cg; 、图形类对象的使用。在“C*View”类中有一个成员函数void OnDraw(CDC* pDC)
13、,找到该函数的实现。在其中加入对图形类对象的使用代码： m_cg- PolygonFill(_,_,_,_); /测试：填充的多边形的七个顶点为： Point0=CPoint(550,400);/P0 Point1=CPoint(350,600);/P1 Point2=CPoint(250,350);/P2 Point3=CPoint(350,50);/P3 Point4=CPoint(500,250);/P4 Point5=CPoint(600,50);/P5 Point6=CPoint(800,450);/P6 在进行填充之前先绘制多边形的轮廓。 6、程序的调试、运行。 五、实验结果抓图与
14、结果分析 1、请给出顶点数7个， Point0=CPoint(550,400);/P0 Point1=CPoint(350,600);/P1 Point2=CPoint(250,350);/P2 Point3=CPoint(350,50);/P3 Point4=CPoint(500,250);/P4 Point5=CPoint(600,50);/P5 Point6=CPoint(800,450);/P6 的多边形，填充颜色为红色的填充效果。 2、请给出顶点数6个， Point0=CPoint(550,400);/P0 Point1=CPoint(350,600);/P1 Point2=CPoint(250,350);/P2 Point3=CPoint(350,50);/P3 Point4=CPoint(600,50);/P4 Point5=CPoint(800,450);/P5 的多边形，填充颜色为兰色的填充效果。 注意：在这个多边形中有一条边为水平边，上述的多边形有效边表填充算法是否仍然有效？ 六、参考文献
