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

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

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

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

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

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

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

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

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

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

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

為了使交點(diǎn)個(gè)數(shù)保持為偶數(shù),規(guī)定當(dāng)奇點(diǎn)是P的極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算；否則按一個(gè)交點(diǎn)計(jì)算。

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

ymax

邊的上端點(diǎn)的y坐標(biāo)在ET中為邊的下端點(diǎn)的x坐標(biāo)x在AEL中是邊與掃描線交點(diǎn)的x坐標(biāo)Δ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)]對奇點(diǎn)采用了預(yù)處理的邊y筒分類表ET是按邊下端點(diǎn)的縱坐標(biāo)y對邊進(jìn)行分類的指針數(shù)組同一類中，各邊按x值遞增的順序排列成行下端點(diǎn)的縱坐標(biāo)y等于i的邊歸入第i類，水平邊除外[P0P1P2P3P4P5

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

-5/357AELe7e54212AEL在y=2掃描線上的當(dāng)前狀態(tài)它記錄了多邊形沿掃描線的交點(diǎn)序列,并根據(jù)遞推關(guān)系,不斷地更新交點(diǎn)序列它是一個(gè)動(dòng)態(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掃描線上的當(dāng)前狀態(tài)-5/35AELe7e54216AEL在y=4掃描線上的當(dāng)前狀態(tài)E4邊做了預(yù)處理(也可以不做預(yù)處理，但要清楚的知道此點(diǎn)要在AEL中計(jì)幾次)掃描線算法實(shí)現(xiàn)步驟步驟1:(AEL初始化)將邊的活化鏈表AEL設(shè)置為空。步驟2:(y初始化)取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號步驟3：按從下到上的順序?qū)v坐標(biāo)值為y的掃描線(當(dāng)前掃描線)執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表AEL都變成空為止。(1)如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表AEL中，AEL中的各邊按照x值(當(dāng)x的值相等時(shí)，按Δx值)遞增方向排序。(2)若相對于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對，即第1，2邊為一對，第3，4邊為一對，依此類推。每一對邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對這些區(qū)段上的點(diǎn)(象素)按多邊形屬性著色。(3)將邊的活化鏈表AEL中滿足y=ymax的邊刪去。

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

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

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

圖邊界標(biāo)志算法的運(yùn)行過程4.3.5邊界標(biāo)志算法邊界標(biāo)志法具體實(shí)現(xiàn)圖邊界標(biāo)志算法的運(yùn)行過程步驟1：以值為boundary-color的特殊顏色勾畫多邊形P的邊界。設(shè)多邊形頂點(diǎn)為Pi=(xi,yi),0≤i≤n，xi,yi均為整數(shù)；置Pn+1=P0。每一條掃描線上著上這種特殊顏色的點(diǎn)的個(gè)數(shù)必定是偶數(shù)(包括零)。步驟2：設(shè)interior_point是一布爾變量。對每一條掃描線從左到右進(jìn)行搜索，如果當(dāng)前是像素位于多邊形P內(nèi)，則interior_point=true，需要填上值為polygon_color的顏色；否則該像素在多邊形P外，需要填上值為background_color的顏色邊界標(biāo)志算法實(shí)例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算法實(shí)現(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]){//獲得多邊形邊的端點(diǎn) 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));//標(biāo)志邊界并處理奇點(diǎn) 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;//多邊形內(nèi)部標(biāo)志變量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));//在多邊形內(nèi)部填充色藍(lán)色elsedc->SetPixel(x1,y1,RGB(255,255,255));//在多邊形外部填充色白色 }}算法特點(diǎn)分析：1本算法避免了對幀緩存的大量元素的賦值2但需逐條掃描線并對幀緩存中的元素進(jìn)行搜索和比較3當(dāng)算法生成的邊界不封閉時(shí)，在一條掃描線上必須有偶數(shù)個(gè)具有邊界顏色的點(diǎn)第4章基本光柵圖形生成算法4.4區(qū)域填充4.4.1區(qū)域的基本概念是指已經(jīng)表示成點(diǎn)陣形式的像素集合。區(qū)域區(qū)域的表示方式在光柵圖形中，有內(nèi)點(diǎn)表示法和邊界表示法內(nèi)點(diǎn)表示法：把位于給定區(qū)域內(nèi)的所有像素一一列舉出來的方法稱為內(nèi)點(diǎn)表示法。邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。是指先將區(qū)域內(nèi)的一點(diǎn)(常稱種子點(diǎn))賦予給定顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過程。區(qū)域填充一個(gè)封閉區(qū)域確定以后,填充要解決的問題是如何確定填充的像素以及如何高效地填充。4連通的區(qū)域:取區(qū)域內(nèi)任意兩點(diǎn)，在該區(qū)域內(nèi)若從其中一點(diǎn)出發(fā)通過上、下、左、右四種運(yùn)動(dòng)可到達(dá)另一點(diǎn)。四個(gè)方向的運(yùn)動(dòng)8連通區(qū)域:

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

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

簡單的種子填充算法

（4連通）種子像素入棧當(dāng)棧非空時(shí)，重復(fù)以下步驟：棧頂像素出棧將出棧象素置成填充色

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

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

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

12種子點(diǎn)位置不同3whilestack–not–emptydo

{pop(x,y)；*從堆棧中取一種子象素*savex:=x:*保存橫坐標(biāo)x的值*whilegetpixel(FB,x,y),<>B–colordo{setpixel(FB,x,y,N–color);x:=x+1}xright:=x–1*保存線段的右端點(diǎn)*x:=savex–1;{*向種子的左邊填充*}whilegetpixel(FB,x,y)<>B–colordo{setpixel(FB,x,y,N–color);x:=x–1}xleft:=x+1*保存線段的左端點(diǎn)*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);右端點(diǎn)進(jìn)棧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掃描線種子點(diǎn)填充算法的具體應(yīng)用。紅色圓點(diǎn)代表種子點(diǎn)，掃描填充過程中，在要進(jìn)棧的像素點(diǎn)的網(wǎng)格上依次標(biāo)出他們的序號(進(jìn)棧次序)；或是建立坐標(biāo)系，寫出每一步棧中所有像素的坐標(biāo)值(有次序)。1234567891011121314151610987654321×××××××××××××××××●××××××××××××××××××××××