实验三多边形的有效边表填充算法
一、实验目的与要求
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>=scanline
4)扫描AET表，填充扫描线和多边形相交的区间。
5)根据的边连贯性，更新AET表。0、构造桶结点的数据结构和有效边表的数据结构：
有效边表的数据结构：类AET
class 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 Point[7];//定义多边形
//设置多边形的7个顶点
Point[0]=CPoint(550,400);//P0
Point[1]=CPoint(350,600);//P1
Point[2]=CPoint(250,350);//P2
Point[3]=CPoint(350,50);//P3
Point[4]=CPoint(500,250);//P4
Point[5]=CPoint(600,50);//P5
Point[6]=CPoint(800,450);//P6
2、初始化桶
Bucket* CreatBucket(int number,CPoint *Point) {
int ScanMin,ScanMax;
Bucket *HeadB,*CurrentB;
ScanMin = ScanMax = Point[0].y;
for(int i = 1;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{
int j = i + 1;//边的第二个顶点，Point[i]和Point[j]构成边
if (j == number) //保证多边形的闭合
{
j = 0;
}
CurrentB = HeadB; //从桶链表的头结点开始搜索边（i,j）放入哪个桶
if(Point[i].y{
while(Point[i].y>CurrentB.ScanLine) //在桶内寻找该边的yMin
{
CurrentB = CrrentB->next; //移到下一个桶结点
}
Edge = new AET(); //构造有效边表结点，计算AET表的值
Edge->x = Point[i].x;
Edge->ymax = Point[j].y;
Edge->k = double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y);//代表1/k
if(CurrentB->p == NULL) //当前桶结点上没有链接边结点
{
