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