第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充-免費(fèi)閱讀
【正文】 后者：區(qū)域封閉，防止遞歸填充跨界。 上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。 掃描線填充算法 (1)初始化：堆棧置空。 BoundaryFill4(x,y1,oldColor,newColor)。 FloodFill4(x1,y,oldColor,newColor)。 ? 區(qū)域填充 指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程。對未打標(biāo)志的點(diǎn)，inside不變。 掃描線算法 ? 特點(diǎn)：算法效率較高。 （ 2）將邊的活化鏈表 AEL設(shè)置為空。它由邊的分類表 ET（ Edge Table）和邊的活化鏈表 AEL（ Active Edge List） 兩部分組成。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 所有的邊和掃描線求交，效率很低。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？ 奇點(diǎn)的處理 奇點(diǎn)的處理 ? 若奇點(diǎn)做一個交點(diǎn)處理，則情況 A，交點(diǎn)個數(shù)不是偶數(shù)。 邊的連貫性 y=e y=d 邊的連貫性 于是，可利用 d的交點(diǎn)序列計算 e的交點(diǎn)序列，即先運(yùn)用遞推關(guān)系式 (1)求得與掃描線 y=e和 y=d都相交的所有多邊形上的交點(diǎn) xer,再求得與掃描線 y=d不相交但與掃描線 y=e相交的所有邊PqPq+1上的交點(diǎn) xeq。 若掃描線 y=e與多邊形 P的Pi1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為 xei。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計算量和提高速度的目的。 – 多邊形的掃描轉(zhuǎn)換： 把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個象素，并給幀緩沖器內(nèi)的各個對應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。 ● 解決方法： 檢查兩相鄰邊在掃描線的哪一側(cè)。 3）兩類梯形在長方形區(qū)域 {yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個在多邊形 P內(nèi)，另一個在 P外。 設(shè) d為一整數(shù)，并且 d=e1,并且 yi0≥d≥y in。 ?當(dāng)掃描線與多邊形 P的交點(diǎn)是 P的頂點(diǎn)時，則稱該交點(diǎn)為奇點(diǎn)。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 算法基本思想：首先取 d=yin。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 ? 如何計算下一條掃描線與邊的交點(diǎn)。有多少條掃描線，就設(shè)多少類。 3）將邊的活化鏈表 AEL中滿足 y=ymax的邊刪去。 取一個布爾變量 inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則 inside為真。 else drawpixel (x, y, background)。 依此類推 ， 最后像素被選中并填充的次序如圖中箭頭所示 s1 2 3 4 9 8 7 6 5 11 12 13 14 10 (2 10 8 13) (3 7 13 10 8 13) (4 6 14 7 13 10 8 13) (5 6 14 7 13 10 8 13) …… 種子填充算法 遞歸算法可實(shí)現(xiàn)如下 void FloodFill4(int x,int y,int oldColor,int newColor) { if(GetPixel(x,y) == oldColor) { PutPixel(x,y,newColor)。amp。 (2) 遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn) /出棧，費(fèi)時費(fèi)內(nèi)存。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為 xl和 xr。 ?區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換；若已知給定多邊形的頂點(diǎn)，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。 。 可相互轉(zhuǎn)換 。否則取棧頂元素（ x， y），以 y作為當(dāng)前掃描線。 } }/*end of BoundaryFill4() */ ? 該算法也可以填充有孔區(qū)域。 color = GetPixel(x,y)。 步驟如下： 種子
物理相關(guān)推薦
鄂ICP備17016276號-1