《計(jì)算機(jī)圖形學(xué)》有序邊表填充算法

1、實(shí) 驗(yàn) 報(bào) 告 一、 實(shí)驗(yàn)?zāi)康?、 掌握有序邊表算法填充多邊形區(qū)域；2、 理解多邊形填充算法的意義；3、 增強(qiáng)C語言編程能力。二、 算法原理介紹根據(jù)多邊形內(nèi)部點(diǎn)的連續(xù)性知：一條掃描線與多邊形的交點(diǎn)中，入點(diǎn)和出點(diǎn)之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。所以，對所有的掃描線填充入點(diǎn)到出點(diǎn)之間所有的點(diǎn)就可填充多邊形。判斷掃描線上的點(diǎn)是否在多邊形之內(nèi)，對于一條掃描線，多邊形的掃描轉(zhuǎn)換過程可以分為四個(gè)步驟：（1）求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)；（2）排序：把所有交點(diǎn)按x值遞增順序排序；（3）配對：第一個(gè)與第二個(gè)，第三個(gè)與第四個(gè)等等；每對交點(diǎn)代表掃描線與多邊 形的一個(gè)相交區(qū)間;（4）著色：把相交區(qū)間內(nèi)的象素置成

2、多邊形顏色，把相交區(qū)間外的象素置成背景色。p1,p3,p4,p5屬于局部極值點(diǎn)，要把他們兩次存入交點(diǎn)表中。 如掃描線y=7上的交點(diǎn)中，有交點(diǎn)(2,7,13)，按常規(guī)方法填充不正確，而要把頂點(diǎn)(7,7)兩次存入交點(diǎn)表中(2,7,7,13)。p2，p6為非極值點(diǎn)，則不用如上處理。為了提高效率，在處理一條掃描線時(shí)，僅對與它相交的多邊形的邊進(jìn)行求交運(yùn)算。把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，稱此鏈表為活性邊表(AET)。 對每一條掃描線都建立一個(gè)與它相交的多邊形的活性邊表（AET）。每個(gè)AET的一個(gè)節(jié)點(diǎn)代表一條活性邊，它包含三項(xiàng)內(nèi)容1. x -當(dāng)前掃

3、描線與這條邊交點(diǎn)的x坐標(biāo)；2. x -該邊與當(dāng)前掃描線交點(diǎn)到下一條掃描線交點(diǎn)的x增量；3. ymax -該邊最高頂點(diǎn)相交的掃描線號。每條掃描線的活性邊表中的活性邊節(jié)點(diǎn)按照各活性邊與掃描線交點(diǎn)的x值遞增排序連接在一起。當(dāng)掃描線y移動(dòng)到下一條掃描線y = y+1時(shí)，活性邊表需要更新，即刪去不與新掃描線相交的多邊形邊，同時(shí)增加與新掃描線相交的多邊形邊，并根據(jù)增量法重新計(jì)算掃描線與各邊的交點(diǎn)x。當(dāng)多邊形新邊表ET構(gòu)成后，按下列步驟進(jìn)行：1 對每一條掃描線i，初始化ET表的表頭指針ETi；2 將ymax = i的邊放入ETi中；3 使y =多邊形最低的掃描線號；4 初始化活性邊表AET為空；5 循環(huán)，直

4、到AET和ET為空。l 將新邊表ET中對應(yīng)y值的新邊節(jié)點(diǎn)插入到AET表。l 遍歷AET表，將兩兩配對的交點(diǎn)之間填充給定顏色值。l 遍歷AET表，將 ymax= y的邊節(jié)點(diǎn)從AET表中刪除，并將ymax y的各邊節(jié)點(diǎn)的x值遞增x；并重新排序。l y增加1。三、 程序源代碼#include graphics.h#define WINDOW_HEIGHT 480#define NULL 0#include alloc.h#include stdio.h#include dos.h#include conio.h typedef struct tEdge /*typedef是將結(jié)構(gòu)定義成數(shù)據(jù)類型*/

