1、精選優質文檔-傾情為你奉上實驗三 多邊形的有效邊表填充算法一、實驗目的與要求1、理解多邊形的掃描轉換原理、方法； 2、掌握有效邊表填充算法；3、掌握鏈表的建立、添加結點、刪除節點的基本方法；3、掌握基于鏈表的排序操作。二、實驗內容在實驗二所實現工程的基礎上，實現以下內容并把實現函數封裝在類CMyGL 中。 1、C+實現有效邊表算法進行多邊形掃描轉換 2、利用1進行多邊形掃描轉換和區域填充的實現； 三、實驗原理 請同學們根據教材及上課的PPT獨立完成。四、實驗步驟（程序實現）。1、建立并選擇工程項目。打開VC6.0->菜單File 的New 項,在projects 屬性頁選擇MFC App

2、Wizard(exe)項，在Project name 中輸入一個工程名,如“Sample”。單文檔。2、新建一個圖形類。選擇菜單Insert New class，Class type 選擇“Generic Class”，Name 輸入類名，如“CMyCG。3、向新建的圖形類中添加成員函數（實際就是加入實驗要求實現的圖形生成算法的實現代碼）。在工作區中直接鼠標右鍵單擊，選擇“Add Member Function”項，添加繪制圓的成員函數。void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC)添加其他成員函數：Creat

3、Bucket();CreatET();AddEdge();EdgeOrder();4、成員函數的實現。實現有效邊表填充算法。這一部分需要同學們去實現。參考實現：多邊形的有效邊表填充算法的基本過程為：1、定義多邊形：2、初始化桶3、建立邊表4、多邊形填充1) 對每一條掃描線，將該掃描線上的邊結點插入到臨時AET表中，HeadE.2) 對臨時AET表排序，按照x遞增的順序存放。3) 根據AET表中邊表結點的ymax拋棄掃描完的邊結點，即ymax>=scanline4) 掃描AET表，填充掃描線和多邊形相交的區間。5) 根據的邊連貫性，更新AET表。0、構造桶結點的數據結構和有效邊表的數據結構

4、：有效邊表的數據結構：類AETclass AET public:AET();virtual AET();double x;int yMax;double k;/代替1/kAET *next;桶結點的數據結構:類Bucketclass Bucket public:Bucket();virtual Bucket();int ScanLine;AET *p;/桶上的邊表指針Bucket *next;1、定義多邊形：CPoint Point7;/定義多邊形/設置多邊形的7個頂點Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoi

5、nt(250,350);/P2Point3=CPoint(350,50);/P3Point4=CPoint(500,250);/P4Point5=CPoint(600,50);/P5Point6=CPoint(800,450);/P62、初始化桶Bucket* CreatBucket(int number,CPoint *Point)int ScanMin,ScanMax;Bucket *HeadB,*CurrentB;ScanMin = ScanMax = Point0.y;for(int i = 1;i<number;i+)/找最低和最高掃描線for(i = ScanMin;i<

6、;=ScanMax;i+)if(i = ScanMin) /桶頭結點HeadB = new Bucket();/建立桶的頭結點CurrentB = HeadB; /CurrentB為Bucket當前結點指針CurrentB->ScanLine = i;CurrentB->p = NULL; /沒有連接邊鏈表CurrentB->next = NULL;Else/建立桶的其它結點return HeadB;3、建立邊表Bucket * CreatET(int number,CPoint *Point)Bucket *HeadB;Bucket *CurrentB;AET *Curre

7、ntE,*Edge;HeadB = CreateBucket(number,Point);for (int i = 0;i<number;i+)/訪問每個頂點int j = i + 1; /邊的第二個頂點，Pointi和Pointj構成邊if (j = number)/保證多邊形的閉合j = 0;CurrentB = HeadB;/從桶鏈表的頭結點開始搜索邊（i,j）放入哪個桶if(Pointi.y<Pointj.y)/終點比起點高while(Pointi.y>CurrentB.ScanLine)/在桶內尋找該邊的yMinCurrentB = CrrentB->next

