有效边表填充算法

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

2、（500，250）, P5（600，50）, P6（800，450）。 图1示例多边形图2屏幕显示多边形3.算法设计：多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。4.源程序：1）/AET.h和AET.cppclass AET public:AET();virtual AET();double x;int yMax

3、;double k; /代替1/kAET *next;2）/Bucket.h和Bucket.cppclass Bucket public:Bucket();virtual Bucket();int ScanLine;AET *p;/桶上的边表指针Bucket *next;3) / TestView.h#include "AET.h"/包含有效边表类#include "Bucket.h"/包含桶类#define Number 7/N为闭合多边形顶点数，顶点存放在整型二维数组PointN中class CTestView : public CView。publ

4、ic:void PolygonFill();/上闭下开填充多边形void CreatBucket();/建立桶结点桶void Et();/构造边表void AddEdge(AET *);/将边插入AET表void EdgeOrder();/对AET表进行排序 。protected:COLORREF GetColor;/调色板CPoint Point7;/定义多边形Bucket *HeadB,*CurrentB;/桶的头结点和当前结点AET ENumber,*HeadE,*CurrentE,*T1,*T2;/有效边表的结点4)/ TestView.cppCTestView:CTestView()

5、/设置多边形的7个顶点Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoint(250,350);/P2Point3=CPoint(350,50);/P3Point4=CPoint(500,250);/P4Point5=CPoint(600,50);/P5Point6=CPoint(800,450);/P6void CTestView:OnDraw(CDC* pDC)CTestDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);pDC->Polygon(Point,7);/绘制

6、多边形/输出多边形的顶点编号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 C

7、TestView:OnMenuAET() /菜单函数AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");/显示标题CColorDialog ccd(GetColor);if(ccd.DoModal()=IDOK)/调用调色板选取前景色GetColor=ccd.GetColor();RedrawWindow();/刷新屏幕CreatBucket();/初始化桶Et();/建立边表PolygonFill();/多边形填充void CTestView:CreatBucket()/初始化桶int ScanMin,ScanMax;/确定扫

8、描线的最小值和最大值ScanMax=ScanMin=Point0.y;for(int i=1;i<Number;i+)if(Pointi.y<ScanMin)ScanMin=Pointi.y;/扫描线的最小值if(Pointi.y>ScanMax)ScanMax=Pointi.y;/扫描线的最大值for(i=ScanMin;i<=ScanMax;i+)/建立桶结点if(ScanMin=i)/桶头结点HeadB=new Bucket;/建立桶的头结点CurrentB=HeadB;/CurrentB为Bucket当前结点指针CurrentB->ScanLine=Sca

9、nMin;CurrentB->p=NULL;/没有连接边链表CurrentB->next=NULL;else/建立桶的其它结点CurrentB->next=new Bucket;/新建一个桶结点CurrentB=CurrentB->next;/使CurrentB指向新建的桶结点CurrentB->ScanLine=i;CurrentB->p=NULL;/没有连接边链表CurrentB->next=NULL;void CTestView:Et()/构造边表 for(int i=0;i<Number;i+)/访问每个顶点CurrentB=HeadB;

10、/从桶链表的头结点开始循环int j=i+1;/边的第二个顶点，Pointi和Pointj构成边if(j=Number) j=0;/保证多边形的闭合if(Pointj.y>Pointi.y)/终点比起点高while(CurrentB->ScanLine!=Pointi.y)/在桶内寻找该边的yMinCurrentB=CurrentB->next;/移到下一个桶结点Ei.x=Pointi.x;/计算AET表的值Ei.yMax=Pointj.y;Ei.k=double(Pointj.x-Pointi.x)/(Pointj.y-Pointi.y);/代表1/kEi.next=NUL

11、L;CurrentE=CurrentB->p;/获得桶上链接边表的地址if(CurrentB->p=NULL)/当前桶结点上没有链接边结点CurrentE=&Ei;/赋边的起始地址CurrentB->p=CurrentE;/第一个边结点直接连接到对应的桶中elsewhile(CurrentE->next!=NULL)/如果当前边已连有边结点CurrentE=CurrentE->next;/移动指针到当前边的最后一个边结点CurrentE->next=&Ei;/把当前边接上去if(Pointj.y<Pointi.y)/终点比起点低whil

12、e(CurrentB->ScanLine!=Pointj.y)CurrentB=CurrentB->next;Ei.x=Pointj.x;Ei.yMax=Pointi.y;Ei.k=double(Pointi.x-Pointj.x)/(Pointi.y-Pointj.y);Ei.next=NULL;CurrentE=CurrentB->p;if(CurrentE=NULL)CurrentE=&Ei;CurrentB->p=CurrentE;elsewhile(CurrentE->next!=NULL)CurrentE=CurrentE->next;C

13、urrentE->next=&Ei;CurrentB=NULL;CurrentE=NULL;void CTestView:AddEdge(AET *NewEdge)/插入临时边表函数 T1=HeadE;if(T1=NULL)/边表为空,将边表置为TempEdgeT1=NewEdge;HeadE=T1;elsewhile(T1->next!=NULL)/边表不为空,将TempEdge连在该边之后T1=T1->next;T1->next=NewEdge;void CTestView:EdgeOrder()/对边表进行排序函数 T1=HeadE;if(T1=NULL)

14、return;if(T1->next=NULL)/如果该边表没有再连边表return;/桶结点只有一条边，不需要排序elseif(T1->next->x<T1->x)/边表按x值排序T2=T1->next;T1->next=T2->next;T2->next=T1;HeadE=T2;T2=HeadE;T1=HeadE->next;while(T1->next!=NULL)/继续两两比较相连的边表的x值,进行排序if(T1->next->x<T1->x)T2->next=T1->next;T1-

15、>next=T1->next->next;T2->next->next=T1;T2=T2->next;elseT2=T1;T1=T1->next;void CTestView:PolygonFill()/多边形填充函数HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)/访问所有桶结点for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)/访问桶中排序前的边结点AET *Tem

16、pEdge=new AET;TempEdge->x=CurrentE->x;TempEdge->yMax=CurrentE->yMax;TempEdge->k=CurrentE->k;TempEdge->next=NULL;AddEdge(TempEdge);/将该边插入临时Aet表EdgeOrder();/使得边表按照x递增的顺序存放T1=HeadE;/根据ymax抛弃扫描完的边结点if(T1=NULL)return;while(CurrentB->ScanLine>=T1->yMax)/放弃该结点，Aet表指针后移（下闭上开）T1

17、=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;elseT2=T1;T1=T2->next;BOOL In=false;/设置一个BOOL变量In，初始值为假double xb,xe;/扫描线的起点和终点for(T1=HeadE;T1!=NULL;T1=T1->next)/填充扫描线和多边形相交的区间if(In=false)xb=T1->x;In=true;/每访问一个结点,把In值取反一次else/如果In值为真，则填充从当前结点的x值开始到下一结点的x值结束的区间xe=T1->x-1;/左闭右开CClientDC dc(t