第4章(2)多邊形填充算法

第4章基本光柵圖形生成算法4.3多邊形的填充4.3.1多邊形的表示方法多邊形的分類:凸多邊形凹多邊形含內環(huán)的多邊形表示方法：頂點表示和點陣表示4.3.1多邊形的表示方法頂點表示是用多邊形的頂點的序列來描述多邊形該表示幾何意義強、占內存少但它不能直觀地說明哪些像素在多邊形內點陣表示是用位于多邊形內的像素的集合來刻劃多邊形該方法雖然沒有多邊形的幾何信息是面著色所需要的圖像表示形式

多邊形填充就是把多邊形的頂點表示轉換為點陣表示即從多邊形的給定邊界出發(fā)，求出位于其內部的各個像素，并將幀緩沖器內的各個對應元素設置相應的灰度或顏色。

多邊形的填充方法：掃描線方法邊緣填充方法邊界標志方法柵欄填充方法4.3.2多邊形填充的掃描線算法算法特點：基本概念：充分利用了相鄰象素之間的連續(xù)性，避免對象素的逐點判斷和反復求交運算，減少了計算量，提高了算法速度，是效率較高的多邊形填充算法，處理對象為非自交多邊形。區(qū)域的連續(xù)性掃描線的連續(xù)性邊的連續(xù)性關于一般多邊形的填充過程,對于一條掃描線,可分為四步:求交排序交點配對區(qū)間填色奇點的處理區(qū)域的連續(xù)性

設多邊形P的頂點各頂點Pi的縱坐標yi的遞減數(shù)列p0p1p7p2p3p4p5p6p8p1,p7,p3,p6,p2,p5,p0,p4,p8(1)梯形的兩底邊分別在y=和y=兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。

它們具有下列性質(設為整數(shù))：(2)梯形可分為兩類：一類位于多邊形P的內部；另一類在多邊形P的外部。

(3)兩類梯形在長方形區(qū)域{，}內相間的排列。

位于y=和y=兩條掃描線之間的長方形區(qū)域被多邊形P的邊分割成若干梯形p0p1p7p2p3p4p5p6p8由區(qū)域的相關性知當知道一個區(qū)域內一點與多邊形的位置關系，即可確定該區(qū)域內所有點與多邊形之間的內外關系掃描線的連續(xù)性掃描線的連續(xù)性是區(qū)域連續(xù)性在掃描線上的體現(xiàn)012345678設e為一整數(shù)≥e≥若掃描線y=e與多邊形P的邊Pi-1Pi相交，則記其交點的橫坐標為y=e該掃描線與P的邊界各交點橫坐標的遞增序列此交點序列具有以下性質：

(1)l是偶數(shù)(2)掃描線被分成好多區(qū)段,一部分在多邊形內,一部分在多邊形外(3)兩類線段間隔排列由區(qū)域的連貫性和掃描線的連續(xù)性知:若已知某一點與多邊形的位置關系,就可知該點所在線段與多邊形的位置關系邊的連續(xù)性若d為一整數(shù)，d=e–1，且yi0≥y≥yin；設位于掃描線y=d上的交點序列為012345678y=ey=d則兩交點序列之間有以下關系:

1兩序列元素的個數(shù)相等2點()與()位于多邊形P的同一邊上，即以上性質稱為邊的連續(xù)性奇點定義

如果，則稱頂點Pi為極值點；否則稱Pi為非極值點。奇點的處理當掃描線與多邊形P的邊界的交點是P的頂點時，則稱該交點為奇點p0p1p7p2p3p4p5p6p8要把奇點作為幾個交點來處理呢??多邊形P的頂點可分為兩類：極值點和非極值點如果把每一奇點簡單地計為一個交點，則交點個數(shù)可能出現(xiàn)奇數(shù)。若將每一奇點都簡單地計為兩個交點，同樣會導致反常的結果

為了使交點個數(shù)保持為偶數(shù),規(guī)定當奇點是P的極值點時，該點按兩個交點計算；否則按一個交點計算。

預處理:若Pi是非極值點，則將兩邊中位于掃描線y=yi上方的那條邊在Pi點處截去一單位長掃描線算法的數(shù)據(jù)結構和實現(xiàn)步驟掃描線算法的數(shù)據(jù)結構多邊形P0P1P2P3P4P5P6P0數(shù)據(jù)結構邊的分類表ET和邊的活化鏈表AELET和AEL中的多邊形的邊由四個域組成：

ymax

