第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充(文件)
【正文】 邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形 P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。 存放的信息： x：掃描線與該邊的初始交點(diǎn) dx： x的增量 ymax：該邊的最大 y值 即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 邊的分類表 ET是按邊的下端點(diǎn)的 y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組。 邊表 7 2 4 ^ P5 P1 7 8 1 ^ P2 P1 6 2 0 ^ P4 P5 3 6 2 P3 P4 5 6 ^ P3 P2 ^ ^ ^ (Ymax, x,Δx, next) 活動(dòng)邊表的例子 3 4 2 P3 P4 5 ^ P3 P2 掃描線 2 AET指針 6 2 0 P4 P5 5 7 ^ P3 P2 掃描線 3 AET指針 (Ymax, x,Δx, next) 3 6 2 P3 P4 5 6 ^ P3 P2 掃描線 2 AET指針 活動(dòng)邊表的例子 6 2 0 P4 P5 5 ^ P3 P2 掃描線 4 AET指針 6 2 0 P4 P5 7 8 1 ^ P2 P1 掃描線 5 AET指針 7 2 4 P5 P1 7 8 1 ^ P2 P1 掃描線 6 AET指針 算法實(shí)現(xiàn)步驟 這樣，當(dāng)建立了邊的分類表 ET后，掃描線算法可按下列步驟進(jìn)行： （ 1）取掃描線縱坐標(biāo) y的初始值為 ET中非空元素的最小序號(hào)。 2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表 AEL非空，則將AEL中的邊兩兩依次配對(duì)，即 1， 2邊為一對(duì)， 3， 4邊為一對(duì)，依次類推。 5）將當(dāng)前的掃描線的縱坐標(biāo)值 y累加 1，即 y:=y+1。 。 Inside 的初始值為假，每當(dāng)當(dāng)前訪問(wèn)象素為被打上標(biāo)志的點(diǎn)，就把 inside取反。 for (每條與多邊形 polydef相交的掃描線 y ) for (掃描線上每個(gè)象素 x ) { if(象素 x 被打上邊標(biāo)志 ) inside = ! (inside)。 邊界標(biāo)志算法 ? 思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？ 第四章多邊形的掃描轉(zhuǎn)換 與區(qū)域填充 ? 區(qū)域 指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。 步驟如下： 種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作： （ 1）棧頂象素出棧； （ 2）將出棧象素置成多邊形色； （ 3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。 FloodFill4(x,y1,oldColor,newColor)。 color = GetPixel(x,y)。 BoundaryFill4(x,y+1,oldColor,newColor)。 } }/*end of BoundaryFill4() */ ? 該算法也可以填充有孔區(qū)域。 解決方法是用掃描線填充算法 種子填充算法 掃描線算法 ? 掃描線算法 – 目標(biāo)：減少遞歸層次 – 適用于邊界表示的 4連通區(qū)域 算法思想 ：在任意不間斷區(qū)間中只取一個(gè)種子像素 （ 不間斷區(qū)間指在一條掃描線上一組相鄰元素 ） ， 填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段 ， 并依次把它們保存起來(lái) ， 反復(fù)進(jìn)行這個(gè)過(guò)程 ， 直到所保存的個(gè)區(qū)段都填充完畢 。否則取棧頂元素（ x， y），以 y作為當(dāng)前掃描線。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（ 2）步。 可相互轉(zhuǎn)
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1