二維填充圖元的生成

二維填充圖元的生成2023/7/81第1頁，課件共60頁，創(chuàng)作于2023年2月

掃描轉(zhuǎn)換矩形問題：矩形是簡單的多邊形，那么為什么要單獨(dú)處理矩形？比一般多邊形可進(jìn)行簡化計(jì)算。應(yīng)用非常多，窗口系統(tǒng)。共享邊界如何處理？ 原則：左閉右開，下閉上開屬于誰？2023/7/82第2頁，課件共60頁，創(chuàng)作于2023年2月掃描轉(zhuǎn)換矩形方法：voidFillRectangle(Rectangle*rect,intcolor) {intx,y; for(y=rect->ymin;y<=rect->ymax;y++) for(x=rect->xmin;x<=rect->xmax;x++) PutPixel(x,y,color); }/*endofFillRectangle() */2023/7/83第3頁，課件共60頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換范圍：多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。2023/7/84第4頁，課件共60頁，創(chuàng)作于2023年2月掃描轉(zhuǎn)換多邊形多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。2023/7/85第5頁，課件共60頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。幾種方法：逐點(diǎn)判斷法；掃描線算法；邊緣填充法；柵欄填充法；邊界標(biāo)志法。2023/7/86第6頁，課件共60頁，創(chuàng)作于2023年2月voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;

for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多邊形頂點(diǎn)個(gè)數(shù)

Pointvertexces[MAX]//多邊形頂點(diǎn)數(shù)組

}Polygon//多邊形結(jié)構(gòu)逐點(diǎn)判斷法2023/7/87第7頁，課件共60頁，創(chuàng)作于2023年2月逐個(gè)判斷繪圖窗口內(nèi)的像素：如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？1）射線法：2）累計(jì)角度法3）編碼法；逐點(diǎn)判斷法2023/7/88第8頁，課件共60頁，創(chuàng)作于2023年2月1）射線法步驟：從待判別點(diǎn)v發(fā)出射線求交點(diǎn)個(gè)數(shù)kK的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系逐點(diǎn)判斷法2023/7/89第9頁，課件共60頁，創(chuàng)作于2023年2月2）累計(jì)角度法步驟從v點(diǎn)向多邊形P頂點(diǎn)發(fā)出射線，形成有向角計(jì)算有向角的和，得出結(jié)論逐點(diǎn)判斷法2023/7/810第10頁，課件共60頁，創(chuàng)作于2023年2月逐點(diǎn)判斷的算法雖然程序簡單，但不可取。原因是速度太慢，主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬甚至幾百萬個(gè)象素都要一一判別，每次判別又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時(shí)間。逐點(diǎn)判斷法2023/7/811第11頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）2023/7/812第12頁，課件共60頁，創(chuàng)作于2023年2月

掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。

開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。掃描線算法2023/7/813第13頁，課件共60頁，創(chuàng)作于2023年2月

設(shè)多邊形P的頂點(diǎn)Pi=(xi,yi),i=0,1,…,n，又設(shè)yi0,yi1,…yin是各頂點(diǎn)Pi的坐標(biāo)yi的遞減數(shù)列，即yik≥yik+1,0≤k≤n-1這樣，當(dāng)yik≥yik+1,0≤k≤n-1時(shí)，屏幕上位于y=yik和y=yik+1兩條掃描線之間的長方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形），它們具有下列性質(zhì)：區(qū)域的連貫性2023/7/814第14頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。2）這些梯形可分為兩類：一類位于多邊形P的內(nèi)部；另一類在多邊形P的外部。3）兩類梯形在長方形區(qū)域{yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個(gè)在多邊形P內(nèi)，另一個(gè)在P外。

2023/7/815第15頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域的連貫性根據(jù)這些性質(zhì)，實(shí)際上只需知道該長方形區(qū)域內(nèi)任一梯形內(nèi)一點(diǎn)關(guān)于多邊形P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于P的內(nèi)外關(guān)系。2023/7/816第16頁，課件共60頁，創(chuàng)作于2023年2月

設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線y=e與多邊形P的Pi-1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為xei。

現(xiàn)設(shè)xei1,xei2,xei3,…,xeil是該掃描線與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱此序列為交點(diǎn)序列。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)：掃描線的連貫性2023/7/817第17頁，課件共60頁，創(chuàng)作于2023年2月掃描線的連貫性1）l是偶數(shù)。2）在該掃描線上，只有區(qū)段xeik,xeik+1）,k=1,3,5,…,l-1位于多邊形P內(nèi)，其余區(qū)段都在P外。以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。2023/7/818第18頁，課件共60頁，創(chuàng)作于2023年2月

