多邊形的掃描轉(zhuǎn)換與區(qū)域填充2

1、2022年3月23日計(jì)算機(jī)圖形學(xué)13.4 多邊形的掃描轉(zhuǎn)換與區(qū)域填充o 多邊形掃描轉(zhuǎn)換與區(qū)域填充可以統(tǒng)稱區(qū)域填充，就是如何用顏色或圖案來填充一個(gè)二維區(qū)域。填充主要做兩件工作：一是確定需要填充的范圍，二是確定填充的內(nèi)容。一般區(qū)域填充指的是已知區(qū)域內(nèi)一個(gè)種子，然后由種子向周圍蔓延填充規(guī)定區(qū)域。o 方法：n掃描線法：x-掃描線法-有序邊表法，邊填充算法n種子填充算法（區(qū)域填充）2022年3月23日計(jì)算機(jī)圖形學(xué)23.4.1 掃描轉(zhuǎn)換（掃描線）法o 多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色

2、，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。o 三種方法：n掃描線算法n邊填充算法n邊界標(biāo)志法2022年3月23日計(jì)算機(jī)圖形學(xué)3多邊形分類o 多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。2022年3月23日計(jì)算機(jī)圖形學(xué)4多邊形表示o 多邊形的表示方法n頂點(diǎn)表示n點(diǎn)陣表示o 頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。o 點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。2022年3月23日計(jì)算機(jī)圖形學(xué)53.4.1.1掃描線算法-x掃描線法o 掃描線算法n 目標(biāo)：利用相鄰像素之間的連貫性，

3、提高算法效率n 處理對(duì)象：非自交多邊形 （邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）2022年3月23日計(jì)算機(jī)圖形學(xué)6步驟(1)確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點(diǎn)的最小和最大y值（ymin和ymax）。(2)從y=ymin到y(tǒng)=ymax，每次用一條掃描線進(jìn)行填充。(3)對(duì)一條掃描線填充的過程可分為四個(gè)步驟：計(jì)算掃描線與多邊形各邊的交點(diǎn)。對(duì)求得的交點(diǎn)進(jìn)行排序。奇偶配對(duì)求出掃描線與多邊形的相交區(qū)間。 對(duì)這些相交區(qū)間填充色。2022年3月23日計(jì)算機(jī)圖形學(xué)7需要解決的幾個(gè)問題o 掃描線與多邊形頂點(diǎn)相交時(shí)交點(diǎn)的取舍問題o 多邊形邊界上像素點(diǎn)的取舍問題o 水平邊的處理o 減少求交運(yùn)算問題2022年3月

4、23日計(jì)算機(jī)圖形學(xué)8需要解決的幾個(gè)問題（一）一、當(dāng)掃描線與多邊形頂點(diǎn)相交時(shí)，交點(diǎn)的取舍問題。解決：當(dāng)掃描線與多邊形的頂點(diǎn)相交時(shí)，n 若共享頂點(diǎn)的兩條邊分別落在掃描線的兩邊，交點(diǎn)只算一個(gè)；n 若共享頂點(diǎn)的兩條邊在掃描線的同一邊，這時(shí)交點(diǎn)作為零個(gè)或兩個(gè)。2022年3月23日計(jì)算機(jī)圖形學(xué)9具體實(shí)現(xiàn)時(shí)只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的Y值，兩個(gè)Y值中大于交點(diǎn)Y值的個(gè)數(shù)是0，1，2，來決定取0，1，2個(gè)交點(diǎn)。2022年3月23日計(jì)算機(jī)圖形學(xué)10 xy213 4 5 6 7 8 9111234567891011121012與多邊形頂點(diǎn)相交的交點(diǎn)的處理2022年3月23日計(jì)算機(jī)圖形學(xué)11011110222

5、 與掃描線相交的多邊形頂點(diǎn)的交點(diǎn)數(shù)2022年3月23日計(jì)算機(jī)圖形學(xué)12需要解決的幾個(gè)問題（二）二、邊界上象素的取舍問題，避免填充擴(kuò)大化。解決方法：邊界象素：規(guī)定落在右上邊界的象素不予填充。具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交區(qū)間實(shí)行：左閉右開（左邊界像素填充，右邊界像素不填充）下閉上開（下邊界像素填充，上邊界像素不填充）屬于誰？2022年3月23日計(jì)算機(jī)圖形學(xué)13需要解決的幾個(gè)問題（三）三、水平邊的處理（與掃描線重合） 將水平邊畫出后刪去，不參加求交，即求交后的操作（但是在計(jì)算交點(diǎn)個(gè)數(shù)時(shí)算作一個(gè)點(diǎn)）。2022年3月23日計(jì)算機(jī)圖形學(xué)14需要解決的幾個(gè)問題（四）o 減少求交算法：x-掃描線法在