8、;/移到下一個桶結點Edge = new AET();/構造有效邊表結點，計算AET表的值Edge->x = Pointi.x;Edge->ymax = Pointj.y;Edge->k = double(Pointj.x-Pointi.x)/(Pointj.y-Pointi.y);/代表1/kif(CurrentB->p = NULL)/當前桶結點上沒有鏈接邊結點Current->p = Edge;/第一個邊結點直接連接到對應的桶中else/如果當前邊已連有邊結點CurrentE = CurrentB->p;/移動指針到當前邊的最后一個邊結點/把當前邊接上

9、去if(Pointj.y<Pointi.y)/終點比起點低/終點比起點高CurrentE = NULL;CurrentB = NULL;AET = NULL;return HeadB;4、多邊形填充1) 對每一條掃描線，將該掃描線上的邊結點插入到臨時AET表中，HeadE.2) 對臨時AET表排序，按照x遞增的順序存放。3) 根據AET表中邊表結點的ymax拋棄掃描完的邊結點，即ymax>=scanline4) 掃描AET表，填充掃描線和多邊形相交的區間。5) 根據的邊連貫性，更新AET表。void PolygonFill (int number,CPoint *p,COLORRE

10、F fillcolor,CDC *pDC)/多邊形填充HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)/訪問所有桶結點1) 對每一條掃描線，將該掃描線上的邊結點插入到臨時AET表中，HeadEfor(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)/訪問桶中排序前的邊結點AET *TempEdge=new AET;TempEdge->x=CurrentE->x;TempEdge->yMax=Curr

11、entE->yMax;TempEdge->k=CurrentE->k;TempEdge->next=NULL;AddEdge(TempEdge);/將該邊插入臨時Aet表2) 對臨時AET表排序，按照x遞增的順序存放。EdgeOrder();/使得邊表按照x遞增的順序存放3) 根據AET表中邊表結點的ymax拋棄掃描完的邊結點，即ymax>=scanlineT1=HeadE;/根據ymax拋棄掃描完的邊結點if(T1=NULL)return;while(CurrentB->ScanLine>=T1->yMax)/放棄該結點，Aet表指針后移（下閉

12、上開）T1=T1->next;HeadE=T1;if(HeadE=NULL)return;if(T1->next!=NULL)T2=T1;T1=T2->next;while(T1!=NULL)/根據AET表中邊表結點的ymax拋棄掃描完的邊結點，即ymax>=ScanLine4) 掃描AET表，填充掃描線和多邊形相交的區間。bool In=false;/設置一個BOOL變量In，初始值為假double xb,xe;/掃描線的起點和終點for(T1=HeadE;T1!=NULL;T1=T1->next)/填充掃描線和多邊形相交的區間if(In=false)xb=T1

13、->x;In=true;/每訪問一個結點,把In值取反一次else/如果In值為真，則填充從當前結點的x值開始到下一結點的x值結束的區間xe=T1->x-1;/左閉右開/填充Sleep(1);/延時1ms,提高填充過程的可視性In=FALSE;5) 根據的邊連貫性，更新AET表。/利用邊的連貫性，更新交點信息delete HeadB; delete CurrentB;delete CurrentE;delete HeadE;5、圖形類的使用 （1）、圖形類對象的定義。首先在“C*View”（本例中是CSampleView）類的頭文件中加入圖形類的頭文件，使圖形類能在C*View 中

14、被辨識和使用；然后，在C*View 類頭文件中實例化圖形類，即定義一個圖形類的對象。在public屬性區加入：CmyCG m_cg;（2）、圖形類對象的使用。在“C*View”類中有一個成員函數void OnDraw(CDC* pDC),找到該函數的實現。在其中加入對圖形類對象的使用代碼：m_cg-> PolygonFill(_,_,_,_);/測試：填充的多邊形的七個頂點為：Point0=CPoint(550,400);/P0Point1=CPoint(350,600);/P1Point2=CPoint(250,350);/P2Point3=CPoint(350,50);/P3Poin

15、t4=CPoint(500,250);/P4Point5=CPoint(600,50);/P5Point6=CPoint(800,450);/P6在進行填充之前先繪制多邊形的輪廓。6、程序的調試、運行。五、實驗結果抓圖與結果分析 1、請給出頂點數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);/P6的多邊形，填充顏色為紅色的填充效果。