多边形有效边表填充算法

1、精选优质文档-倾情为你奉上多边形有效边表填充算法案例效果如下：具体实现：（1） 新建MFC项目：（2）分别添加类：AET 和Bucket 在AET.h 中定义#pragma onceclass AETpublic:AET(void);AET(void);double x;int yMax;double k;AET * next;在Bucket.h中定义#pragma once#include "AET.h"class Bucketpublic:Bucket(void);Bucket(void);int Scanline;AET *p;Bucket * next;（3）定义菜

2、单 （4）添加菜单处理程序（5）定义视图头文件/ scanfillView.h : CscanfillView 类的接口/#pragma once#include "AET.h"#include "Bucket.h"# define Number 7class CscanfillView : public CViewprotected: / 仅从序列化创建CscanfillView();DECLARE_DYNCREATE(CscanfillView)/ 属性public:CscanfillDoc* GetDocument() const;/ 操作publ

3、ic:void PolygonFill(); /上闭下开填充多边形void CreatBucket(); /建立桶节点void Et(); /构造边表void AddEdge(AET *); /将边插入AET表void EdgeOrder(); /对AET表进行排序/ 重写public:virtual void OnDraw(CDC* pDC); / 重写以绘制该视图virtual BOOL PreCreateWindow(CREATESTRUCT& cs);protected:virtual BOOL OnPreparePrinting(CPrintInfo* pInfo);virt

4、ual void OnBeginPrinting(CDC* pDC, CPrintInfo* pInfo);virtual void OnEndPrinting(CDC* pDC, CPrintInfo* pInfo);/ 实现public:virtual CscanfillView();#ifdef _DEBUGvirtual void AssertValid() const;virtual void Dump(CDumpContext& dc) const;#endifprotected:COLORREF GetColor; /调色板CPoint Point7; /定义多边形Buc

5、ket * HeadB,*CurrentB; /桶的头结点和当前节点AET ENumber,*HeadE,*CurrentE,*T1,*T2; /有效边表的节点/ 生成的消息映射函数protected:DECLARE_MESSAGE_MAP()public:afx_msg void OnMenuAET();#ifndef _DEBUG / scanfillView.cpp 中的调试版本inline CscanfillDoc* CscanfillView:GetDocument() const return reinterpret_cast<CscanfillDoc*>(m_pDoc

6、ument); #endif（6）实现视图/ scanfillView.cpp : CscanfillView 类的实现/#include "stdafx.h"#include "scanfill.h"#include "scanfillDoc.h"#include "scanfillView.h"#ifdef _DEBUG#define new DEBUG_NEW#endif#define ROUND(a) int(a+0.5) /定义四舍五入/ CscanfillViewIMPLEMENT_DYNCREATE(

7、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

8、_MAP()/ CscanfillView 构造/析构CscanfillView:CscanfillView()/ TODO: 在此处添加构造代码/设置多边形的个顶点Point0 = CPoint(550,400);Point1 = CPoint(350,600);Point2 = CPoint(250,350);Point3 = CPoint(350,50);Point4 = CPoint(500,250);Point5 = CPoint(600,50);Point6 = CPoint(800,450);CscanfillView:CscanfillView()BOOL CscanfillV

9、iew:PreCreateWindow(CREATESTRUCT& cs)/ TODO: 在此处通过修改/ CREATESTRUCT cs 来修改窗口类或样式return CView:PreCreateWindow(cs);/ CscanfillView 绘制void CscanfillView:OnDraw(CDC* pDC)CscanfillDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);if (!pDoc)return;/ TODO: 在此处为本机数据添加绘制代码pDC->Polygon(Point,7); /绘制多边形pDC-&g

