有效边表填充算法.docVIP

实验二 有效边表填充算法 实验题目： 有效边表填充算法 学号： 姓名： 班级： 指导老师： 完成日期： 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.算法设计： 多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。 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 class Bucket { public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; } 3) // TestView.h #include AET.h//包含有效边表类 #include Bucket.h//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中 class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入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,P0); pDC-TextOut(350,600,P1); pDC-TextOut(230,340,P2); pDC-TextOut(350,30,P3); pDC-TextOut(490,220,P4); pDC-TextOut(600,30,P5); pDC-TextOut(805,450,P6); } void CTestView::OnMenuAET() //菜单函数 { Af