6、處理每條掃描線時(shí)需要與多邊形的所有邊求交，而實(shí)際上一條掃描線往往只與少數(shù)幾條邊相交，因此降低了效率，于是提出了改進(jìn)算法有序邊表法，也稱y連貫性算法。2022年3月23日計(jì)算機(jī)圖形學(xué)153.4.1.2 掃描轉(zhuǎn)換法-有序邊表法o 該法與x-掃描線法基本過程一樣，只是在處理求交計(jì)算時(shí)作了改進(jìn)。2022年3月23日計(jì)算機(jī)圖形學(xué)16改進(jìn)思路可以從以下方面考慮：1 在處理一條掃描線時(shí)，僅對(duì)與它相交的邊（有效邊）進(jìn)行求交運(yùn)算，于是可以構(gòu)造活性邊表。2 考慮掃描描線的連貫性，即當(dāng)前掃描線與各邊的交點(diǎn)順序與下一條掃描線與各邊的交點(diǎn)順序很可能相同或者相似。3 多邊形邊的連貫性，即當(dāng)一條邊與當(dāng)前掃描線相交時(shí)，它可能

7、也與下一條掃描線相交。2022年3月23日計(jì)算機(jī)圖形學(xué)17o 所有的邊和掃描線求交，效率很低。因?yàn)橐粭l掃描線往往只和少數(shù)幾條邊相交。如何判斷多邊形的一條邊與掃描線是否相交？o 有效邊（Active Edge）：指與當(dāng)前掃描線相交的多邊形的邊，也稱為活性邊。o 有效邊表（Active Edge Table, AET）：把有效邊按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，此鏈表稱為有效（活性）邊表。2022年3月23日計(jì)算機(jī)圖形學(xué)18數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟o 只需對(duì)當(dāng)前掃描線的活動(dòng)邊表作更新，即可得到下一條掃描線的活動(dòng)邊表。2022年3月23日計(jì)算機(jī)圖形學(xué)19如何計(jì)算下一條掃描線與邊的交點(diǎn)直線方程

8、：ax+by+c = 0當(dāng)前交點(diǎn)坐標(biāo)：(xi, yi)下一交點(diǎn)坐標(biāo)：(xi+1,yi+1)xi+1= (-byi+1)-c)/a = (-byi+1)-c)/a =xi-b/a=xi-1/k活動(dòng)邊表中需要存放的信息：x：當(dāng)前掃描線與邊的交點(diǎn)dx-b/a：從當(dāng)前掃描線到下一條掃描線之間的x增量xymax：邊所交的最高掃描線2022年3月23日計(jì)算機(jī)圖形學(xué)20數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟o 為了方便邊的活化鏈表的更新，建立另一個(gè)表-新邊表，存放在該掃描線第一次出現(xiàn)的邊。存放的信息：x：掃描線與該邊的初始交點(diǎn)dx：x的增量ymax：該邊的最大y值2022年3月23日計(jì)算機(jī)圖形學(xué)21數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟即算法中采

9、用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的新邊表NET（new Edge Table）和邊的活性邊表AET（Active Edge Table ）兩部分組成。 表結(jié)構(gòu)NET和AET中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成： ymax ：邊的上端點(diǎn)的y坐標(biāo)； x：在NET中表示邊的最低點(diǎn)的x坐標(biāo)，在AET中則表示邊與掃描線的交點(diǎn)的坐標(biāo)； x：邊的斜率的倒數(shù)；（當(dāng)前掃描線到下一條掃描線x的增量） next ：指向下一條邊的指針。2022年3月23日計(jì)算機(jī)圖形學(xué)22ymaxx1/m(x)nextymaxx1/m (x)nextAET 活性邊表NET 新邊表X:邊的下端點(diǎn)的x坐標(biāo)X:邊與掃描線的交點(diǎn)的坐標(biāo)

10、2022年3月23日計(jì)算機(jī)圖形學(xué)232022年3月23日計(jì)算機(jī)圖形學(xué)24活性邊表的例子34-2P3 P456.50.5P3 P2掃描線2AET指針620P4 P5570.5P3 P2掃描線3AET指針(Y(Ymax, max, x,x, next)x,x, next)36-2P3 P4560.5P3 P2掃描線1AET指針2022年3月23日計(jì)算機(jī)圖形學(xué)25活性邊表的例子620P4 P557.50.5P3 P2掃描線4AET指針620P4 P578-1P2 P1掃描線5AET指針724P5 P178-1P2 P1掃描線6AET指針2022年3月23日計(jì)算機(jī)圖形學(xué)26新邊表724P5 P178-