10、t;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("P

11、6");/ CscanfillView 打印BOOL CscanfillView:OnPreparePrinting(CPrintInfo* pInfo)/ 默认准备return DoPreparePrinting(pInfo);void CscanfillView:OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)/ TODO: 添加额外的打印前进行的初始化过程void CscanfillView:OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)/ TODO: 添加打印后进行的

12、清理过程/ CscanfillView 诊断#ifdef _DEBUGvoid CscanfillView:AssertValid() constCView:AssertValid();void CscanfillView:Dump(CDumpContext& dc) constCView:Dump(dc);CscanfillDoc* CscanfillView:GetDocument() const / 非调试版本是内联的ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CscanfillDoc);return (CscanfillDoc*)

13、m_pDocument;#endif /_DEBUG/ CscanfillView 消息处理程序void CscanfillView:CreatBucket() /建立桶节点函数int ScanMin,ScanMax; /确定扫描线的最小值和最大值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(int i=ScanMin;

14、i<=ScanMax;i+) /建立桶节点if(ScanMin = i) /桶头结点HeadB = new Bucket; /建立桶的头结点CurrentB = HeadB; /CurrentB为Bucket当前节点指针CurrentB->Scanline = ScanMin;CurrentB->p = NULL; /没有连接边链表CurrentB->next = NULL;else /建立桶的其他节点CurrentB->next = new Bucket; /新建一个桶节点CurrentB = CurrentB->next; /使CurrentB指向新建的

15、桶节点CurrentB->Scanline = i;CurrentB->p = NULL; /没有连接边链表CurrentB->next = NULL;void CscanfillView:Et() /构造边表函数for(int i=0;i<Number;i+) /访问每个顶点CurrentB = HeadB; /从桶链表的头节点开始循环int j = i+1; /边的第二个顶点，Pointi和Pointj构成边if(j=Number) j=0; /保证多边形的闭合if(Pointj.y>Pointi.y) /终点比起点高while(CurrentB->Sc

16、anline!=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);Ei.next = NULL;CurrentE = CurrentB->p; /获得桶上链接边表的地址if(CurrentB->p=NULL) /当前桶节点上没有链接边节点CurrentE = &Ei; /赋边的起始地址CurrentB-&g

17、t;p=CurrentE; /第一个边节点直接连接到对应的桶中elsewhile(CurrentE->next!=NULL) /如果当前边已有边节点CurrentE = CurrentE->next; /移动指针到当前边的最后一个节点CurrentE->next = &Ei; /把当前边接上去if(Pointj.y<Pointi.y) /终点比起点低while(CurrentB->Scanline!=Pointj.y)CurrentB = CurrentB->next;Ei.x = Pointj.x;Ei.yMax = Pointi.y;Ei.k =

18、 (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;CurrentE->next=&Ei;CurrentB = NULL;CurrentE = NULL;void CscanfillView:AddEdge(A

19、ET * NewEdge) /插入临时边表函数T1 = HeadE;if(T1 = NULL) /边表为空，将边表置为TempEdgeT1 = NewEdge;HeadE =T1;elsewhile(T1->next!=NULL) /边表不为空，将TempEdge连在该边之后T1 = T1->next;T1->next = NewEdge;void CscanfillView:EdgeOrder() /对边表进行排序AET *F,*T;T1 = HeadE;if(T1 = NULL)return;if(T1->next= NULL) /如果该边表没有再连接边return

20、;elseF =HeadE->next;HeadE->next = NULL;while(F!=NULL)for (T=F, T1=HeadE; (T1!=NULL) && (T1->x < T->x); T2=T1, T1=T1->next);F = F->next;if(T1 = HeadE)HeadE = T; elseT2->next = T;T->next = T1; void CscanfillView:PolygonFill() /多边形填充函数HeadE = NULL;for(CurrentB = HeadB

21、;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(Temp

22、Edge); /将该边插入临时AET表EdgeOrder(); /边表按照x递增的顺序存放T1 = HeadE; /根据yMax抛弃扫描完的边节点if(T1 = NULL)return;while(CurrentB->Scanline>=T1->yMax) /放弃该节点，AET表指针后移，下闭上开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 = NUL