5、int ymax; /* 邊所交的最高掃描線號 */float x; /*當(dāng)前掃描線與邊的交點(diǎn)的x值 */float dx; /*從當(dāng)前掃描線到下一條掃描線之間的x增量*/struct tEdge *next;Edge; typedef struct pointint x,y;POINT;/*將結(jié)點(diǎn)插入邊表的主體函數(shù)*/void InsertEdge(Edge *list,Edge *edge)/*活性邊edge插入活性邊表list中*/ Edge *p,*q=list;p=q-next; /*記住q原來所指之結(jié)點(diǎn)*/while(p!=NULL) /*按x值非遞減順序增加邊表*/if(edge

6、-xx) /*要插入的邊的x較大不應(yīng)該在當(dāng)前插入*/p=NULL; else /*要插入的邊的x較小應(yīng)該在當(dāng)前插入*/q=p; p=p-next;edge-next=q-next; /*使欲插入之結(jié)點(diǎn)edge指向q原來所指之結(jié)點(diǎn)*/q-next=edge; /*使q指向插入之結(jié)點(diǎn)*/int yNext(int k,int cnt,POINT *pts) /*對于多邊形中的某個(gè)頂點(diǎn)序號k(0,1.6)，返回下一頂點(diǎn)的縱坐標(biāo),如果這2個(gè)頂點(diǎn)所在邊是 水平的，則順延，即返回第(k+2)個(gè)頂點(diǎn)的縱坐標(biāo)),cnt是頂點(diǎn)個(gè)數(shù)+1,pts指向多邊形頂點(diǎn)結(jié)構(gòu)體的指針*/int j;if(k+1)(cnt-1)

