多邊形的有效邊表填充算法

實(shí)驗(yàn)三 多邊形的有效邊表填充算法一、實(shí)驗(yàn)?zāi)康呐c要求1、理解多邊形的掃描轉(zhuǎn)換原理、方法； 2、掌握有效邊表填充算法；3、掌握鏈表的建立、添加結(jié)點(diǎn)、刪除節(jié)點(diǎn)的基本方法；3、掌握基于鏈表的排序操作。二、實(shí)驗(yàn)內(nèi)容在實(shí)驗(yàn)二所實(shí)現(xiàn)工程的基礎(chǔ)上，實(shí)現(xiàn)以下內(nèi)容并把實(shí)現(xiàn)函數(shù)封裝在類CMyGL 中。 1、C+實(shí)現(xiàn)有效邊表算法進(jìn)行多邊形掃描轉(zhuǎn)換 2、利用1進(jìn)行多邊形掃描轉(zhuǎn)換和區(qū)域填充的實(shí)現(xiàn)； 三、實(shí)驗(yàn)原理 請(qǐng)同學(xué)們根據(jù)教材及上課的PPT獨(dú)立完成。四、實(shí)驗(yàn)步驟（程序?qū)崿F(xiàn)）。1、建立并選擇工程項(xiàng)目。打開VC6.0-菜單File 的New 項(xiàng),在projects 屬性頁(yè)選擇MFC AppWizard(exe)項(xiàng)，在Project name 中輸入一個(gè)工程名,如“Sample”。單文檔。2、新建一個(gè)圖形類。選擇菜單Insert New class，Class type 選擇“Generic Class”，Name 輸入類名，如“CMyCG。3、向新建的圖形類中添加成員函數(shù)（實(shí)際就是加入實(shí)驗(yàn)要求實(shí)現(xiàn)的圖形生成算法的實(shí)現(xiàn)代碼）。在工作區(qū)中直接鼠標(biāo)右鍵單擊，選擇“Add Member Function”項(xiàng)，添加繪制圓的成員函數(shù)。void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC)添加其他成員函數(shù)：CreatBucket();CreatET();AddEdge();EdgeOrder();4、成員函數(shù)的實(shí)現(xiàn)。實(shí)現(xiàn)有效邊表填充算法。這一部分需要同學(xué)們?nèi)?shí)現(xiàn)。參考實(shí)現(xiàn)：多邊形的有效邊表填充算法的基本過程為：1、定義多邊形：2、初始化桶3、建立邊表4、多邊形填充1) 對(duì)每一條掃描線，將該掃描線上的邊結(jié)點(diǎn)插入到臨時(shí)AET表中，HeadE.2) 對(duì)臨時(shí)AET表排序，按照x遞增的順序存放。3) 根據(jù)AET表中邊表結(jié)點(diǎn)的ymax拋棄掃描完的邊結(jié)點(diǎn)，即ymax=scanline4) 掃描AET表，填充掃描線和多邊形相交的區(qū)間。5) 根據(jù)的邊連貫性，更新AET表。0、構(gòu)造桶結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)和有效邊表的數(shù)據(jù)結(jié)構(gòu)：有效邊表的數(shù)據(jù)結(jié)構(gòu)：類AETclass AET public:AET();virtual AET();double x;int yMax;double k;/代替1/kAET *next;桶結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu):類Bucketclass Bucket public:Bucket();virtual Bucket();int ScanLine;AET *p;/桶上的邊表指針Bucket *next;1、定義多邊形：CPoint Point7;/定義多邊形/設(shè)置多邊形的7個(gè)頂點(diǎn)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);/P62、初始化桶Bucket* CreatBucket(int number,CPoint *Point)int ScanMin,ScanMax;Bucket *HeadB,*CurrentB;ScanMin = ScanMax = Point0.y;for(int i = 1;inumber;i+)/找最低和最高掃描線for(i = ScanMin;iScanLine = i;CurrentB-p = NULL; /沒有連接邊鏈表CurrentB-next = NULL;Else/建立桶的其它結(jié)點(diǎn)return HeadB;3、建立邊表Bucket * CreatET(int number,CPoint *Point)Bucket *HeadB;Bucket *CurrentB;AET *CurrentE,*Edge;HeadB = CreateBucket(number,Point);for (int i = 0;inumber;i+)/訪問每個(gè)頂點(diǎn)int j = i + 1; /邊的第二個(gè)頂點(diǎn)，Pointi和Pointj構(gòu)成邊if (j = number)/保證多邊形的閉合j = 0;CurrentB = HeadB;/從桶鏈表的頭結(jié)點(diǎn)開始搜索邊（i,j）放入哪個(gè)桶if(Pointi.yCurrentB.ScanLine)/在桶內(nèi)尋找該邊的yMinCurrentB = CrrentB-next;/移到下一個(gè)桶結(jié)點(diǎn)Edge = new AET();/構(gòu)造有效邊表結(jié)點(diǎn)，計(jì)算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)/當(dāng)前桶結(jié)點(diǎn)上沒有鏈接邊結(jié)點(diǎn)Current-p = Edge;/第一個(gè)邊結(jié)點(diǎn)直接連接到對(duì)應(yīng)的桶中else/如果當(dāng)前邊已連有邊結(jié)點(diǎn)CurrentE = CurrentB-p;/移動(dòng)指針到當(dāng)前邊的最后一個(gè)邊結(jié)點(diǎn)/把當(dāng)前邊接上去if(Pointj.y=scanline4) 掃描AET表，填充掃描線和多邊形相交的區(qū)間。5) 根據(jù)的邊連貫性，更新AET表。void PolygonFill (int number,CPoint *p,COLORREF fillcolor,CDC *pDC)/多邊形填充HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB-next)/訪問所有桶結(jié)點(diǎn)1) 對(duì)每一條掃描線，將該掃描線上的邊結(jié)點(diǎn)插入到臨時(shí)AET表中，HeadEfor(CurrentE=CurrentB-p;CurrentE!=NULL;CurrentE=CurrentE-next)/訪問桶中排序前的邊結(jié)點(diǎn)AET *TempEdge=new AET;TempEdge-x=CurrentE-x;TempEdge-yMax=CurrentE-yMax;TempEdge-k=CurrentE-k;TempEdge-next=NULL;AddEdge(TempEdge);/將該邊插入臨時(shí)Aet表2) 對(duì)臨時(shí)AET表排序，按照x遞增的順序存放。EdgeOrder();/使得邊表按照x遞增的順序存放3) 根據(jù)AET表中邊表結(jié)點(diǎn)的ymax拋棄掃描完的邊結(jié)點(diǎn)，即ymax=scanlineT1=HeadE;/根據(jù)ymax拋棄掃描完的邊結(jié)點(diǎn)if(T1=NULL)return;while(CurrentB-ScanLine=T1-yMax)/放棄該結(jié)點(diǎn)，Aet表指針后移（下閉上開）T1=T1-next;HeadE=T1;if(HeadE=NULL)return;if(T1-next!=NULL)T2=T1;T1=T2-next;while(T1!=NULL)/根據(jù)AET表中邊表結(jié)點(diǎn)的ymax拋棄掃描完的邊結(jié)點(diǎn)，即ymax=ScanLine4) 掃描AET表，填充掃描線和多邊形相交的區(qū)間。bool In=false;/設(shè)置一個(gè)BOOL變量In，初始值為假double xb,xe;/掃描線的起點(diǎn)和終點(diǎn)for(T1=HeadE;T1!=NULL;T1=T1-next)/填充掃描線和多邊形相交的區(qū)間if(In=false)xb=T1-x;In=true;/每訪問一個(gè)結(jié)點(diǎn),把In值取反一次else/如果In值為真，則填充從當(dāng)前結(jié)點(diǎn)的x值開始到下一結(jié)點(diǎn)的x值結(jié)束的區(qū)間xe=T1-x-1;/左閉右開/填充Sleep(1);/延時(shí)1ms,提高填充過程的可視性In=FALSE;5) 根據(jù)的邊連貫性，更新AET表。/利用邊的連貫性，更新交點(diǎn)信息delete HeadB; delete CurrentB;delete CurrentE;delete HeadE;5、圖形類的使用 （1）、圖形類對(duì)象的定義。首先在“C*View”（本例中是CSampleView）類的頭文件中加入圖形類的頭文件，使圖形類能在C*View 中被辨識(shí)和使用；然后，在C*View 類頭文件中實(shí)例化圖形類，即定義一個(gè)圖形類的對(duì)象。在public屬性區(qū)加入：CmyCG m_cg;（2）、圖形類對(duì)象的使用。在“C*View”類中有一個(gè)成員函數(shù)void OnDraw(CDC* pDC),找到該函數(shù)的實(shí)現(xiàn)。在其中加入對(duì)圖形類對(duì)象的使用代碼：m_cg- PolygonFill(_,_,_,_);/測(cè)試：填充的多邊形的七個(gè)頂點(diǎn)為：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在進(jìn)行填充之前先繪制多邊形的輪廓。6、程序的調(diào)試、運(yùn)行。五、實(shí)驗(yàn)結(jié)果抓圖與結(jié)果分析 1、請(qǐng)給出頂點(diǎn)數(shù)7個(gè)，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的多邊形，填充顏色為紅色的填充效果。2、請(qǐng)給出頂點(diǎn)數(shù)6個(gè)，Point0