邊的上端點的y坐標在ET中為邊的下端點的x坐標x在AEL中是邊與掃描線交點的x坐標Δx邊的斜率的倒數(shù)next指向下一條邊的指針[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]多邊形P0P1P2P3P4P5P6P0[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]對奇點采用了預處理的邊y筒分類表ET是按邊下端點的縱坐標y對邊進行分類的指針數(shù)組同一類中，各邊按x值遞增的順序排列成行下端點的縱坐標y等于i的邊歸入第i類，水平邊除外[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]多邊形P0P1P2P3P4P5P6P0對奇點采用了預處理的邊y筒邊的活化鏈表AEL由與當前掃描線相交的所有多邊形的邊組成

-5/357AELe7e54212AEL在y=2掃描線上的當前狀態(tài)它記錄了多邊形沿掃描線的交點序列,并根據(jù)遞推關系,不斷地更新交點序列它是一個動態(tài)列表，新邊插入，舊邊刪除[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)][P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]-5/35AELe7e54214AEL在y=3掃描線上的當前狀態(tài)-5/35AELe7e54216AEL在y=4掃描線上的當前狀態(tài)E4邊做了預處理(也可以不做預處理，但要清楚的知道此點要在AEL中計幾次)掃描線算法實現(xiàn)步驟步驟1:(AEL初始化)將邊的活化鏈表AEL設置為空。步驟2:(y初始化)取掃描線縱坐標y的初始值為ET中非空元素的最小序號步驟3：按從下到上的順序對縱坐標值為y的掃描線(當前掃描線)執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表AEL都變成空為止。(1)如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表AEL中，AEL中的各邊按照x值(當x的值相等時，按Δx值)遞增方向排序。(2)若相對于當前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對，即第1，2邊為一對，第3，4邊為一對，依此類推。每一對邊與當前掃描線的交點所構成的區(qū)段位于多邊形內，依次對這些區(qū)段上的點(象素)按多邊形屬性著色。(3)將邊的活化鏈表AEL中滿足y=ymax的邊刪去。

(4)將邊的活化鏈表AEL剩下的每一條邊的x域累加Δx，即x=x+Δx。

(5)將當前的掃描線的縱坐標值y累加，即y=y+1掃描線算法實現(xiàn)步驟偽代碼Polygonfill(polydef,color)Intcolor多邊形定義polydef{for(各條掃描線I){初始化新邊表表頭指針ET[I];把ymin=I的邊放進邊表ET[I];}y=最低掃描線號;初始化活化邊表AEL為空;for(各條掃描線I){把新邊表ET[I]中的邊結點用插入排序法插入AEL表,使之按x遞增順序排列;遍歷AET表,把配對交點之間的區(qū)間上的各像素(x,y)用待填顏色改寫遍歷AET表,把ymax=I的結點從AEL中刪除,并把ymax>I的結點的x遞增dx;若允許多邊形的邊自交,則用冒泡排序法對AEL表重新排序;}}掃描線算法特點數(shù)據(jù)結構較復雜但充分利用了掃描線、多邊形邊的連續(xù)性,避免了反復求交點的運算,是一種較快的填充方法對各種表的維持和排序開銷太大，適合軟件實現(xiàn)而不適合硬件實現(xiàn)優(yōu)點：對每個像素只訪問一次與設備無關缺點：數(shù)據(jù)結構復雜只適合軟件實現(xiàn)yx0123456789101112345678P6P4P1P5P2P3例習題1：用掃描線算法來掃描轉換一個多邊形邊的Y筒ET5432125-3353720811075-3/2852yx0123456789101112345678P6P4P1P5P2P3邊的活化鏈表Y=125-3353(5,1)(5,1)Y=222-3383(2,2)(8,2)yx0123456789101112345678P6P4P1P5P2P3yx0123456789101112345678P6P4P1P5P2P3例習題1：習題

設現(xiàn)在要用掃描線算法來掃描轉換一個多邊形，該多邊形的頂點分別為，如圖所示。先寫出邊y桶，然后試給出邊的活化鏈表AEL,完成掃描轉換4.3.3邊緣填充算法采用對圖像進行逐位求反的方法，免去對邊排序的工作量算法特點:預備知識：對圖像M作偶數(shù)次求反運算，其結果還是M;而對M作奇數(shù)次求反運算的結果是反的在光柵圖形中，如某區(qū)域已著上值為M的某種顏色，則上述求反運算得到的結果是：對區(qū)域作偶數(shù)次求反運算后，該區(qū)域的顏色不變；作奇數(shù)次求反運算后，該區(qū)域的顏色則變成值為的顏色。邊緣填充算法的實現(xiàn)對多邊形P的每一非水平邊（i=0,1,…,n）上的各像素做向右求反運算即可01234122334340邊緣填充算法分析優(yōu)點：最適合于有幀緩存的顯示器可按任意順序處理多邊形的邊僅訪問與該邊有交點的掃描線上右方的像素，算法簡單缺點：對復雜圖形，每一像素可能被訪問多次，輸入/輸出量大圖形輸出不能與掃描同步進行，只有全部畫完才能打印4.3.4柵欄填充算法此算法是為了減少邊緣算法訪問像素的次數(shù)而提出的柵欄:是一條與掃描線垂直的直線,柵欄的位置通常取過多邊形頂點,能把多邊形分為左右兩半柵欄填充的基本思想:對于每個掃描線與多邊形邊的交點,就將交點與柵欄之間的像素取補.若交點位于柵欄左邊,則將交點之右,柵欄之左的所有像素取補若交點位于柵欄右邊,則將交點之左,柵欄之右的所有像素取補柵欄填充的具體實現(xiàn):01234柵欄線12柵欄線34柵欄線23柵欄線4柵欄線0邊界標志法:先畫邊界后填色，使對幀緩沖器中的每個元素的賦值次數(shù)不超過2次?；舅枷胧牵合扔靡环N特殊的顏色在幀緩沖器中將多邊形的邊界(水平邊的部分邊界除外)勾畫出來。然后再采用和掃描線算法類似的方法將位于多邊形內的各個區(qū)段著上所需的顏色

