资源描述：
《vc++多边形的填充》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验二有效边表填充算法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）。请使用有效边表算法填充该多边形。图
2、1示例多边形图2屏幕显示多边形3.算法设计：1．根据多边形顶点坐标值，计算扫描线的最大值ScanMax和最小值ScanMin。2．用多边形覆盖的扫描线动态建立桶结点。3．循环多边形的所有顶点，根据边的终点y值比起点y值高或边的终点y值比起点y值低两种情况（边的终点y值和起点y值相等的情况属于扫描线，不予考虑），计算每条边的yMin。在桶中寻找与该yMin相应的桶结点，计算该边表的x
3、yMin、yMax、k（代表斜率倒数1/k），并依次连接该边表结点到桶结点。4．对每个桶结点连接的边表，根据x
4、yMin值的大小进行排序，若x
5、yMin相等，则按照k由小到大排序。5
6、．对每个桶结点进行循环，将桶内每个结点的边表合并为有效边表，并进行有效边表循环。6．从有效边表中取出相邻两条边的交点对进行填充。填充时设置一个逻辑变量In（初始值为假），每访问一个结点，把In值取反一次，若In为真，则把从当前结点的x值开始到下一结点的x－1值结束的区间用指定颜色填充。(左闭右开)7．循环下一桶结点，按照xi+1=xi+k（k的值为1/k）修改有效边表，同时合并桶结点内的新边表，形成新的有效边表。8．如果桶结点的扫描线值大于等于有效边表中某个结点的yMax值，则放弃该有效边表。9．当桶结点不为空则转⑸，否则删除桶结点和边结点的头结点，算法结束。4
7、.源程序：1）//AET.h和AET..cppclassAET{}2）//Bucket.h和Bucket.cppclassBucket{}3)//TestView.h#include"AET.h"//包含有效边表类#include"Bucket.h"//包含桶类#defineNumber7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中classCTestView:publicCView{。。。。。。。。。public:voidPolygonFill();//上闭下开填充多边形voidCreatBucket();//建立桶结点桶voidEt()
8、;//构造边表voidAddEdge(AET*);//将边插入AET表voidEdgeOrder();//对AET表进行排序。。。。。。。。。。protected:COLORREFGetColor;//调色板CPointPoint[7];//定义多边形Bucket*HeadB,*CurrentB;//桶的头结点和当前结点AETE[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点4)//TestView.cppCTestView::CTestView(){//设置多边形的7个顶点Point[0]=CPoint(550,400);
9、//P0Point[1]=CPoint(350,600);//P1Point[2]=CPoint(250,350);//P2Point[3]=CPoint(350,50);//P3Point[4]=CPoint(500,250);//P4Point[5]=CPoint(600,50);//P5Point[6]=CPoint(800,450);//P6}voidCTestView::OnDraw(CDC*pDC){CTestDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);pDC->Polygon(Point,7);//绘制多边形
10、//输出多边形的顶点编号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");}voidCTestView::OnMenuAET()//菜单函数{AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");//显示标
11、题CColorDialo
