第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充-資料下載頁
2025-08-01 13:31本頁面
【正文】 olor) { PutPixel(x,y,newColor)。 FloodFill4(x,y+1,oldColor,newColor)。 FloodFill4(x,y1,oldColor,newColor)。 FloodFill4(x1,y,oldColor,newColor)。 FloodFill4(x+1,y,oldColor,newColor)。 } }/*end of FloodFill4() */ 種子填充算法 – 邊界表示的 4連通區(qū)域 void BoundaryFill4(int x,int y,int boundaryColor,int newColor) { int color。 color = GetPixel(x,y)。 if((color != boundaryColor) amp。amp。 (color != newColor)) { PutPixel(x,y,newColor)。 BoundaryFill4(x,y+1,oldColor,newColor)。 BoundaryFill4(x,y1,oldColor,newColor)。 BoundaryFill4(x1,y,oldColor,newColor)。 BoundaryFill4(x+1,y,oldColor,newColor)。 } }/*end of BoundaryFill4() */ ? 該算法也可以填充有孔區(qū)域。 ? 缺點 ： (1) 有些象素會入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。 (2) 遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn) /出棧，費時費內(nèi)存。 ? 改進(jìn)算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線填充算法 種子填充算法 掃描線算法 ? 掃描線算法 – 目標(biāo)：減少遞歸層次 – 適用于邊界表示的 4連通區(qū)域 算法思想 ：在任意不間斷區(qū)間中只取一個種子像素 （ 不間斷區(qū)間指在一條掃描線上一組相鄰元素 ） ， 填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段 ， 并依次把它們保存起來 ， 反復(fù)進(jìn)行這個過程 ， 直到所保存的個區(qū)段都填充完畢 。 掃描線填充算法 (1)初始化：堆棧置空。將種子點（ x， y）入棧。 (2)出棧：若棧空則結(jié)束。否則取棧頂元素（ x， y），以 y作為當(dāng)前掃描線。 (3)填充并確定種子點所在區(qū)段：從種子點（ x， y）出發(fā)，沿當(dāng)前掃描線向左、右兩個方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點坐標(biāo)為 xl和 xr。 (4)并確定新的種子點：在區(qū)間 [xl， xr]中檢查與當(dāng)前掃描線 y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（ 2）步。 上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。 掃描線算法分析（舉例分析） ? 該算法也可以填充有孔區(qū)域。 像素中的序號標(biāo)指它所在區(qū)段位于堆棧中的位置 掃描線算法分析（舉例分析） 掃描線算法分析（舉例分析） 掃描線算法分析（舉例分析） 多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較 ?聯(lián)系：都是光柵圖形面著色 ， 用于真實感圖形顯示 。 可相互轉(zhuǎn)換 。 ?多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充問題：當(dāng)給定多邊形內(nèi)一點為種子點，并用 Bresenham或DDA算法將多邊形的邊界表示成八連通區(qū)域后，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。 ?區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換；若已知給定多邊形的頂點，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。 多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較 ? 不同點： ；前者是 頂點表示轉(zhuǎn)換成點陣表示，后者只改變區(qū)域內(nèi)填充顏色，沒有改變表示方法。 ? 前者只要求掃描線與多邊形邊界交點個數(shù)為偶數(shù)。后者：區(qū)域封閉，防止遞歸填充跨界。 ? 前者：從邊界頂點信息出發(fā)。 ? 后者：區(qū)域內(nèi)種子點。
物理相關(guān)推薦
鄂ICP備17016276號-1