多边形有效边表填充算法

多边形有效边表填充算法案例效果如下：具体实现：（1）新建MFC项目：（2）分别添加类：AET和Bucket在AET.h中定义#pragmaonceclassAET{public:AET(void);~AET(void);doublex;intyMax;doublek;AET*next;};在Bucket.h中定义#pragmaonce#includeAET.hclassBucket{public:Bucket(void);~Bucket(void);intScanline;AET*p;Bucket*next;};（3）定义菜单（4）添加菜单处理程序（5）定义视图头文件//scanfillView.h:CscanfillView类的接口//#pragmaonce#includeAET.h#includeBucket.h#defineNumber7classCscanfillView:publicCView{protected://仅从序列化创建CscanfillView();DECLARE_DYNCREATE(CscanfillView)//属性public:CscanfillDoc*GetDocument()const;//操作public:voidPolygonFill();//上闭下开填充多边形voidCreatBucket();//建立桶节点voidEt();//构造边表voidAddEdge(AET*);//将边插入AET表voidEdgeOrder();//对AET表进行排序//重写public:virtualvoidOnDraw(CDC*pDC);//重写以绘制该视图virtualBOOLPreCreateWindow(CREATESTRUCT&cs);protected:virtualBOOLOnPreparePrinting(CPrintInfo*pInfo);virtualvoidOnBeginPrinting(CDC*pDC,CPrintInfo*pInfo);virtualvoidOnEndPrinting(CDC*pDC,CPrintInfo*pInfo);//实现public:virtual~CscanfillView();#ifdef_DEBUGvirtualvoidAssertValid()const;virtualvoidDump(CDumpContext&dc)const;#endifprotected:COLORREFGetColor;//调色板CPointPoint[7];//定义多边形Bucket*HeadB,*CurrentB;//桶的头结点和当前节点AETE[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的节点//生成的消息映射函数protected:DECLARE_MESSAGE_MAP()public:afx_msgvoidOnMenuAET();};#ifndef_DEBUG//scanfillView.cpp中的调试版本inlineCscanfillDoc*CscanfillView::GetDocument()const{returnreinterpret_castCscanfillDoc*(m_pDocument);}#endif（6）实现视图//scanfillView.cpp:CscanfillView类的实现//#includestdafx.h#includescanfill.h#includescanfillDoc.h#includescanfillView.h#ifdef_DEBUG#definenewDEBUG_NEW#endif#defineROUND(a)int(a+0.5)//定义四舍五入//CscanfillViewIMPLEMENT_DYNCREATE(CscanfillView,CView)BEGIN_MESSAGE_MAP(CscanfillView,CView)//标准打印命令ON_COMMAND(ID_FILE_PRINT,&CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT,&CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW,&CView::OnFilePrintPreview)ON_COMMAND(ID_MenuAET,&CscanfillView::OnMenuAET)END_MESSAGE_MAP()//CscanfillView构造/析构CscanfillView::CscanfillView(){//TODO:在此处添加构造代码//设置多边形的个顶点Point[0]=CPoint(550,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);}CscanfillView::~CscanfillView(){}BOOLCscanfillView::PreCreateWindow(CREATESTRUCT&cs){//TODO:在此处通过修改//CREATESTRUCTcs来修改窗口类或样式returnCView::PreCreateWindow(cs);}//CscanfillView绘制voidCscanfillView::OnDraw(CDC*pDC){CscanfillDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);if(!pDoc)return;//TODO:在此处为本机数据添加绘制代码pDC-Polygon(Point,7);//绘制多边形pDC-TextOutW(550,410,_T(P0));//注意文本的输出pDC-TextOutW(350,600,_T(P1));pDC-TextOutW(230,340,_T(P2));pDC-TextOutW(350,30,_T(P3));pDC-TextOutW(490,220,_T(P4));pDC-TextOutW(600,30,_T(P5));pDC-TextOutW(805,450,_T(P6));}//CscanfillView打印BOOLCscanfillView::OnPreparePrinting(CPrintInfo*pInfo){//默认准备returnDoPreparePrinting(pInfo);}voidCscanfillView::OnBeginPrinting(CDC*/*pDC*/,CPrintInfo*/*pInfo*/){//TODO:添加额外的打印前进行的初始化过程}voidCscanfillView::OnEndPrinting(CDC*/*pDC*/,CPrintInfo*/*pInfo*/){//TODO:添加打印后进行的清理过程}//CscanfillView诊断#ifdef_DEBUGvoidCscanfillView::AssertValid()const{CView::AssertValid();}voidCscanfillView::Dump(CDumpContext&dc)const{CView::Dump(dc);}CscanfillDoc*CscanfillView::GetDocument()const//非调试版本是内联的{ASSERT(m_pDocument-IsKindOf(RUNTIME_CLASS(CscanfillDoc)));return(CscanfillDoc*)m_pDocument;}#endif//_DEBUG//CscanfillView消息处理程序voidCscanfillView::CreatBucket()//建立桶节点函数{intScanMin,ScanMax;//确定扫描线的最小值和最大值ScanMax=ScanMin=Point[0].y;for(inti=1;iNumber;i++){if(Point[i].yScanMin){ScanMin=Point[i].y;//扫描线的最小值}if(Point[i].yScanMax){ScanMax=Point[i].y;//扫描线的最大值}}for(inti=ScanMin;i=ScanMax;i++)//建立桶节点{if(ScanMin==i)//桶头结点{HeadB=newBucket;//建立桶的头结点CurrentB=HeadB;//CurrentB为Bucket当前节点指针CurrentB-Scanline=ScanMin;CurrentB-p=NULL;//没有连接边链表CurrentB-next=NULL;}else{//建立桶的其他节点CurrentB-next=newBucket;//新建一个桶节点CurrentB=CurrentB-next;//使CurrentB指向新建的桶节点CurrentB-Scanline=i;CurrentB-p=NULL;//没有连接边链表CurrentB-next=NULL;}}}voidCscanfillView::Et()//构造边表函数{for(inti=0;iNumber;i++)//访问每个顶点{CurrentB=HeadB;//从桶链表的头节点开始循环intj=i+1;//边的第二个顶点，Point[i]和Point[j]构成边if(j==Number)j=0;//保证多边形的闭合if(Point[j].yPoint[i].y)//终点比起点高{while(CurrentB-Scanline!=Point[i].y)//在桶内寻找该边的yMin{CurrentB=CurrentB-next;//移到下一个桶节点}E[i].x=Point[i].x;//计算AET表的值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].yPoint[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;}voidCscanfillView: