計(jì)算機(jī)圖形學(xué)第3節(jié)區(qū)域填充

1、第三節(jié) 區(qū)域填充種子填充算法多邊形掃描轉(zhuǎn)換算法1.區(qū)域是指光柵網(wǎng)格上的一組象素。 區(qū)域填充是把某確定的象素值送入到區(qū)域內(nèi) 部的所有象素中。2.區(qū)域定義方法分為兩大類。 區(qū)域由多邊形圍成，區(qū)域由多邊形的頂點(diǎn)序列來定義; 優(yōu)點(diǎn)：占用內(nèi)存少，缺點(diǎn)：得區(qū)分內(nèi)外側(cè) 是通過象素的值來定義區(qū)域的內(nèi)部 優(yōu)點(diǎn)：形狀可任意復(fù)雜，可直接著色 缺點(diǎn)：幾何意義不直觀一、種子填充算法 3.用象素值定義區(qū)域 （1）內(nèi)定義區(qū)域(oldvalue)指出區(qū)域內(nèi)部所具有 的象素值,（內(nèi)點(diǎn)表示）（2）邊界定義區(qū)域(boundaryvalue)，指出區(qū)域邊界所具有的象素值。此時(shí)區(qū)域邊界上所有象素具有某個(gè)邊界boundaryvalue。

2、區(qū)域的邊界應(yīng)該是封閉的，指明區(qū)域的內(nèi)部和外部。以象素為基礎(chǔ)的區(qū)域填充主要是依據(jù)區(qū)域的連通性進(jìn)行。 4.區(qū)域的連通性 （1）四連通:從區(qū)域中的一個(gè)象素出發(fā)，經(jīng)連續(xù)地向上下左右四個(gè)相鄰象素的移動(dòng)，就可以到達(dá)區(qū)域內(nèi)的任意另一個(gè)象素. （2）八連通:如果除了要經(jīng)上下左右的移動(dòng)，還要經(jīng)左上、右上、左下和右下的移動(dòng)，才能由一個(gè)象素走到區(qū)域中另外任意一個(gè)象素.四連通區(qū)域必定是八連通區(qū)域，反之不一定四連通區(qū)域八連通區(qū)域 4.區(qū)域的連通性 （1）四連通 （2）八連通5.種子填充算法 利用區(qū)域的連通性進(jìn)行區(qū)域填充，除了需要區(qū)域應(yīng)該明確定義外，還需要事先給定一個(gè)區(qū)域內(nèi)部象素，這個(gè)象素稱為種子。 做區(qū)域填充時(shí)，要對光

3、柵網(wǎng)格進(jìn)行遍歷，找出由種子出發(fā)能達(dá)到而又不穿過邊界的所有象素。 這種利用連通性的填充，其主要優(yōu)點(diǎn)是不受區(qū)域不規(guī)則性的影響，主要缺點(diǎn)是需要事先知道一個(gè)內(nèi)部象素。 （1）四連通內(nèi)定義區(qū)域填充算法：void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue)/*(x,y)為種子 oldvalue是原值 newvalue是新值，應(yīng)不等于原值。*/ /是否在區(qū)域內(nèi)并且尚未被訪問過if (GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue); /賦值為新值Floodfill(x,y-1,oldva

4、lue,newvalue);/向上擴(kuò)散Floodfill(x,y+1,oldvalue,newvalue); /向下擴(kuò)散Floodfill(x-1,y,oldvalue,newvalue); /向左擴(kuò)散Floodfill(x+1,y,oldvalue,newvalue); /向右擴(kuò)散 優(yōu)點(diǎn)：算法簡單 缺點(diǎn)：重復(fù)多（2）四連通邊界定義區(qū)域填充算法：void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)/*(x,y) 為種子位置 boundaryvalue是邊界象素值newvalue是區(qū)域內(nèi)象素新值，未填充前區(qū)

5、域內(nèi)不應(yīng)有值為newvalue的象素。*/if( GetPixel(x,y)!=boundaryvalue & GetPixel(x,y)!=newvalue) /未達(dá)邊界且未訪問過 SetPixel(x,y,newvalue);/賦以新值/向四個(gè)方向擴(kuò)散。Boundaryfill(x,y-1,boundaryvalue,newvalue); Boundaryfill(x,y+1,boundaryvalue,newvalue);Boundaryfill(x-1,y,boundaryvalue,newvalue);Boundaryfill(x+1,y,boundaryvalue,newvalue

6、);算法簡單，多層遞歸，存儲(chǔ)空間有限堆棧溢出void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue)stack s;Point p;if(GetPixel(x,y) = oldvalue)s.push(Point(x,y);while(!s.empty()p=s.pop();SetPixel(p.x ,p.y ,newvalue);if(GetPixel(p.x,p.y-1) = oldvalue)s.push(Point(p.x,p.y-1);if(GetPixel(p.x,p.y+1) = oldvalue)s.push

7、(Point(p.x,p.y+1);if(GetPixel(p.x-1,p.y) = oldvalue)s.push(Point(p.x-1,p.y);if(GetPixel(p.x+1,p.y) = oldvalue)s.push(Point(p.x+1,p.y);void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)stack s;Point p;if(GetPixel(x,y) != boundaryvalue)&(GetPixel(x,y) !=newvalue)s.push(Point(x,y);

8、while(!s.empty()p=s.pop();SetPixel(p.x ,p.y ,newvalue);if (GetPixel(p.x,p.y-1) != boundaryvalue)&(GetPixel(p.x,p.y-1) !=newvalue)s.push(Point(p.x,p.y-1);if (GetPixel(p.x,p.y+1) != boundaryvalue)&(GetPixel(p.x,p.y+1) !=newvalue)s.push(Point(p.x,p.y+1);if (GetPixel(p.x-1,p.y) != boundaryvalue)&(GetPix

9、el(p.x-1,p.y) !=newvalue)s.push(Point(p.x-1,p.y);if (GetPixel(p.x+1,p.y) != boundaryvalue)&(GetPixel(p.x+1,p.y) !=newvalue)s.push(Point(p.x+1,p.y); （3）掃描線種子填充算法(適用于邊界定義的四連通區(qū)域） 象素段：將區(qū)域內(nèi)由邊界點(diǎn)限定的同一行內(nèi)相連 接的不具有新值newvalue的一組象素稱為一個(gè)象素段，象素段用它最右邊的象素來標(biāo)識(shí)。 12345算法的步驟如下：1.初始化將堆棧置為空，將給定的種子點(diǎn)(x,y)壓入堆棧2.出棧如果堆棧為空，算法結(jié)束，否

10、則取棧頂元素(x,y) 作為種子點(diǎn)3.區(qū)段填充從種子點(diǎn)(x,y)開始沿當(dāng)前掃描線向左右兩個(gè)方 向逐個(gè)象素進(jìn)行填充，直到遇到邊界點(diǎn)為止4.定范圍用xl和xr分別表示在步驟3中填充的區(qū)段的左右兩 個(gè)端點(diǎn)的橫坐標(biāo)5.進(jìn)棧對當(dāng)前掃描線上下相鄰的兩條掃描線從右向左的確定 位于xl,xr區(qū)域內(nèi)的象素段。如果區(qū)域內(nèi)的象素已 經(jīng)填充或?yàn)檫吔鐒t轉(zhuǎn)到步驟2，否則取象素段的右端 點(diǎn)作為種子點(diǎn)，壓入堆棧，再轉(zhuǎn)到步驟2。下面我們用偽C語言寫出掃描線填充算法。 void ScanlineSeedfill(intx,inty,COLORREF boundaryvalue,COLORREF newvalue)int x0,x

11、l,xr,y0,xid;int flag;Stack s； Point p; s.push(Point(x,y);/種子象素入棧 while(!s.isempty() p=s.pop(); /棧頂象素出棧 x=p.x;y=p.y; SetPixel(x ,y ,newvalue); x0= x+1;while(GetPixel(x0,y)!=boundaryvalue)/填充右方象素SetPixel(x0 ,y ,newvalue); x0+;xr=x0-1;/最右邊象素x0= x-1;while(GetPixel(x0,y)!=boundaryvalue)/填充左方象素SetPixel(x0

12、 ,y ,newvalue);x0-;xl=x0+1;/最左邊象素/檢查上一條掃描線和下一條掃描線，/若存在非邊界且未填充的象素，/則選取代表各連續(xù)區(qū)間的種子象素入棧。y0=y;for(int i=-1;i=xl) flag=0;/是否找到象素段的標(biāo)識(shí)，是為1，否為0while(GetPixel(x0,y)!=boundaryvalue)& (GetPixel(x0,y)!=newvalue) & (x0 xl) if(flag=0) flag=1;/標(biāo)志找到新的象素段xid=x0; x0-;/繼續(xù)向左找其它的象素段標(biāo)志 1/將最右側(cè)可填充象素壓入棧中if(flag=1) s.push(Poi

13、nt(xid,y);flag=0;/檢查當(dāng)前填充行是否被中斷，若被中斷，尋找左方第一個(gè)可填 充象素/判斷當(dāng)前點(diǎn)是否為邊界點(diǎn)/判斷當(dāng)前點(diǎn)是否為已填充點(diǎn)while(GetPixel(x0,y)=boundaryvalue|(GetPixel(x0,y)=newvalue)/若當(dāng)前點(diǎn)為邊界點(diǎn)或已填充點(diǎn)，根據(jù)前面的判斷，當(dāng)前點(diǎn)必然未超出左邊界，則當(dāng)前點(diǎn)向左移動(dòng)x0-;/while(x0=xl)/for(int i=1;i=-1;i-=2)/while(!s.isempty()112123412345(2)(1)123451234(4)(3)1234123(6)(5)SeedScanLineShowin

14、gEdgeFillShowing二、多邊形的掃描轉(zhuǎn)換算法“奇偶”性質(zhì)：即一條直線與任意封閉的曲線相交時(shí)，總是從第一個(gè)交點(diǎn)進(jìn)入內(nèi)部，再從第二個(gè)交點(diǎn)退出，以下交替的進(jìn)入退出，即奇數(shù)次進(jìn)入，偶數(shù)次退出。當(dāng)然可能有一些“相切”的點(diǎn)應(yīng)特殊處理。二、多邊形的掃描轉(zhuǎn)換算法掃描轉(zhuǎn)換算法步驟： step1找出掃描線與多邊形邊界線的所有交點(diǎn)；step2按x坐標(biāo)增加順序?qū)稽c(diǎn)排序；step3在交點(diǎn)對之間進(jìn)行填充。（偶數(shù)） “相切”點(diǎn)的特殊處理： 正確的解決辦法是，當(dāng)頂點(diǎn)表現(xiàn)為是局部極大或局部極小時(shí)，就看做是二個(gè)，否則看做一個(gè)。如果一個(gè)頂點(diǎn)的前面和后面各有一些相鄰頂點(diǎn)的y坐標(biāo)，都小于該頂點(diǎn)的y坐標(biāo)，則這個(gè)頂點(diǎn)是局部極

15、大。局部極小可類似地確定。實(shí)際處理這個(gè)問題可以有一個(gè)簡便辦法，那就是對應(yīng)該看做是一個(gè)的頂點(diǎn)，將其上面的邊縮短兩條相鄰掃描線對應(yīng)的一個(gè)單位。 奇異頂點(diǎn)： 局部極大或局部極小點(diǎn)，交點(diǎn)看做是二個(gè) 非局部極值點(diǎn)，交點(diǎn)看做一個(gè) 對非極值點(diǎn)的簡便處理局部極大或局部極小點(diǎn)，交點(diǎn)看做是二個(gè)22221局部極大或局部極小點(diǎn)，交點(diǎn)看做是二個(gè)非局部極值點(diǎn)，交點(diǎn)看做一個(gè)22221局部極大或局部極小點(diǎn)，交點(diǎn)看做是二個(gè)非局部極值點(diǎn)，交點(diǎn)看做一個(gè)非局部極值點(diǎn)將這些相鄰邊分割開來step1如何計(jì)算掃描線與多邊形邊界線的所有交點(diǎn)？若掃描線yi與多邊形邊界線交點(diǎn)x的坐標(biāo)是xi，則對下一條掃描線yi+l，它與那條邊界線的交點(diǎn)的x坐標(biāo)

16、xi+1，可如下求出：ABC二 多邊形的掃描轉(zhuǎn)換算法活躍(活性)邊：與當(dāng)前掃描線相交的邊活躍(活性)邊表AET：存貯當(dāng)前掃描線相交的各邊的表。 ymaxx 1/mnextymax:當(dāng)前這條邊的上端點(diǎn)的y坐標(biāo)x: 當(dāng)前邊與掃描線交點(diǎn)的x坐標(biāo)1/m:當(dāng)前邊的斜率的倒數(shù)next：指向下一條邊的指針每次離開一條掃描線進(jìn)入下一條之前，將表中有但與下一條掃描線不相交的邊清除出表，將與下一條掃描線相交而表中沒有的邊加入表中。新邊表ET：記錄多邊形的所有邊，按y坐標(biāo)遞增排序一條邊的記錄信息：ymaxxmin 1/mnextymax: 邊的另端點(diǎn)的較大的y坐標(biāo)xmin: 與較小的y坐標(biāo)對應(yīng)的邊的端點(diǎn)的x坐標(biāo)1/

17、m: 斜率的倒數(shù)next：指向下一條邊的指針Polygonfill(EdgeTable ET,COLORREF color)1.y=置y為邊表ET中各登記項(xiàng)對應(yīng)的y 坐標(biāo)中最小的值;2.活躍邊表AET初始化為空表;3.若AET非空或ET非空，則做下列步驟，否則算法結(jié)束 3.1.將ET中登記項(xiàng)y對應(yīng)的各條邊合并到表AET中,將AET中各邊按x坐標(biāo)遞增排序；3.2.在掃描線y上，按照AET表提供的x坐標(biāo)對, 用 color實(shí)施填充；3.3.將AET表中有y=ymax的各項(xiàng)清除出表；3.4.對AET中留下的各項(xiàng)，分別將x換為x+1/m，求出AET中各邊與下一條掃描線交點(diǎn)的x坐標(biāo)；3.5.y=y1，返

18、回步驟3處理下一條掃描線。ET：AET指針初始化137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：掃描線137-5/2e1576/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：掃描線2341/2-5/2e1581/26/4e6掃描線137-5/2e1576/4e6137-5/2e1576/4e60234920e25611130e5797-5/2

19、e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：掃描線332-5/2e15106/4e6掃描線2341/2-5/2e1581/26/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：掃描線4920e25111/26/4e6掃描線332-5/2e15106/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4E

20、T：掃描線5920e25136/4e6掃描線4920e25111/26/4e6137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/me1e6e2e5e3e4ET：掃描線6920e211130e5掃描線5920e25136/4e6e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：掃描線7920e297-5/2e31176/4e411130e5掃描線6920e211130e5e1e6e2e5

21、e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：掃描線8920e2941/2-5/2e31181/26/4e411130e5掃描線7920e297-5/2e31176/4e411130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：掃描線9920e292-5/2e311106/4e411130e5掃描線8920e2941/2-5/2e31181/26/4e411

22、130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：掃描線1011111/26/4e411130e5掃描線9920e292-5/2e311106/4e411130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：掃描線1111136/4e411130e5掃描線1011111/26/4e411130e5e1e6e2e5e3e4137-5/2e1

23、576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mET：掃描線12掃描線1111136/4e411130e5e1e6e2e5e3e4137-5/2e1576/4e60234920e25611130e5797-5/2e31176/4e4891011 ymax xmin 1/mAET指針初始化掃描線137-5/2掃描線1011111/26/4e1576/4e6掃描線2341/2-5/2e1581/26/4e6掃描線332-5/2e15106/4e6e4掃描線4920e25111/26/4e6掃描線5920e25136/4e65掃描線6920e211130e5掃描線7920e297-5/2e31176/4e411130e5掃描線8920e2941/2-5/2e31181/26/4e411130e5掃描線9920e292-5/2e311106/4e411130e511130e5掃描線111