7、/*當(dāng)前頂點(diǎn)為最后一個(gè)頂點(diǎn)，則下一個(gè)頂點(diǎn)為第0個(gè)頂點(diǎn) */j=0;elsej=k+1; /*當(dāng)前頂點(diǎn)不是最后一個(gè)頂點(diǎn)，下一個(gè)頂點(diǎn)為數(shù)組下標(biāo)加一*/while(ptsk.y=ptsj.y) /*掃描線掃過平行頂點(diǎn)，需分情況找到當(dāng)前頂點(diǎn)下下個(gè)頂點(diǎn)*/if(j+1)(cnt-1)j=0;elsej+;return(ptsj.y); /*返回下一個(gè)頂點(diǎn)的y值 */* 計(jì)算增量，修改AET*/*生成邊表結(jié)點(diǎn)，并插入到邊表中的主體函數(shù)*/void MakeEdgeRec(POINT lower,POINT upper,int yComp,Edge *edge,Edge *edges) /*把邊結(jié)點(diǎn)edge

8、,放到lower.y掃描線所在的邊結(jié)點(diǎn)指針數(shù)組edges中 */ edge-dx=(float)(upper.x-lower.x)/(upper.y-lower.y); edge-x=lower.x; if(upper.yymax=upper.y-1; /*縮短上層頂點(diǎn)*/ /*奇點(diǎn)，應(yīng)該把這點(diǎn)當(dāng)作兩個(gè)點(diǎn)而分開，所以把y的最大值減一，向下移動(dòng)*/ elseedge-ymax=upper.y; /*不是奇點(diǎn)，不需改變y值 */ insertEdge(edgeslower.y,edge); /*插入一個(gè)邊緣掃描線，插入到列表 */ /*創(chuàng)建邊表的主體函數(shù)*/void BuildEdgeList(i

9、nt cnt,POINT *pts,Edge *edges) /*建立新邊表,cnt:多邊形頂點(diǎn)個(gè)數(shù)+1,edges:指向活性邊結(jié)點(diǎn)的指針數(shù)組*/ Edge *edge; POINT v1,v2; int i,yPrev=ptscnt-2.y; /*當(dāng)前頂點(diǎn)的前一個(gè)頂點(diǎn)的y值，在當(dāng)前頂點(diǎn)不是奇點(diǎn)時(shí)使用該參數(shù)*/ v1.x=ptscnt-1.x; v1.y=ptscnt-1.y; for(i=0;icnt;i+) v2=ptsi;if(v1.y!=v2.y) /*非水平線*/ edge=(Edge *)malloc(sizeof(Edge);edge=(Edge*)malloc(sizeof(E

10、dge); if(v1.ynext; /*查找當(dāng)前掃描線對應(yīng)的y桶*/while(p) /*y桶不空*/q=p-next; /*找到最后一個(gè)邊結(jié)點(diǎn)，插入*/ InsertEdge(active,p); /*把更新后的邊表重新插入邊表中保存*/ p=q; /*填充一對交點(diǎn)的主體函數(shù)*/void FillScan(int scan,Edge *active,int color) /*填充掃描線:填充掃描線上,且在下一結(jié)點(diǎn)到再下一結(jié)點(diǎn)之間的點(diǎn)*/Edge *p1,*p2;int i;p1=active-next;while(p1)p2=p1-next;for(i=p1-x;ix;i+)putpixe

11、l(int)i,scan,color); /*畫出圖形內(nèi)部的點(diǎn)*/ p1=p2-next; /*活性表的下一條邊表 */void DeleteAfter(Edge *q) /*刪除鏈表中結(jié)點(diǎn),刪除邊結(jié)點(diǎn)q的后續(xù)結(jié)點(diǎn)p*/ Edge *p=q-next;q-next=p-next; /*刪除結(jié)點(diǎn)*/free(p); /* 刪除 y=ymax 的邊 */*填充完后，更新活動(dòng)邊表的主體函數(shù)*/void UpdateActiveList(int scan,Edge *active) /*刪除掃描線scan完成交點(diǎn)計(jì)算的活性邊,同時(shí)更新交點(diǎn)x域*/Edge *q=active,*p=active-nex

12、t;while(p)if(scan=p-ymax) /*掃描線超過邊的最大y值，此條邊的節(jié)點(diǎn)應(yīng)該刪掉*/ p=p-next; deleteAfter(q);else /*掃描線未超過邊的最大y值，相應(yīng)的x值增加*/ p-x=p-x+p-dx; q=p;p=p-next;/*對活性邊表結(jié)點(diǎn)重新排序的主體函數(shù)*/void ResortActiveList(Edge *active) /*活性邊表active中的結(jié)點(diǎn)按x域從小到大重新排序*/Edge *q,*p=active-next;active-next=NULL;while(p)q=p-next; InsertEdge(active,p);

13、/*把更新后的邊表重新插入邊表中保存 */ p=q;/*多邊形填充的主體程序*/void ScanFill(int cnt,POINT *pts,int color) /*填充函數(shù),輸入:多邊形頂點(diǎn)個(gè)數(shù)+1=cnt, 指向多邊形頂點(diǎn)的指針數(shù)組pts*/Edge *edgesWINDOW_HEIGHT,*active;int i,scan,scanmax=0,scanmin=WINDOW_HEIGHT;for(i=0;icnt-1;i+) /*求掃描線的最大值最小值*/if(scanmaxptsi.y)scanmin=ptsi.y;for(scan=scanmin;scannext=NULL;B

14、uildEdgeList(cnt,pts,edges); /*建立有序邊表*/active=(Edge *)malloc(sizeof(Edge);active-next=NULL;for(scan=scanmin;scannext) /*活性邊表不為空*/FillScan(scan,active,color); /*填充當(dāng)前掃描線*/ UpdateActiveList(scan,active); /*更新活化邊表*/ ResortActiveList(active); /*重排活化邊表*/*開始菜單*/void main() POINT pts7; /*保存數(shù)組*/int gdrive=DE

15、TECT,gmode;pts0.x=100;pts0.y=40; /*多邊形頂點(diǎn)x、y坐標(biāo)*/pts1.x=220;pts1.y=140;pts2.x=280;pts2.y=80;pts3.x=350;pts3.y=300;pts4.x=200;pts4.y=380;pts5.x=50;pts5.y=280;pts6.x=100;pts6.y=40; /*合并桶中的新邊，按次序插入到 AET 中*/ initgraph(&gdrive,&gmode,C:TC3.0BGI); /*設(shè)置graphic模式*/ScanFill(7,pts,2);getch();四、 實(shí)驗(yàn)結(jié)果圖1 用有序邊表算法生成的多邊形五、 總結(jié)與體會實(shí)驗(yàn)步驟1) 分析多邊形區(qū)域掃描線填充算法的原理，確定算法流程1 初始化：構(gòu)造邊表，AET表置空2 將第一個(gè)不空的ET表中的邊插入AET表3 由AET表取出交點(diǎn)進(jìn)行配對（奇偶）獲得填充區(qū)間，依次對這些填充區(qū)間著色4 y=yi+1時(shí)，根據(jù)x=xi+1/k修改AET表所有結(jié)點(diǎn)中交點(diǎn)的x坐標(biāo)。同時(shí)如果相 應(yīng)的ET表不空，則將其中的結(jié)點(diǎn)插入AET表，形成新的AET表5 AET表不空，則轉(zhuǎn)（3），否則結(jié)束。2) 編程實(shí)現(xiàn)1 首先確定多邊形頂點(diǎn)和ET/AET表中結(jié)點(diǎn)的結(jié)構(gòu)2 編寫鏈表相關(guān)操作