圖邊界標志算法的運行過程4.3.5邊界標志算法邊界標志法具體實現(xiàn)圖邊界標志算法的運行過程步驟1：以值為boundary-color的特殊顏色勾畫多邊形P的邊界。設多邊形頂點為Pi=(xi,yi),0≤i≤n，xi,yi均為整數(shù)；置Pn+1=P0。每一條掃描線上著上這種特殊顏色的點的個數(shù)必定是偶數(shù)(包括零)。步驟2：設interior_point是一布爾變量。對每一條掃描線從左到右進行搜索，如果當前是像素位于多邊形P內，則interior_point=true，需要填上值為polygon_color的顏色；否則該像素在多邊形P外，需要填上值為background_color的顏色邊界標志算法實例XXXXXXXXXXXXP2(8,5)Y=2Y=3XXXXXXY=1P0(1,4)P1(1,10)P3(14,8)P4(14,2)P5(11,0)P6(6,0)XXXXХXXХY=4Y=5Y=6Y=7Y=8Y=9Y=10算法實現(xiàn)inti=0;doublex,y;doubledy,dx;intymin,ymax;for(i=0;i<=n;i++){dy=y[i+1]-y[i];if(dy!=0){dx=(x[i+1]-x[i])/dy;if(dy>0) x=x[i];elsex=x[i+1];if(y[i]>=y[i+1]){//獲得多邊形邊的端點 ymin=y[i+1]; ymax=y[i];}else{ ymin=y[i]; ymax=y[i+1];}for(y=ymin;y<=ymax-1;y++){ x=x+dx; COLORREFk=RGB(0,0,255),n; n=dc->GetPixel(x,y); if(k==n) dc->SetPixel(x+1,y,RGB(0,0,255));//標志邊界并處理奇點 elsedc->SetPixel(x,y,RGB(0,0,255));}}}//maxx、maxy、minx、miny是獲得的多邊形最小矩形包圍盒邊界值doublex1,y1;for(y1=miny-1;y1<=maxy-1;y1++){in_flag=0;//多邊形內部標志變量for(x1=minx-1;x1<=maxx-1;x1++){COLORREFl,m;

l=dc->GetPixel(x1,y1);m=RGB(0,0,255);//多邊形邊界顏色if(l==m) {if(in_flag==0) in_flag=1;else in_flag=0;}if(in_flag)dc->SetPixel(x1,y1,RGB(0,0,255));//在多邊形內部填充色藍色elsedc->SetPixel(x1,y1,RGB(255,255,255));//在多邊形外部填充色白色 }}算法特點分析：1本算法避免了對幀緩存的大量元素的賦值2但需逐條掃描線并對幀緩存中的元素進行搜索和比較3當算法生成的邊界不封閉時，在一條掃描線上必須有偶數(shù)個具有邊界顏色的點第4章基本光柵圖形生成算法4.4區(qū)域填充4.4.1區(qū)域的基本概念是指已經(jīng)表示成點陣形式的像素集合。區(qū)域區(qū)域的表示方式在光柵圖形中，有內點表示法和邊界表示法內點表示法：把位于給定區(qū)域內的所有像素一一列舉出來的方法稱為內點表示法。邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。是指先將區(qū)域內的一點(常稱種子點)賦予給定顏色，然后將這種顏色擴展到整個區(qū)域內的過程。區(qū)域填充一個封閉區(qū)域確定以后,填充要解決的問題是如何確定填充的像素以及如何高效地填充。4連通的區(qū)域:取區(qū)域內任意兩點，在該區(qū)域內若從其中一點出發(fā)通過上、下、左、右四種運動可到達另一點。四個方向的運動8連通區(qū)域:

取區(qū)域內任意兩點，若從其中任一點出發(fā)，在該區(qū)域內通過沿水平方向、垂直方向和對角線方向的八種運動可到達另一點。8個方向的運動區(qū)域的連通性4連通區(qū)域可理解為8連通區(qū)域，但他們的邊界不盡相同。四連通區(qū)域的邊界是八連通的八連通區(qū)域的邊界是四連通的4.4.2簡單的種子填充算法

基本思想：1給定區(qū)域G一種子點（x,y）2判斷該點是否是區(qū)域內的一點如果是，則將該點填充為新的顏色3然后將該點周圍的四個點（四連通）或八個點（八連通）作為新的種子點進行同樣的處理4通過這種擴散完成對整個區(qū)域的填充

簡單的種子填充算法

（4連通）種子像素入棧當棧非空時，重復以下步驟：棧頂像素出棧將出棧象素置成填充色

按左、上、右、下順序檢查與出棧象素相鄰的四象素，若其中某象素不在邊界上且未被置成填充色，則將其入棧算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799按右、上、左、下的順序進棧區(qū)域連通方式對填充結果的影響4連通區(qū)域邊界填充算法的填充結果8連通區(qū)域邊界填充算法的填充結果算法分析：1有些象素會入棧多次，降低算法效率；棧結構占空間。2遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內每一象素都引起一次遞歸，進/出棧，費時費內存。種子算法充分利用了遞歸調用的機理，在前一種子點確定并變?yōu)樾骂伾?，按照自身調用的八(四）向順序依次查找新的種子點，找到即變?yōu)樾骂伾?，繼續(xù)下一種子的查找。未查的方向被壓棧保存，等退棧時繼續(xù)查找，最終完成蔓延至整個區(qū)域所有點都變?yōu)樾骂伾?/p>

改進算法，減少遞歸次數(shù)，提高效率。方法之一使用掃描線填充算法；4.4.3掃描線種子填充算法從給定的種子點開始，填充當前掃描線上種子點所在的區(qū)間基本思想：然后確定與這一區(qū)間相鄰的上下兩條掃描線上需要填充的區(qū)間從這些區(qū)間上各取一個種子點并把他們保存起來，作為下次填充的種子點反復這個過程，直到所保存的各區(qū)間都填充完畢算法步驟：步驟1：將算法設置的堆棧置為空。將給定的種子點（x,y）壓入堆棧步驟2：如果堆棧為空，算法結束；否則取棧頂元素（x,y）作為種子點步驟3：從種子點（x,y）開始，沿縱坐標為y的當前掃描線向左右兩個方向逐個像素用新的顏色值進行填充，直到邊界為止。設區(qū)間兩邊界的橫坐標分別為xleft和xright。步驟4：在與當前掃描線相鄰的上下兩條掃描線上，以區(qū)間[xleft,xright]為搜索范圍，求出需要填充的各小區(qū)間，把各小區(qū)間中最右邊的點并作為種子點壓入堆棧，轉到步驟2。

具體實現(xiàn)過程圖3.32掃描線種子填充算法的執(zhí)行過程1212123對于每一個待填充區(qū)段，只需壓棧一次；而在遞歸算法中，每個象素都需要壓棧。因此，掃描線填充算法提高了區(qū)域填充的效率。

12種子點位置不同3whilestack–not–emptydo

{pop(x,y)；*從堆棧中取一種子象素*savex:=x:*保存橫坐標x的值*whilegetpixel(FB,x,y),<>B–colordo{setpixel(FB,x,y,N–color);x:=x+1}xright:=x–1*保存線段的右端點*x:=savex–1;{*向種子的左邊填充*}whilegetpixel(FB,x,y)<>B–colordo{setpixel(FB,x,y,N–color);x:=x–1}xleft:=x+1*保存線段的左端點*x:=xleft;y:=y+1;whilex<=xrightdo

{span–need–fill:=false;算法程序：whilegetpixel(FB,x,y)<>N–colorandgetpixel(FB,x,y),<>B–colordo

{span–need–fill:=true;x:=x+1;}ifspan–need–fillthen

{push(x–1,y);右端點進棧span-need–fill:=false;}while(getpixel(FB,x,y)=B-colororgetpixel(FB,x,y)=N-color)andx<xrightdo{x:=x+1}

};*在上一條掃描上檢查完*y:=y–2;*在掃描線y–1上從左向右地檢查位于區(qū)間[xletft,xright]上的象素，其方法與在掃描線y+1上檢查的情況完全一樣，故略去詳情*}*出棧完*算法程序：123掃描線種子點填充算法的具體應用。紅色圓點代表種子點，掃描填充過程中，在要進棧的像素點的網(wǎng)格上依次標出他們的序號(進棧次序)；或是建立坐標系，寫出每一步棧中所有像素的坐標值(有次序)。1234567891011121314151610987654321×××××××××××××××××●××××××××××××××××××××××