設(shè)d為一整數(shù)，并且d=e-1,并且

yi0≥d≥yin。設(shè)位于掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdj3,…,xdjk

現(xiàn)在來討論掃描線d，e交點(diǎn)序列之間的關(guān)系。若多邊形P的邊Pr-1Pr與掃描線y=e,y=d都相交，則交點(diǎn)序列中對應(yīng)元素xer,xdr滿足下列關(guān)系：xer=xdr+1/mr(1)其中mr為邊Pr-1Pr的斜率。

邊的連貫性2023/7/819第19頁，課件共60頁，創(chuàng)作于2023年2月邊的連貫性

可利用d的交點(diǎn)序列計(jì)算e的交點(diǎn)序列：先運(yùn)用遞推關(guān)系式(1)求得與掃描線y=e和y=d都相交的所有多邊形上的交點(diǎn)xer；再求得與掃描線y=d不相交但與掃描線y=e相交的所有邊PqPq+1上的交點(diǎn)xeq。然后把這兩部分按遞增的順序排列，即可得e的交點(diǎn)序列。

2023/7/820第20頁，課件共60頁，創(chuàng)作于2023年2月當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是如果把每一奇點(diǎn)簡單地計(jì)為一個(gè)交點(diǎn)或者簡單地計(jì)為兩個(gè)交點(diǎn)，都可能出現(xiàn)奇數(shù)個(gè)交點(diǎn)。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？奇點(diǎn)的處理2023/7/821第21頁，課件共60頁，創(chuàng)作于2023年2月奇點(diǎn)的處理若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。若奇點(diǎn)做兩個(gè)交點(diǎn)處理，則情況B，交點(diǎn)個(gè)數(shù)不是偶數(shù)。2023/7/822第22頁，課件共60頁，創(chuàng)作于2023年2月奇點(diǎn)的處理多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點(diǎn)Pi為極值點(diǎn)；否則稱Pi為非極值點(diǎn)。規(guī)定：奇點(diǎn)是極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。奇點(diǎn)的預(yù)處理：非極值奇點(diǎn)屬于y值小的邊

2023/7/823第23頁，課件共60頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟算法基本思想：首先取d=yin。容易求得掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,…xdjn，這一序列由位于掃描線y=d上的多邊形P的頂點(diǎn)組成。由yin的交點(diǎn)序列開始，根據(jù)多邊形的邊的連貫性，按從下到上的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。2023/7/824第24頁，課件共60頁，創(chuàng)作于2023年2月即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（EdgeTable）和邊的活化鏈表AEL（ActiveEdgeList）兩部分組成。表結(jié)構(gòu)ET和AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成：

ymax

邊的上端點(diǎn)的y坐標(biāo)；

x在ET中表示邊的下端點(diǎn)的x坐標(biāo)，在AEL中則表示邊與掃描線的交點(diǎn)的坐標(biāo)；

Δx邊的斜率的倒數(shù)；

next指向下一條邊的指針。

數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟2023/7/825第25頁，課件共60頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟邊的分類表ET是按邊的下端點(diǎn)的y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列成行。

