多邊形有效邊表填充算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上多邊形有效邊表填充算法案例效果如下：具體實現(xiàn)：（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: / 僅從序列化創(chuàng)建CscanfillView();DECLARE_DYNCREATE(CscanfillView)/ 屬性public:CscanfillDoc* GetDocument() const;/ 操作publ

3、ic:void PolygonFill(); /上閉下開填充多邊形void CreatBucket(); /建立桶節(jié)點void Et(); /構(gòu)造邊表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);/ 實現(xiàn)public:virtual CscanfillView();#ifdef _DEBUGvirtual void AssertValid() const;virtual void Dump(CDumpContext& dc) const;#endifprotected:COLORREF GetColor; /調(diào)色板CPoint Point7; /定義多邊形Buc

5、ket * HeadB,*CurrentB; /桶的頭結(jié)點和當前節(jié)點AET ENumber,*HeadE,*CurrentE,*T1,*T2; /有效邊表的節(jié)點/ 生成的消息映射函數(shù)protected:DECLARE_MESSAGE_MAP()public:afx_msg void OnMenuAET();#ifndef _DEBUG / scanfillView.cpp 中的調(diào)試版本inline CscanfillDoc* CscanfillView:GetDocument() const return reinterpret_cast<CscanfillDoc*>(m_pDoc

6、ument); #endif（6）實現(xiàn)視圖/ scanfillView.cpp : CscanfillView 類的實現(xiàn)/#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 構(gòu)造/析構(gòu)CscanfillView:CscanfillView()/ TODO: 在此處添加構(gòu)造代碼/設置多邊形的個頂點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: 在此處為本機數(shù)據(jù)添加繪制代碼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 / 非調(diào)試版本是內(nèi)聯(lián)的ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CscanfillDoc);return (CscanfillDoc*)

13、m_pDocument;#endif /_DEBUG/ CscanfillView 消息處理程序void CscanfillView:CreatBucket() /建立桶節(jié)點函數(shù)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+) /建立桶節(jié)點if(ScanMin = i) /桶頭結(jié)點HeadB = new Bucket; /建立桶的頭結(jié)點CurrentB = HeadB; /CurrentB為Bucket當前節(jié)點指針CurrentB->Scanline = ScanMin;CurrentB->p = NULL; /沒有連接邊鏈表CurrentB->next = NULL;else /建立桶的其他節(jié)點CurrentB->next = new Bucket; /新建一個桶節(jié)點CurrentB = CurrentB->next; /使CurrentB指向新建的

15、桶節(jié)點CurrentB->Scanline = i;CurrentB->p = NULL; /沒有連接邊鏈表CurrentB->next = NULL;void CscanfillView:Et() /構(gòu)造邊表函數(shù)for(int i=0;i<Number;i+) /訪問每個頂點CurrentB = HeadB; /從桶鏈表的頭節(jié)點開始循環(huán)int j = i+1; /邊的第二個頂點，Pointi和Pointj構(gòu)成邊if(j=Number) j=0; /保證多邊形的閉合if(Pointj.y>Pointi.y) /終點比起點高while(CurrentB->Sc

16、anline!=Pointi.y) /在桶內(nèi)尋找該邊的yMinCurrentB = CurrentB->next; /移到下一個桶節(jié)點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) /當前桶節(jié)點上沒有鏈接邊節(jié)點CurrentE = &Ei; /賦邊的起始地址CurrentB-&g

17、t;p=CurrentE; /第一個邊節(jié)點直接連接到對應的桶中elsewhile(CurrentE->next!=NULL) /如果當前邊已有邊節(jié)點CurrentE = CurrentE->next; /移動指針到當前邊的最后一個節(jié)點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) /插入臨時邊表函數(shù)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() /多邊形填充函數(shù)HeadE = NULL;for(CurrentB = HeadB

21、;CurrentB!=NULL;CurrentB=CurrentB->next) /訪問所有的桶節(jié)點for(CurrentE = CurrentB->p;CurrentE!=NULL;CurrentE = CurrentE->next) /桶中所有邊節(jié)點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; /根據(jù)yMax拋棄掃描完的邊節(jié)點if(T1 = NULL)return;while(CurrentB->Scanline>=T1->yMax) /放棄該節(jié)點，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) /跳過一個節(jié)點T2->next = T1->next;T1->next = NUL