版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、實(shí) 驗(yàn) 報(bào) 告 一、 實(shí)驗(yàn)?zāi)康?、 掌握有序邊表算法填充多邊形區(qū)域;2、 理解多邊形填充算法的意義;3、 增強(qiáng)C語(yǔ)言編程能力。二、 算法原理介紹根據(jù)多邊形內(nèi)部點(diǎn)的連續(xù)性知:一條掃描線與多邊形的交點(diǎn)中,入點(diǎn)和出點(diǎn)之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。所以,對(duì)所有的掃描線填充入點(diǎn)到出點(diǎn)之間所有的點(diǎn)就可填充多邊形。判斷掃描線上的點(diǎn)是否在多邊形之內(nèi),對(duì)于一條掃描線,多邊形的掃描轉(zhuǎn)換過(guò)程可以分為四個(gè)步驟:(1)求交:計(jì)算掃描線與多邊形各邊的交點(diǎn);(2)排序:把所有交點(diǎn)按x值遞增順序排序;(3)配對(duì):第一個(gè)與第二個(gè),第三個(gè)與第四個(gè)等等;每對(duì)交點(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í),僅對(duì)與它相交的多邊形的邊進(jìn)行求交運(yùn)算。把與當(dāng)前掃描線相交的邊稱為活性邊,并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中,稱此鏈表為活性邊表(AET)。 對(duì)每一條掃描線都建立一個(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)相交的掃描線號(hào)。每條掃描線的活性邊表中的活性邊節(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 對(duì)每一條掃描線i,初始化ET表的表頭指針ETi;2 將ymax = i的邊放入ETi中;3 使y =多邊形最低的掃描線號(hào);4 初始化活性邊表AET為空;5 循環(huán),直
4、到AET和ET為空。l 將新邊表ET中對(duì)應(yīng)y值的新邊節(jié)點(diǎn)插入到AET表。l 遍歷AET表,將兩兩配對(duì)的交點(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; /* 邊所交的最高掃描線號(hào) */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原來(lái)所指之結(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原來(lái)所指之結(jié)點(diǎn)*/q-next=edge; /*使q指向插入之結(jié)點(diǎn)*/int yNext(int k,int cnt,POINT *pts) /*對(duì)于多邊形中的某個(gè)頂點(diǎn)序號(hào)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) /*掃描線掃過(guò)平行頂點(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)而分開(kāi),所以把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)前掃描線對(duì)應(yīng)的y桶*/while(p) /*y桶不空*/q=p-next; /*找到最后一個(gè)邊結(jié)點(diǎn),插入*/ InsertEdge(active,p); /*把更新后的邊表重新插入邊表中保存*/ p=q; /*填充一對(duì)交點(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); /*畫(huà)出圖形內(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) /*掃描線超過(guò)邊的最大y值,此條邊的節(jié)點(diǎn)應(yīng)該刪掉*/ p=p-next; deleteAfter(q);else /*掃描線未超過(guò)邊的最大y值,相應(yīng)的x值增加*/ p-x=p-x+p-dx; q=p;p=p-next;/*對(duì)活性邊表結(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); /*重排活化邊表*/*開(kāi)始菜單*/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é)與體會(huì)實(shí)驗(yàn)步驟1) 分析多邊形區(qū)域掃描線填充算法的原理,確定算法流程1 初始化:構(gòu)造邊表,AET表置空2 將第一個(gè)不空的ET表中的邊插入AET表3 由AET表取出交點(diǎn)進(jìn)行配對(duì)(奇偶)獲得填充區(qū)間,依次對(duì)這些填充區(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 編寫(xiě)鏈表相關(guān)操作
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 電梯用齒輪傳動(dòng)裝置相關(guān)項(xiàng)目建議書(shū)
- 拋光鐵丹相關(guān)項(xiàng)目實(shí)施方案
- 手機(jī)軟件設(shè)計(jì)與用戶體驗(yàn)優(yōu)化教程
- 浴鹽項(xiàng)目可行性實(shí)施報(bào)告
- 五年級(jí)英語(yǔ)下冊(cè) Unit 2單元話題拓展閱讀“出行方式”(含答案)譯林版三起
- Unit6語(yǔ)法(復(fù)習(xí)講義)-2023-2024學(xué)年六年級(jí)英語(yǔ)上冊(cè)單元速記·巧練(人教PEP版)
- Unit 5 語(yǔ)音(復(fù)習(xí)講義)-2023-2024學(xué)年六年級(jí)英語(yǔ)上冊(cè)單元速記·巧練(譯林版三起)
- 交互綜合英語(yǔ)(23-24-1)學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年
- M6U1課文知識(shí)復(fù)習(xí)+鞏固練習(xí)-2023-2024學(xué)年六年級(jí)英語(yǔ)上冊(cè)單元速記·巧練(外研版三起)
- 共享經(jīng)濟(jì)平臺(tái)車輛調(diào)度優(yōu)化預(yù)案
- 我的公共關(guān)系學(xué)課件
- 供需雙方框架性合作協(xié)議書(shū)
- 孩子歸女方撫養(yǎng)承諾書(shū)
- 路基施工質(zhì)量控制要點(diǎn)
- 會(huì)計(jì)學(xué)原理方法與中國(guó)情境案例潘立新課后參考答案
- 籃球賽活動(dòng)經(jīng)費(fèi)申請(qǐng)報(bào)告
- 鼻飼患者護(hù)理精選PPT
- 通用車輛抵押借款合同書(shū)范本
- 觀測(cè)墩澆筑及觀測(cè)交通施工方案
- 桂工10級(jí)資勘優(yōu)秀灌陽(yáng)實(shí)習(xí)報(bào)告
- 【藥劑】11第十一章 新藥的臨床藥物代謝動(dòng)力學(xué)評(píng)價(jià)-2015
評(píng)論
0/150
提交評(píng)論