2023/7/826第26頁，課件共60頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟與當(dāng)前掃描線相交的邊稱為活性邊（activeedge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表（AEL,Activeedgetable)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。2023/7/827第27頁，課件共60頁，創(chuàng)作于2023年2月例子已知多邊形P=(P0P1P2P3P4P5P6P0)；其各邊坐標(biāo)分別為[P0（2，5）P1（2，10）P2（9，6）P3（16，11）P4（16，4）P5（12，2）P6（7，2）]建立其邊表和邊的活化鏈表2023/7/828第28頁，課件共60頁，創(chuàng)作于2023年2月邊表2023/7/829第29頁，課件共60頁，創(chuàng)作于2023年2月y=3Y=8活動(dòng)鏈表的例子2023/7/830第30頁，課件共60頁，創(chuàng)作于2023年2月算法實(shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下列步驟進(jìn)行：（1）取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號。（2）將邊的活化鏈表AEL設(shè)置為空。（3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。

2023/7/831第31頁，課件共60頁，創(chuàng)作于2023年2月算法實(shí)現(xiàn)步驟1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中。遞增方向排序。2）若相對于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對，依此類推。并填色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）x:=x+Δx。5）y:=y+1。2023/7/832第32頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法總結(jié)特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。缺點(diǎn)：對各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。2023/7/833第33頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法總結(jié)問題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？有孔的多邊形如何處理？如何處理圓、橢圓的掃描線算法？2023/7/834第34頁，課件共60頁，創(chuàng)作于2023年2月邊緣填充算法▼求余運(yùn)算：假定A為一個(gè)正整數(shù)，則M的余定義為A–M,記為。計(jì)算機(jī)中取A為n位能表示的最大整數(shù)。即，A=0xFFFFFFFF▼算法由來：光柵圖形中，如果某區(qū)域已著上值為M的顏色值，對該區(qū)域做偶數(shù)次求余運(yùn)算，該區(qū)域顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐榈念伾?。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就為邊緣填充算法。▼算法基本思想：對于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有象素取余。2023/7/835第35頁，課件共60頁，創(chuàng)作于2023年2月1、將當(dāng)前掃描線上的所有象素著上顏色；2、求余：

for(i=0;i<=m;i++)

在當(dāng)前掃描線上，從橫坐標(biāo)為Xi的交點(diǎn)向右求余；

算法1（以掃描線為中心的邊緣填充算法）2023/7/836第36頁，課件共60頁，創(chuàng)作于2023年2月 1、將繪圖窗口的背景色置為；

2、對多邊形的每一條非水平邊做： 從該邊上的每個(gè)象素開始向右求余；算法2（以邊為中心的邊緣填充算法）2023/7/837第37頁，課件共60頁，創(chuàng)作于2023年2月邊緣填充算法總結(jié)適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順序讀出幀緩存的內(nèi)容，送入顯示設(shè)備。優(yōu)點(diǎn)：算法簡單缺點(diǎn)：對于復(fù)雜圖形，每一象素可能被訪問多次，輸入/輸出的量比有序邊表算法大得多。2023/7/838第38頁，課件共60頁，創(chuàng)作于2023年2月引入柵欄，以減少填充算法訪問象素的次數(shù)。柵欄：與掃描線垂直的直線，通常過一頂點(diǎn)，且把多邊形分為左右二半?；舅枷耄簰呙杈€與多邊形的邊求交，將交點(diǎn)與柵欄之間的象素取補(bǔ)。減少了象素重復(fù)訪問數(shù)目，但不徹底。柵欄填充算法2023/7/839第39頁，課件共60頁，創(chuàng)作于2023年2月1.對多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對多邊形邊界所經(jīng)過的象素作一個(gè)邊界標(biāo)志。2.填充。對每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。Inside的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對未打標(biāo)志的點(diǎn)，inside不變。邊界標(biāo)志算法2023/7/840第40頁，課件共60頁，創(chuàng)作于2023年2月邊界標(biāo)志算法:算法過程voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}2023/7/841第41頁，課件共60頁，創(chuàng)作于2023年2月邊界標(biāo)志算法總結(jié)用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級。2023/7/842第42頁，課件共60頁，創(chuàng)作于2023年2月邊界標(biāo)志算法總結(jié)思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？2023/7/843第43頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的2023/7/844第44頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示(象素表示區(qū)域)枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示（幾何表示區(qū)域）枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色2023/7/845第45頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充區(qū)域填充要求區(qū)域是連通的連通性

4連通、8連通4連通：8連通2023/7/846第46頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對邊界有要求對邊界的要求內(nèi)點(diǎn)表示的4連通區(qū)域，它的邊界必然是一個(gè)8連通區(qū)域，反之，內(nèi)點(diǎn)表示的8連通區(qū)域，它的邊界必然是一個(gè)4連通區(qū)域2023/7/847第47頁，課件共60頁，創(chuàng)作于2023年2月A：適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色?，F(xiàn)取(x,y)為種子點(diǎn)對區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。步驟如下：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作：（1）棧頂象素出棧；（2）將出棧象素置成new_color

；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素在邊界內(nèi)且未置成new_color

，則把該象素入棧。種子填充算法2023/7/848第48頁，課件共60頁，創(chuàng)作于2023年2月種子填充算法例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示

2023/7/849第49頁，課件共60頁，創(chuàng)作于2023年2月種子填充算法遞歸算法可實(shí)現(xiàn)如下voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GetPixel(x,y)==oldColor){PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);}}/*endofFloodFill4() */

2023/7/850第50頁，課件共60頁，創(chuàng)作于2023年2月種子填充算法邊界表示的4連通區(qū)域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { PutPixel(x,y,newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}/*endofBoundaryFill4() */

2023/7/851第51頁，課件共60頁，創(chuàng)作于2023年2月該算法也可以填充有孔區(qū)域。

缺點(diǎn)：

(1)有些象素會(huì)入棧多次，降低算法效率；

(2)遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。改進(jìn)算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線填充算法種子填充算法2023/7/852第52頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法掃描線算法目標(biāo)：減少遞歸層次適用于邊界表示的4連通區(qū)域算法思想：在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在