[理學(xué)]第四章二維圖形的生成__區(qū)域填充(完整版)
【正文】 點(diǎn)的狀態(tài) ， 若點(diǎn)在 多邊形內(nèi) ， 則 inside為真 。 3） 將邊的活化鏈表 AEL中滿足 y=ymax的邊刪去 。 它記錄了多邊形邊沿掃描線的交點(diǎn)序列 。它由邊的分類表 ET（ Edge Table）和邊的活化鏈表 AEL（ Active Edge List） 兩部分組成。 ?若奇點(diǎn)做兩個(gè)交點(diǎn)處理，則情況 B，交點(diǎn)個(gè)數(shù)不是偶數(shù)。 然后把這兩部分按遞增的順序排列 ， 即可得 e的交點(diǎn)序列 。 現(xiàn)設(shè) xei1,xei2,xei3,… ,xeil 是該掃描線與 P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱此序列為交點(diǎn)序列。 // 多邊形頂點(diǎn)個(gè)數(shù) Point vertexces[MAX] //多邊形頂點(diǎn)數(shù)組 } Polygon // 多邊形結(jié)構(gòu) 逐點(diǎn)判斷法 2022/2/16 西安工程大學(xué)計(jì)算機(jī)圖形學(xué) 9 掃描線算法是多邊形 填充 的常用算法。 ? 共享邊界如何處理？ ?原則：左閉右開，下閉上開 屬于誰？ 2022/2/16 西安工程大學(xué)計(jì)算機(jī)圖形學(xué) 8 void FillPolygonPbyP(Polygon *P,int polygonColor) { int x,y。 如果規(guī)定：每條有向邊的左側(cè)為其內(nèi)部實(shí)面積區(qū)域 。 它由有序頂點(diǎn)的點(diǎn)集 Pi（ i=0～ n1） 及有向邊的線集 Ei（ i=0～ n1） 定義 ， n為多邊形的頂點(diǎn)數(shù)或邊數(shù) ，且 Ei＝ PiPi+1， i=0～ n1 。 多邊形上任意兩頂點(diǎn)間的連線有不在多邊形內(nèi)部的部分 ， 凹點(diǎn)對(duì)應(yīng)的內(nèi)角大于 180176。即從多邊形的頂點(diǎn)信息出發(fā)，求出多邊形內(nèi)部的各個(gè)像素點(diǎn)信息。x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor)。 3） 兩類梯形在長(zhǎng)方形區(qū)域 {yik , yik+1}內(nèi)相間的排列 ， 即相鄰的兩梯形必有一個(gè)在多邊形 P內(nèi) ， 另一個(gè)在 P外 。 設(shè)位于掃描線 y=d上的 交點(diǎn)序列為 xdj1,xdj2,…, xdjk （遞增） 現(xiàn)在來討論掃描線 d， e交點(diǎn)序列之間的關(guān)系。 ?以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)： 每一條 掃描線 與 多邊形 P的邊界 的交點(diǎn)個(gè)數(shù)都是 偶數(shù) 。 容易求得掃描線 y=d上的交點(diǎn)序列為 xdj1,xdj2,… xdjn ， 這一序列由位于掃描線 y=d上的多邊形 P的頂點(diǎn)組成 。 有多少條掃描線 ， 就設(shè)多少類 。 遞增方向排序 。 2022/2/16 西安工程大學(xué)計(jì)算機(jī)圖形學(xué) 29 ?1. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換 ， 即對(duì)多邊形邊界所經(jīng)過的象素作一個(gè)邊界標(biāo)志 。 { 對(duì)多邊形 polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE。 現(xiàn)取 (x,y)為種子點(diǎn)對(duì)區(qū)域 G進(jìn)行填充：即先置像素 (x,y)的顏色為 new_color， 然后逐步將整個(gè)區(qū)域 G都置為同樣的顏色 。 } }/*end of FloodFill4() */ 、種子填充算法 2022/2/16 西安工程大學(xué)計(jì)算機(jī)圖形學(xué) 42 邊界表示的 4連通區(qū)域 void BoundaryFill4(int x,int y,int boundaryColor,int newColor) { int color。 BoundaryFill4(x+1,y,oldColor,newColor)。否則取棧頂元素（ x， y），以 y作為當(dāng)前掃描線。 可相互轉(zhuǎn)換 。 多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較 。 ? 區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換；若已知給定多邊形的頂點(diǎn)，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為 xl和 xr。 ?缺點(diǎn) ： (1) 有些象素會(huì)入棧多次 ， 降低算法效率； (2) 遞歸執(zhí)行 ， 算法簡(jiǎn)單 ， 但效率不高 ， 區(qū)域內(nèi)每一象素都引起一次遞歸 ， 進(jìn) /出棧 ， 費(fèi)時(shí)費(fèi)內(nèi)存 。 if((color != boundaryColor) amp。 、種子填充算法 2022/2/16 西安工程大學(xué)計(jì)算機(jī)圖形學(xué) 40 ? 例 ： 多邊形由 P0P1P2P3P4 構(gòu)成 ， P0(1,5) P1(5,5) P2(7,3) P3(7,1) P4(1,1) ? 設(shè)種子點(diǎn)為 （ 3， 3） ， 搜索的方向是上 、 下 、 左 、 右 。 if(inside！ = FALSE) dra
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1