11、1P2 P1620P4 P536-2P3 P4560.5P3 P2(Ymax, x,x, next)2022年3月23日計(jì)算機(jī)圖形學(xué)27算法實(shí)現(xiàn)步驟 這樣，當(dāng)建立了邊的分類表NET后，掃描線算法可按下列步驟進(jìn)行： （1）取掃描線縱坐標(biāo)y的初始值為NET中非空元素的最小序號(hào)。 （2）將邊的活化鏈表AET設(shè)置為空。 （3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。2022年3月23日計(jì)算機(jī)圖形學(xué)28算法實(shí)現(xiàn)步驟o1）如邊分類表NET中的第y類元素非空，則將屬于該類的所有邊從AET中取出并插入邊的活化鏈表中，AET中的各邊按照x值

12、（當(dāng)x值相等時(shí)，按x值）遞增方向排序。o2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AET中的邊兩兩依次配對(duì)，即1，2邊為一對(duì)，3，4邊為一對(duì)，依次類推。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。o3）將邊的活化鏈表AET中滿足y=ymax的邊刪去。o4）將邊的活化鏈表AET剩下的每一條邊的x域累加x，即x:=x+x。o5）將當(dāng)前的掃描線的縱坐標(biāo)值y累加1，即y:=y+1。2022年3月23日計(jì)算機(jī)圖形學(xué)29掃描線算法o 特點(diǎn)：算法效率較高。o 缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。2022年3月23日

13、計(jì)算機(jī)圖形學(xué)30掃描線算法o 問題：n 如何處理多邊形的水平邊？n 如何修改掃描線算法，使它能處理邊自交的多邊形？2022年3月23日計(jì)算機(jī)圖形學(xué)313.4.1.3 邊填充法o 算法簡(jiǎn)單，但對(duì)于復(fù)雜圖型，每一象素可能被訪問多次o 算法過程：對(duì)于每一條掃描線和每條多邊形邊的交點(diǎn)（x1,y1）,將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)，對(duì)多邊形的每條邊做同樣處理，多邊形順序隨意，如下圖：2022年3月23日計(jì)算機(jī)圖形學(xué)322022年3月23日計(jì)算機(jī)圖形學(xué)333.4.1.4 柵欄填充算法柵欄填充算法為了減少重復(fù)計(jì)算，可采用柵欄算法，柵欄指的是一條過多邊形頂點(diǎn)且與掃描線垂直的直線。它把多邊形分為兩半。202

14、2年3月23日計(jì)算機(jī)圖形學(xué)34算法過程o 對(duì)于每個(gè)掃描線與多邊形的交點(diǎn)，將交點(diǎn)與柵欄之間的像素取補(bǔ)，若交點(diǎn)位于柵欄左邊，則將交點(diǎn)之右，柵欄之作的所有像素取補(bǔ)，若交點(diǎn)位于柵欄右邊，則將柵欄之左，交點(diǎn)之右的像素取補(bǔ)。 2022年3月23日計(jì)算機(jī)圖形學(xué)35柵欄算法圖示2022年3月23日計(jì)算機(jī)圖形學(xué)363.4.1.5 邊界標(biāo)志算法o 1. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過的象素作一個(gè)邊界標(biāo)志。o 2.填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。o 取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則

15、inside為假。o Inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。2022年3月23日計(jì)算機(jī)圖形學(xué)37邊界標(biāo)志算法:算法過程ovoid edgemark_fill(polydef, color)o多邊形定義 polydef； int color;o 對(duì)多邊形polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換；o inside = FALSE;o for (每條與多邊形polydef相交的掃描線y )o for (掃描線上每個(gè)象素x )o if(象素 x 被打上邊標(biāo)志)o inside = ! (inside);o if(inside

16、！= FALSE)o drawpixel (x, y, color);o else drawpixel (x, y, background);o o 2022年3月23日計(jì)算機(jī)圖形學(xué)38邊界標(biāo)志算法o 用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，o 但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。o 思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？2022年3月23日計(jì)算機(jī)圖形學(xué)393.4.2 區(qū)域填充算法3.4.2.1 種子填充法o 區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。o 區(qū)域填充指先

