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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date多边形的有效边表填充算法-实验二 C语言的基础知识实验三 多边形的有效边表填充算法一、实验目的与要求1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法；3、掌握链表的建立、添加结点、删除节点的基本方法；3、掌握基于链表的排序操作。二、实验内容在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类CMyGL 中。 1、C+实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。四、实验步骤（程序实现）。1、建立并选择工程项目。打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(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();EdgeOrder();4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。参考实现：多边形的有效边表填充算法的基本过程为：1、定义多边形：2、初始化桶3、建立边表4、多边形填充1) 对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE.2) 对临时AET表排序，按照x递增的顺序存放。3) 根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline4) 扫描AET表，填充扫描线和多边形相交的区间。5) 根据的边连贯性，更新AET表。0、构造桶结点的数据结构和有效边表的数据结构：有效边表的数据结构：类AETclass AET public:AET();virtual AET();double x;int yMax;double k;/代替1/kAET *next;桶结点的数据结构:类Bucketclass Bucket public:Bucket();virtual Bucket();int ScanLine;AET *p;/桶上的边表指针Bucket *next;1、定义多边形：CPoint Point7;/定义多边形/设置多边形的7个顶点Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoint(250,350);/P2Point3=CPoint(350,50);/P3Point4=CPoint(500,250);/P4Point5=CPoint(600,50);/P5Point6=CPoint(800,450);/P62、初始化桶Bucket* CreatBucket(int number,CPoint *Point)int ScanMin,ScanMax;Bucket *HeadB,*CurrentB;ScanMin = ScanMax = Point0.y;for(int i = 1;i<number;i+)/找最低和最高扫描线for(i = ScanMin;i<=ScanMax;i+)if(i = ScanMin) /桶头结点HeadB = new Bucket();/建立桶的头结点CurrentB = HeadB; /CurrentB为Bucket当前结点指针CurrentB->ScanLine = 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;i<number;i+)/访问每个顶点int j = i + 1; /边的第二个顶点，Pointi和Pointj构成边if (j = number)/保证多边形的闭合j = 0;CurrentB = HeadB;/从桶链表的头结点开始搜索边（i,j）放入哪个桶if(Pointi.y<Pointj.y)/终点比起点高while(Pointi.y>CurrentB.ScanLine)/在桶内寻找该边的yMinCurrentB = 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/kif(CurrentB->p = NULL)/当前桶结点上没有链接边结点Current->p = Edge;/第一个边结点直接连接到对应的桶中else/如果当前边已连有边结点CurrentE = CurrentB->p;/移动指针到当前边的最后一个边结点/把当前边接上去if(Pointj.y<Pointi.y)/终点比起点低/终点比起点高CurrentE = NULL;CurrentB = NULL;AET = NULL;return HeadB;4、多边形填充1) 对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE.2) 对临时AET表排序，按照x递增的顺序存放。3) 根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline4) 扫描AET表，填充扫描线和多边形相交的区间。5) 根据的边连贯性，更新AET表。void PolygonFill (int number,CPoint *p,COLORREF fillcolor,CDC *pDC)/多边形填充HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)/访问所有桶结点1) 对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadEfor(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表2) 对临时AET表排序，按照x递增的顺序存放。EdgeOrder();/使得边表按照x递增的顺序存放3) 根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanlineT1=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)/根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=ScanLine4) 扫描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);/延时1ms,提高填充过程的可视性In=FALSE;5) 根据的边连贯性，更新AET表。/利用边的连贯性，更新交点信息delete HeadB; delete CurrentB;delete CurrentE;delete HeadE;5、图形类的使用 （1）、图形类对象的定义。首先在“C*View”（本例中是CSampleView）类的头文件中加入图形类的头文件，使图形类能在C*View 中被辨识和使用；然后，在C*View 类头文件中实例化图形类，即定义一个图形类的对象。在public属性区加入：CmyCG m_cg;（2）、图形类对象的使用。在“C*View”类中有一个成员函数void OnDraw(CDC* pDC),找到该函数的实现。在其中加入对图形类对象的使用代码：m_cg-> PolygonFill(_,_,_,_);/测试：填充的多边形的七个顶点为：Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoint(250,350);/P2Point3=CPoint(350,50);/P3Point4=CPoint(500,250);/P4Point5=CPoint(600,50);/P5Point6=CPoint(800,450);/P6在进行填充之前先绘制多边形的轮廓。6、程序的调试、运行。五、实验结果抓图与结果分析 1、请给出顶点数7个，Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoint(250,350);/P2Point3=CPoint(350,50);/P3Point4=CPoint(500,250);/P4Point5=CPoint(600,50);/P5Point6=CPoint(800,450);/P6的多边形，填充颜色为红色的填充效果。2、请给出顶点数6个，Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoint(250,350);/P2Point3=CPoint(350,50);/P3Point4=CPoint(600,50);/P4Point5=CPoint(800,450);/P5的多边形，填充颜色为兰色的填充效果。注意：在这个多边形中有一条边为水平边，上述的多边形有效边表填充算法是否仍然有效？六、参考文献 -