多边形有效边表填充算法

1、 多边形有效边表填充算法 案例效果如下： 具体实现： （1） 新建MFC项目： （2）分别添加类：AET 和Bucket 中定义在AET.h once #pragma AET class : public); AET( void); void AET( x; double yMax; int k; doubleAET * next; ; Bucket.h中定义在once #pragma#include AET.h class Bucket : public); Bucket(void); Bucket( void Scanline; int AET *p; Bucket * next; ; ）

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

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

4、BeginPrinting(CDC* pDC, CPrintInfo* pInfo); void virtual OnEndPrinting(CDC* pDC, CPrintInfo* pInfo); virtual void 实现/ : public CscanfillView(); virtual _DEBUG #ifdef; AssertValid() virtualvoidconst; virtual Dump(CDumpContext& dc) void const#endif : protected COLORREF GetColor; /调色板 CPoint Point7; /定

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

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

7、anfillView, 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:Cscanfill

8、View() / 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 CscanfillView:PreCreateWindow(CREATESTRUCT& cs) 在

9、此处通过修改/ TODO: 来修改窗口类或样式/ CREATESTRUCT cs CView:PreCreateWindow(cs); return / CscanfillView 绘制 CscanfillView:OnDraw(CDC* pDC) void CscanfillDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); (!pDoc) if ; return / TODO: 在此处为本机数据添加绘制代码 绘制多边形pDC-Polygon(Point,7); / pDC-TextOutW(550,410,_T(/停尰 ); 注意文本的输出); 停

10、就 pDC-TextOutW(350,600,_T(); pDC-TextOutW(230,340,_T(停尲 ); pDC-TextOutW(350,30,_T(停尳); pDC-TextOutW(490,220,_T(停尴); 停尵pDC-TextOutW(600,30,_T(); 停尶pDC-TextOutW(805,450,_T( / CscanfillView 打印 BOOL CscanfillView:OnPreparePrinting(CPrintInfo* pInfo) 默认准备 / DoPreparePrinting(pInfo); return ) CscanfillVie

11、w:OnBeginPrinting(CDC* /*pInfo*/*pDC*/, CPrintInfo* void 添加额外的打印前进行的初始化过程 / TODO: ) , CPrintInfo* /*pInfo*/void CscanfillView:OnEndPrinting(CDC* /*pDC*/ 添加打印后进行的清理过程/ TODO: 诊断/ CscanfillView _DEBUG #ifdefconst void CscanfillView:AssertValid() CView:AssertValid(); const void CscanfillView:Dump(CDumpC

12、ontext& dc) CView:Dump(dc); constCscanfillDoc* CscanfillView:GetDocument() / 非调试版本是内联的 ASSERT(m_pDocument-IsKindOf(RUNTIME_CLASS(CscanfillDoc); (CscanfillDoc*)m_pDocument; return /_DEBUG #endif / CscanfillView 消息处理程序 /void CscanfillView:CreatBucket() 建立桶节点函数 ScanMin,ScanMax; int/确定扫描线的最小值和最大值ScanMax

13、 = ScanMin = Point0.y; i=1;iNumber;i+) int for( (Pointi.yScanMax) if 扫描线的最大值 /ScanMax = Pointi.y; (forint i=ScanMin;iScanline = ScanMin; CurrentB-p = NULL; / 没有连接边链表CurrentB-next = NULL; else / 建立桶的其他节点 新建一个桶节点 / Bucket; newCurrentB-next = 使 /CurrentB 指向新建的桶节点CurrentB = CurrentB-next; CurrentB-Scanl

14、ine = i; CurrentB-p = NULL; / 没有连接边链表 CurrentB-next = NULL; void CscanfillView:Et() 构造边表函数/ i=0;iPointi.y) if/终点比起点高 yMin /while(CurrentB-Scanline!=Pointi.y) 在桶内寻找该边的 移到下一个桶节点 / CurrentB = CurrentB-next; /Ei.x = Pointi.x; AET计算表的值 Ei.yMax = Pointj.y; (Pointj.x-Pointi.x)/(Pointj.y-Pointi.y); double E

15、i.k = ( Ei.next = NULL; / CurrentE = CurrentB-p; 获得桶上链接边表的地址 if /(CurrentB-p=NULL) 当前桶节点上没有链接边节点 赋边的起始地址/ CurrentE = &Ei; 第一个边节点直接连接到对应的桶中/ CurrentB-p=CurrentE; else while (CurrentE-next!=NULL) /如果当前边已有边节点 移动指针到当前边的最后一个节点/ CurrentE = CurrentE-next; 把当前边接上去/ CurrentE-next = &Ei; if终点比起点低 (Pointj.ySca

16、nline!=Pointj.y) while CurrentB = CurrentB-next; Ei.x = Pointj.x; Ei.yMax = Pointi.y; (Pointi.x-Pointj.x)/(Pointi.y-Pointj.y); doubleEi.k = ( Ei.next = NULL; CurrentE = CurrentB-p; (CurrentE = NULL) if CurrentE=&Ei; CurrentB-p = CurrentE; else (CurrentE-next!=NULL) while CurrentE = CurrentE-next; Cu

17、rrentE-next=&Ei; CurrentB = NULL; CurrentE = NULL; void/ CscanfillView:AddEdge(AET * NewEdge) 插入临时边表函数 T1 = HeadE; TempEdge if(T1 = NULL) /边表为空，将边表置为 T1 = NewEdge; HeadE =T1; else 连在该边之后边表不为空，将(T1-next!=NULL) while /TempEdge T1 = T1-next; T1-next = NewEdge; /void CscanfillView:EdgeOrder() 对边表进行排序 AE

18、T *F,*T; T1 = HeadE; (T1 = NULL) if ; return 如果该边表没有再连接边(T1-next= NULL) if / ; return else F =HeadE-next; HeadE-next = NULL; (F!=NULL) while (T=F, T1=HeadE; (T1!=NULL) & (T1-x x); T2=T1, T1=T1-next); for F = F-next; (T1 = HeadE) if HeadE = T; else T2-next = T; T-next = T1; void多边形填充函数 CscanfillView:

19、PolygonFill() / HeadE = NULL; 访问所有的桶节点for(CurrentB = HeadB;CurrentB!=NULL;CurrentB=CurrentB-next) / (CurrentE = CurrentB-p;CurrentE!=NULL;CurrentE = CurrentE-next) for 桶中所有边节点 / AET; new AET * TempEdge = TempEdge-x = CurrentE-x; TempEdge-yMax = CurrentE-yMax; TempEdge-k = CurrentE-k; TempEdge-next =

20、 NULL; 表 AET 将该边插入临时/AddEdge(TempEdge); 递增的顺序存放边表按照 EdgeOrder(); /x T1 = HeadE; yMax/根据 抛弃扫描完的边节点(T1 = NULL) if ; return AET/ (CurrentB-Scanline=T1-yMax) while放弃该节点，表指针后移，下闭上开 T1 = T1-next; HeadE = T1; (HeadE = NULL) if ; return (T1-next!=NULL) if T2 = T1; T1 = T2-next; (T1!=NULL) while if /跳过一个节点(CurrentB-Scanline=T1-yMax) T2-next = T1-next; T1-next = NULL; T1 =