17、將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的2022年3月23日計(jì)算機(jī)圖形學(xué)40區(qū)域填充o 表示方法：內(nèi)點(diǎn)表示、邊界表示o 內(nèi)點(diǎn)表示n枚舉出區(qū)域內(nèi)部的所有像素n內(nèi)部的所有像素著同一個(gè)顏色n邊界像素著與內(nèi)部像素不同的 顏色o 邊界表示n枚舉出邊界上所有的像素n邊界上的所有像素著同一顏色n內(nèi)部像素著與邊界像素不同的顏色2022年3月23日計(jì)算機(jī)圖形學(xué)41區(qū)域填充o 區(qū)域填充要求區(qū)域是連通的o 連通性：4連通、8連通n 4連通：n 8連通44p44(b)p的8-鄰接點(diǎn)88888p888(a)p的4-鄰接點(diǎn) 鄰接點(diǎn)的定義2022年3月23日計(jì)算機(jī)圖形學(xué)42

18、區(qū)域填充o 4連通與8連通區(qū)域的區(qū)別n 連通性： 4連通可看作8連通區(qū)域，但對(duì)邊界有要求2022年3月23日計(jì)算機(jī)圖形學(xué)43 區(qū)域的邊界表示和內(nèi)點(diǎn)表示(a)以邊界表示的4-連通區(qū)域(d)以內(nèi)點(diǎn)表示的8-連通區(qū)域(b)以內(nèi)點(diǎn)表示的4-連通區(qū)域(c)以邊界表示的8-連通區(qū)域2022年3月23日計(jì)算機(jī)圖形學(xué)44四鄰域法不能正確填充一些特殊圖形2022年3月23日計(jì)算機(jī)圖形學(xué)45種子填充算法-4鄰域算法的輸入：種子點(diǎn)坐標(biāo)(x,y)，填充色和邊界顏色。棧結(jié)構(gòu)實(shí)現(xiàn)4-連通邊界填充算法的算法步驟為：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)按一定順序

19、檢查出棧象素的4-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。2022年3月23日計(jì)算機(jī)圖形學(xué)46種子填充算法-8鄰域棧結(jié)構(gòu)實(shí)現(xiàn)8-連通邊界填充算法連通邊界填充算法的算法步驟算法步驟為：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)按一定順序檢查出棧象素的8-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。2022年3月23日計(jì)算機(jī)圖形學(xué)47種子填充算法適合于內(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)對(duì)區(qū)域G進(jìn)行填充：

20、即先置像素(x,y)的顏色為new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。 步驟如下：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作： （1）棧頂象素出棧； （2）將出棧象素置成多邊形色； （3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。2022年3月23日計(jì)算機(jī)圖形學(xué)48舉例o 以s1為種子，按照左、上、右、下順序入棧出棧，過程如下： 2022年3月23日計(jì)算機(jī)圖形學(xué)492022年3月23日計(jì)算機(jī)圖形學(xué)5068454468422684533S1S16845568466S1S1123456789101168446886

21、6684988684996849772022年3月23日計(jì)算機(jī)圖形學(xué)51種子填充算法o 例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)o 設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示 2022年3月23日計(jì)算機(jī)圖形學(xué)52種子填充算法o遞歸算法可實(shí)現(xiàn)如下：void FloodFill4(int x,int y,int oldColor,int newColor) if(GetPixel(x,y) = oldColor) PutPixel(x,y,newColor); FloodF

22、ill4(x,y+1,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); /*end of FloodFill4()*/ 2022年3月23日計(jì)算機(jī)圖形學(xué)53種子填充算法-邊界表示的4連通區(qū)域void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color = GetPixel(x,y);if(co

23、lor != 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);/*end of BoundaryFill4() */ 2022年3月23日計(jì)算機(jī)圖形學(xué)54種子填充算法該算法也可以填充有孔區(qū)域。 o 缺點(diǎn)：n(1) 有些

24、象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。n(2) 遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。o 解決方法n改進(jìn)算法，減少遞歸次數(shù)，提高效率。n解決方法是用掃描線填充算法2022年3月23日計(jì)算機(jī)圖形學(xué)553.4.2.2 掃描線種子算法（四連通）o 目標(biāo)：減少遞歸層次o 適用于邊界表示的4連通區(qū)域o 算法思想：在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進(jìn)行這個(gè)過程，直到所保存的個(gè)區(qū)段都填充完畢。2022年3月23日計(jì)算機(jī)圖形學(xué)56掃描線填充算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若棧空則結(jié)束。否則取棧頂元素（x， y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y） 出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點(diǎn)：在區(qū)間xl，xr中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。 上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填