实验二 有效边表填充算法
1.实验目的：
设计有效边表结点和边表结点数据结构 设计有效边表填充算法 编程实现有效边表填充算法 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（800，450）。请使用有效边表算法填充该多边形。
图1示例多边形
图2 屏幕显示多边形
3.算法设计：
1．根据多边形顶点坐标值，计算扫描线的最大值ScanMax和最小值ScanMin。 2．用多边形覆盖的扫描线动态建立桶结点。
3．循环多边形的所有顶点，根据边的终点y 值比起点y值高或边的终点y值比起点y值低两种情况（边的终点y值和起点y值相等的情况属于扫描线，不予考虑），计算每条边的yMin。在桶中寻找与该yMin 相应的桶结点，计算该边表的x|yMin、yMax、k（代表斜率倒数1/k），并依次连接该边表结点到桶结点。
4．对每个桶结点连接的边表，根据x|yMin值的大小进行排序，若 x|yMin相等，则按照k由小到大排序。
5．对每个桶结点进行循环，将桶内每个结点的边表合并为有效边表，并进行有效边表循环。 6．从有效边表中取出相邻两条边的交点对进行填充。填充时设置一个逻辑变量In（初始值为假），每访问一个结点，把In值取反一次，若In为真，则把从当前结点的x值开始到下一结点的x－1值结束的区间用指定颜色填充。(左闭右开)
7．循环下一桶结点，按照 xi+1=xi+k（k的值为1/k）修改有效边表，同时合并桶结点内的新边表，形成新的有效边表。
8．如果桶结点的扫描线值大于等于有效边表中某个结点的yMax值，则放弃该有效边表。 9．当桶结点不为空则转⑸，否则删除桶结点和边结点的头结点，算法结束。
4.源程序：
1）//AET.h和AET..cpp class AET {
public: AET();
virtual ~AET(); double x; int yMax; double k;//代替1/k AET *next; }
2）//Bucket.h和Bucket.cpp #include \class Bucket {
public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; }
3) // TestView.h
#include \包含有效边表类 #include \包含桶类
#define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中 class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET * NewEdge);//将边插入AET表 void EdgeOrder();//对AET表进行排序 。。。。。。。。。。 protected: COLORREF GetColor;//调色板 CPoint Point[7];//定义多边形 Bucket *HeadB,*CurrentB;//桶的头结点和当前结点 AET E[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点 4)// TestView.cpp
CTestView::CTestView() { //设置多边形的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 }
void CTestView::OnDraw(CDC* pDC) { CTestDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); pDC->Polygon(Point,7);//绘制多边形 //输出多边形的顶点编号 pDC->TextOut(550,410,\ pDC->TextOut(350,600,\ pDC->TextOut(230,340,\ pDC->TextOut(350,30,\ pDC->TextOut(490,220,\ pDC->TextOut(600,30,\ pDC->TextOut(805,450,\}
void CTestView::OnMenuAET() //菜单函数 { AfxGetMainWnd()->SetWindowText(\多边形有效边表填充算法\显示标题 CColorDialog ccd(GetColor); if(ccd.DoModal()==IDOK)//调用调色板选取前景色 { GetColor=ccd.GetColor(); } RedrawWindow();//刷新屏幕 CreatBucket();//初始化桶 Et();//建立边表 PolygonFill();//多边形填充 }
void CTestView::CreatBucket()//初始化桶 { int ScanMin,ScanMax;//确定扫描线的最小值和最大值 ScanMax=ScanMin=Point[0].y; for(int i=1;i
