一、实验目的与要求：
设计有效边表节点和边表节点数据结构
二、实验描述：
使用有效边算法填充示例多边形
三、实验结果：
四、算法设计：
创建菜单栏，添加函数。
在VC++的class view 界面，新建两个类，VET和Bucket。其中AET类用于建立有效边表和边表节点，Bucket类用来建立桶节点。
AET.h文件。
class AET
{
public:
AET();
virtual ~AET();
double x;
int yMax;
double k;
AET *next;
};
Bucket.h文件
#include "AET.h"
class Bucket
{
public:
Bucket();
virtual ~Bucket();
int ScanLine;
AET *p;
Bucket *next;
};
CExp2View.h文件。其中添加了成员变量和函数的声明，以及库的导入。
#include "AET.h"
#include "Bucket.h"
#define Number 7
添加的成员变量和函数声明如下：
public:
void PolygonFill();
void CreatBucket();
void Et();
void AddEdge(AET *);
void EdgeOrder();
protected:
COLORREF GetColor;
CPoint Point[7];
Bucket *HeadB,*CurrentB;
AET E[Number],*HeadE,*CurrentE,*T1,*T2;
CExp2View.cpp文件。包含构造方法、OnDraw方法和其他成员方法的描述
#define ROUND(a) int(a+0.5)
CExp2View::CExp2View()
{
// TODO: add construction code here
Point[0] = CPoint(500,400);
Point[1] = CPoint(350,600);
Point[2] = CPoint(250,350);
Point[3] = CPoint(350,50);
Point[4] = CPoint(500,250);
Point[5] = CPoint(600,50);
Point[6] = CPoint(800,450);
}
void CExp2View::OnDraw(CDC* pDC)
{
CExp2Doc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
pDC->TextOut(505,410,"P0");
pDC->TextOut(340,600,"P1");
pDC->TextOut(230,350,"P2");
pDC->TextOut(360,50,"P3");
pDC->TextOut(490,225,"P4");
pDC->TextOut(610,50,"P5");
pDC->TextOut(800,450,"P6");
}
void CExp2View::OnMenuAET()
{
// TODO: Add your command handler code here
AfxGetMainWnd()->SetWindowText("¶à±ßÐÎÌî³ä£ºÓÐЧ±ßËã·¨");
CColorDialog ccd(GetColor);
if(ccd.DoModal() == IDOK)
GetColor = ccd.GetColor();
RedrawWindow();
CreatBucket();
Et();
PolygonFill();
}
void CExp2View::CreatBucket()
{
int ScanMin,ScanMax;
ScanMax = ScanMin = Point[0].y;
for(int i=1;i if(Point[i].y if(Point[i].y>ScanMax) ScanMax = Point[i].y; } for(i=ScanMin;i if(ScanMin == i) { HeadB = new Bucket; CurrentB = HeadB; CurrentB->ScanLine = ScanMin; CurrentB->p = NULL; CurrentB->next = NULL; } else { CurrentB->next = new Bucket; CurrentB = CurrentB->next; CurrentB->ScanLine = i; CurrentB->p = NULL; CurrentB->next = NULL; } } } void CExp2View::Et() { for(int i=0;i CurrentB = HeadB; int j=i+1; if(j==Number) j=0; if(Point[j].y>Point[i].y) { while(CurrentB->ScanLine != Point[i].y) { CurrentB = CurrentB->next; } E[i].x = Point[i].x; E[i].yMax = Point[j].y; E[i].k = double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y); E[i].next = NULL; CurrentE = CurrentB->p; if(CurrentB->p == NULL) { CurrentE = &E[i]; CurrentB->p = CurrentE; } else { while(CurrentE->next != NULL) { CurrentE = CurrentE->next; } CurrentE->next = &E[i]; } } if(Point[j].y < Point[i].y) { while(CurrentB->ScanLine != Point[j].y) { CurrentB = CurrentB->next; } E[i].x = Point[j].x; E[i].yMax = Point[i].y; E[i].k = double((Point[i].x-Point[j].x))/(Point[i].y-Point[j].y); E[i].next = NULL; CurrentE = CurrentB->p; if(CurrentE == NULL) { CurrentE = &E[i]; CurrentB->p = CurrentE; } else { while(CurrentE->next != NULL) { CurrentE = CurrentE->next; } CurrentE->next = &E[i]; } } } CurrentB = NULL; CurrentE = NULL; } void CExp2View::AddEdge(AET *NewEdge) { T1 = HeadE; if(T1 == NULL) { T1 = NewEdge; HeadE = T1; } else { while(T1->next != NULL) { T1 = T1->next; } T1->next = NewEdge; } } void CExp2View::EdgeOrder() { T1 = HeadE; if(T1 ==NULL) return; if(T1->next == NULL) return; else { if(T1->next->x < T1->x) { T2 = T1->next; T1->next = T2->next; T2->next = T1; HeadE = T2; } T2 = HeadE; T1 = HeadE->next; while(T1->next != NULL) { if(T1->next->x < T1->x) { T2->next = T1->next; T1->next = T1->next->next; T2->next->next = T1; T2 = T2->next; } else{ T2 = T1; T1 = T1->next; } } } } void CExp2View::PolygonFill() { HeadE = NULL; for(CurrentB=HeadB; CurrentB!=NULL; CurrentB=CurrentB->next) { 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(TempEdge); } EdgeOrder(); T1 = HeadE; if(T1 == NULL) return; while(CurrentB->ScanLine >= T1->yMax) { T1 = T1->next; HeadE = T1; if(HeadE == NULL) return; } if(T1->next != NULL) { T2 = T1; T1 = T2->next; } while(T1 != NULL) { if(CurrentB->ScanLine >= T1->yMax) { T2->next = T1->next; T1->next = NULL; T1 = T2->next; } else { T2 = T1; T1 = T2->next; } } BOOL In = false; double xb,xe; for(T1=HeadE; T1!=NULL; T1=T1->next) { if(In == false){ xb = T1->x; In = true; } else { xe = T1->x-1; CClientDC dc(this); for(double x=xb; x<=xe; x++) dc.SetPixel(ROUND(x),CurrentB->ScanLine,GetColor); Sleep(1); In = FALSE; } } for(T1=HeadE; T1!=NULL; T1=T1->next) { T1->x = T1->x+T1->k; } } delete HeadB; delete CurrentB; delete CurrentE; delete HeadE; } 五、实验小结 对于有效边填充算法还有一些地方不是很了解们，最后在同学的帮助下新建了一个适合的类才解决了问题下载本文
