計(jì)算機(jī)圖形學(xué)5多邊形掃描轉(zhuǎn)換與區(qū)域填充

多邊形的掃描轉(zhuǎn)換與區(qū)域填充一、多邊形的掃描轉(zhuǎn)換前面講的畫直線是一維圖形的光柵化，就是如何在計(jì)算機(jī)屏幕上即在一個(gè)離散的像素集上表示一個(gè)連續(xù)的圖形。而多邊形的掃描轉(zhuǎn)換和區(qū)域填充這個(gè)問題是怎么樣在離散的像素集上表示一個(gè)連續(xù)的二維圖形。多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。

點(diǎn)陣表示P1P2P3P4P5頂點(diǎn)表示P6

頂點(diǎn)表示是用多邊形的頂點(diǎn)序列來表示多邊形。這種表示直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換，但由于它沒有明確指出哪些象素在多邊形內(nèi)，故不能直接用于面著色。

點(diǎn)陣表示是用位于多邊形內(nèi)的象素集合來刻畫多邊形。這種表示丟失了許多幾何信息（如邊界、頂點(diǎn)等），但它卻是光柵顯示系統(tǒng)顯示時(shí)所需的表示形式。這涉及到兩個(gè)問題：第一個(gè)問題是如果知道邊界，能否求出這個(gè)多邊形哪些像素在多邊形內(nèi)。眾所周知，在計(jì)算機(jī)上畫圖形，實(shí)際上就是寫幀緩存（framebuffer）。如果知道多邊形哪些像素在里面，就直接寫到幀緩存里即可。

第二個(gè)問題是知道多邊形內(nèi)部的像素，反過來求多邊形的邊界。很遺憾，這個(gè)問題不是圖形學(xué)關(guān)心的問題，是模式識別所關(guān)心的問題。圖形學(xué)、圖像處理、模式識別、計(jì)算機(jī)視覺有密切的聯(lián)系。我們只關(guān)心從頂點(diǎn)表示到點(diǎn)陣表示。光柵圖形的一個(gè)基本問題是把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。這種轉(zhuǎn)換稱為多邊形的掃描轉(zhuǎn)換。為什么叫掃描轉(zhuǎn)換？因?yàn)楣鈻棚@示器是逐行掃描！區(qū)域填充:指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形等：（1）凸多邊形任意兩頂點(diǎn)間的連線均在多邊形內(nèi)。（2）凹多邊形任意兩頂點(diǎn)間的連線有不在多邊形內(nèi)的部分。凸多邊形凹多邊形含內(nèi)環(huán)的多邊形

有關(guān)概念

1)區(qū)域：一組相鄰而且又相連的像素，而且具有相同屬性的封閉區(qū)域。3)區(qū)域填充：以某種屬性對整個(gè)區(qū)域進(jìn)行設(shè)置的過程。2）種類：①單域②復(fù)合域逐點(diǎn)判斷填充算法區(qū)域填充的基本(初級)方法:逐點(diǎn)判斷填充算法逐點(diǎn)判斷繪圖窗口內(nèi)的每一個(gè)像素；若在區(qū)域的內(nèi)部：用指定的屬性設(shè)置該點(diǎn)；否則不予處理；設(shè)有如下函數(shù)：

TruewhenxDInside(D,x,y)=FalsewhenxDD取矩形R(x1≤x≤x2,y1≤y≤y2)，使R包圍D，則逐點(diǎn)判斷填充算法如下：for(y=y1;y<=y2;y++)for(x=x1;x<=x2;x++)if(inside(D,x,y))drawpixel(x,y,color);上述算法原理簡單、實(shí)用，但效率低；效率低的原因是沒有考慮各象素之間的聯(lián)系，孤立地考察象素與區(qū)域的關(guān)系，使得幾十萬甚至幾百萬個(gè)象素都要一一判別，每次判別又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時(shí)間。1）射線法；2）累計(jì)角度法；3）編碼法；4）……..如何判斷點(diǎn)在多邊形的內(nèi)或外？（包含性檢查的方法）1）射線法；

過被檢測點(diǎn)任作一條射線,求其與邊界的交點(diǎn),若交點(diǎn)數(shù)為偶數(shù),則該點(diǎn)在邊界之外,否則在邊界之內(nèi)。

PP逐點(diǎn)判斷法2）累計(jì)角度法步驟從v點(diǎn)向多邊形P頂點(diǎn)發(fā)出射線，形成有向角計(jì)算有相交的和，得出結(jié)論現(xiàn)在的問題是，知道多邊形的邊界，如何找到多邊形內(nèi)部的點(diǎn)，即把多邊形內(nèi)部填上顏色。對每條橫越多邊形的掃描線，掃描轉(zhuǎn)換算法確定掃描線與多邊形邊的交點(diǎn)位置。掃描線交點(diǎn)交點(diǎn)交點(diǎn)交點(diǎn)

X-掃描線算法填充多邊形的基本思想是按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。

區(qū)間的端點(diǎn)可以通過計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。根據(jù)該原理，X-掃描線算法可以填充凸的、凹的、還可以是帶孔的多邊形。1、x-掃描線算法掃描線交點(diǎn)交點(diǎn)交點(diǎn)交點(diǎn)對于每條穿越多邊形的掃描線，X-掃描線算法確定掃描線與多邊形邊相交區(qū)間的像素點(diǎn)位置。x-掃描線算法填充多邊形xy213456789111234567891011121012如掃描線y=3與多邊形的邊界相交于4點(diǎn)：（2，3）、（4，3）、（7，3）、（9，3）。這四點(diǎn)定義了掃描線從X=2到X=4，從X=7到X=9兩個(gè)落在多邊形內(nèi)的區(qū)間，該區(qū)間內(nèi)的像素應(yīng)取填充色。從該例可以看出，算法的核心是需按x遞增順序排列交點(diǎn)的x坐標(biāo)序列。由此，可得到X-掃描線算法步驟如下：（1）確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點(diǎn)的最小和最大y值（ymin和ymax）。（2）從y=ymin到y(tǒng)=ymax，每次用一條掃描線進(jìn)行填充。（3）對一條掃描線填充的過程可分為四個(gè)步驟：a、求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)；b、排序：把所有交點(diǎn)按遞增順序進(jìn)行排序；注意：交點(diǎn)在計(jì)算時(shí)未必是按遞增順序排列的。c、交點(diǎn)配對：第一個(gè)與第二個(gè)，第三個(gè)與第四個(gè)等等，每對交點(diǎn)就代表掃描線與多邊形的一個(gè)相交區(qū)間；d、區(qū)間填色：把這些相交區(qū)間內(nèi)的像素置成不同于背景色的填充色。在填充過程，當(dāng)掃描線與多邊形頂點(diǎn)相交時(shí)，交點(diǎn)的取舍問題??（交點(diǎn)的個(gè)數(shù)應(yīng)保證為偶數(shù)個(gè)）。xy213456789111234567891011121012與多邊形頂點(diǎn)相交的交點(diǎn)的處理當(dāng)掃描線與多邊形頂點(diǎn)相交時(shí)，會出現(xiàn)異常情況。解決方案：（1）、若共享頂點(diǎn)的兩條邊分別落在掃描線的兩邊，交點(diǎn)只算一個(gè)；（2）若共享頂點(diǎn)的兩條邊在掃描線的同一邊，這時(shí)交點(diǎn)作為零個(gè)或兩個(gè)。具體實(shí)現(xiàn)方式是：檢查共享頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的y值，按這兩個(gè)y值中大于交點(diǎn)y值的個(gè)數(shù)是0、1、2來決定交點(diǎn)數(shù)取0、1、2。

與掃描線相交的多邊形頂點(diǎn)的交點(diǎn)數(shù)123456789011110222但這個(gè)算法效率比較低，因?yàn)檫@個(gè)算法的關(guān)鍵問題是求交！而求交是很可怕的，求交的計(jì)算量是非常大的。假設(shè)一個(gè)100邊形（一個(gè)卡通片至少是100、200個(gè)邊形），現(xiàn)在每條掃描線和這個(gè)多邊形求交點(diǎn)，一共有1024條掃描線，一共要進(jìn)行10萬多次求交運(yùn)算，每次求交還要做大量的加減乘除法，計(jì)算量太大。

最理想的算法是不求交（排序、配對、填色總是要的）！如果不求交，那會極大提高算法的效率。

為了計(jì)算每條掃描線與多邊形各邊的交點(diǎn)，最簡單的方法是把多邊形的所有邊放在一個(gè)表中。在處理每條掃描線時(shí)，按順序從表中取出所有的邊，分別與掃描線求交。掃描轉(zhuǎn)換算法重要意義是提出了圖形學(xué)里兩個(gè)重要的思想：第一個(gè)思想是掃描線的思想，當(dāng)處理圖形圖像時(shí)按一條條掃描線處理；第二個(gè)思想是增量的思想。DDA在算y值的時(shí)候是采用增量的方法，求交點(diǎn)的時(shí)候能不能也采取增量的方法？每條掃描線的y值都知道，關(guān)鍵是求x的值。X是什么？2、多邊形的掃描轉(zhuǎn)換算法可以從三方面考慮加以改進(jìn)：（1）在處理一條掃描線時(shí)，僅對與它相交的多邊形的邊（有效邊）進(jìn)行求交運(yùn)算。（2）需要考慮掃描線的連貫性，即當(dāng)前掃描線與各邊的交點(diǎn)順序與下一條掃描線與各邊的交點(diǎn)順序很可能相同或非常相似，這樣在當(dāng)前掃描線處理完畢之后，不必為下一條掃描線從頭開始構(gòu)造交點(diǎn)信息。（3）最后考慮多邊形的連貫性，即當(dāng)某條邊與當(dāng)前掃描線相交時(shí)，它很可能也與下一條掃描線相交。為了避免求交運(yùn)算，需要引進(jìn)一套特殊的數(shù)據(jù)結(jié)構(gòu)。這套數(shù)據(jù)結(jié)構(gòu)在后面的消隱算法中還要出現(xiàn)。數(shù)據(jù)結(jié)構(gòu)：11/k

與多邊形邊界相交的兩條

連續(xù)掃描線交點(diǎn)的相關(guān)性xi,yixi+1,yi+1隨著掃描線的移動(dòng)，掃描線與多邊形的交點(diǎn)和上一次交點(diǎn)相關(guān)：設(shè)邊的直線斜率為k，若y=yi時(shí)，x=xi，則當(dāng)y=yi+1=yi+1時(shí)，xi+1=xi+1/k活性邊表(AET)：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中。

x

△x

ymaxnext結(jié)點(diǎn)內(nèi)容（一個(gè)結(jié)點(diǎn)在數(shù)據(jù)結(jié)構(gòu)里可用結(jié)構(gòu)來表示）x：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)△x：從當(dāng)前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線的坐標(biāo)值ymax即△x=1/k為常量。則下一條掃描線與該邊的交點(diǎn)不要重新計(jì)算，只要加一個(gè)增量△x。x

△xymaxnext其中x為當(dāng)前掃描線與邊的交點(diǎn)，ymax是邊所在的最大掃描線值，通過它可以知道何時(shí)才能“拋棄”該邊，△x表示從當(dāng)前掃描線到下一條掃描線之間的x增量即斜率的倒數(shù)。next為指向下一條邊的指針另外使用增量法計(jì)算時(shí)，我們需要知道一條邊何時(shí)不再與下一條掃描線相交，以便及時(shí)把它從有效邊表中刪除出去，避免下一步進(jìn)行無謂的計(jì)算。綜上所述，有效邊表AET的每個(gè)結(jié)點(diǎn)存放對應(yīng)邊的有關(guān)信息如下：一個(gè)多邊形與若干掃描線看掃描線y=6的活性邊表：為了方便有效邊表的建立與更新，需構(gòu)造一個(gè)新邊表（NET），用來存放多邊形的邊的信息，分為4個(gè)步驟：（1）首先構(gòu)造一個(gè)縱向鏈表，鏈表的長度為多邊形所占有的最大掃描線數(shù)，鏈表的每個(gè)結(jié)點(diǎn)，稱為一個(gè)桶，對應(yīng)多邊形覆蓋的每一條掃描線。（2）將每條邊的信息鏈入與該邊最小y坐標(biāo)（ymin）相對應(yīng)的桶處。也就是說，存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點(diǎn)為ymin，則該邊就放在掃描線ymin的新邊表中。（3）每條邊的數(shù)據(jù)形成一個(gè)結(jié)點(diǎn)，內(nèi)容包括：該掃描線與該邊的初始交點(diǎn)x（即較低端點(diǎn)的x值），1/k，以及該邊的最大y值ymax。x|ymin1/kymaxnext（4）同一桶中若干條邊按X|ymin由小到大排序。若X|ymin

相等，則按照1/k由小到大排序。一個(gè)多邊形與若干掃描線

7

6

5

4

3

2

1

0

8P1P2

P2P3

5-32

533P4P5

P5P6

207

1108

528

5-1.57P6P1P3P4這個(gè)結(jié)構(gòu)實(shí)際上是一個(gè)指針數(shù)組，數(shù)組的每個(gè)變量是個(gè)指針，這個(gè)指針指向所有的以這個(gè)y值作為起點(diǎn)的邊。把多邊形所有的邊全部填成這樣的結(jié)構(gòu)，插到這個(gè)指針數(shù)組里面來。如y=1,y=5指向哪些邊？從上面這個(gè)指針數(shù)組里面就知道多邊形是從哪里開始的。在這個(gè)指針數(shù)組里只有1、2、3、5處有邊，因此當(dāng)從下往上進(jìn)行掃描轉(zhuǎn)換的時(shí)候，從y=1開始做，而在1這條線上有兩條邊進(jìn)來了，然后就把這兩條邊放進(jìn)活性邊表來處理。當(dāng)處理y=2這條掃描線時(shí)（活性邊里有2條邊），先看活性邊表里是否有邊要退出和加入，實(shí)際上p1p2邊要退出了（y=ymax），p1p6邊要加入了。退出的邊要從活性邊表里去掉，不退出的邊要進(jìn)行處理，即把x值加上一個(gè)增量。一個(gè)多邊形與若干掃描線即每做一次新的掃描線時(shí)，要對已有的邊進(jìn)行三個(gè)處理：一是否被去除掉；如果不被去除，第二就要對它的數(shù)據(jù)進(jìn)行更新，。所謂更新數(shù)據(jù)就是要更新它的x值，即x+△x；最后，就是有沒有新的邊進(jìn)來，新的邊在NET里，可以插入排序插進(jìn)來。這個(gè)算法過程從來沒有求交，這套數(shù)據(jù)結(jié)構(gòu)使得你不用求交點(diǎn)！避免了求交運(yùn)算。voidpolyfill(polygon,color)intcolor;多邊形polygon;{for(各條掃描線i)

{

初始化新邊表頭指針NET[i]；把ymin=i的邊放進(jìn)邊表NET[i];

}y=最低掃描線號；初始化活性邊表AET為空；

for(各條掃描線i)

{

把新邊表NET[i]中的邊結(jié)點(diǎn)用插入排序法插入AET表，使之按x坐標(biāo)遞增順序排列；遍歷AET表，把配對交點(diǎn)區(qū)間(左閉右開)上的象素(x,y)，用putpixel(x,y,color)改寫象素顏色值；遍歷AET表，把ymax=i的結(jié)點(diǎn)從AET表中刪除，并把ymax>i結(jié)點(diǎn)的x值遞增x；若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；

}}/*polyfill*/3、邊緣填充算法其基本思想是按任意順序處理多邊形的每條邊。在處理每條邊時(shí)，首先求出該邊與掃描線的交點(diǎn)，然后將每一條掃描線上交點(diǎn)右方的所有像素取補(bǔ)。多邊形的所有邊處理完畢之后，填充即完成。逐邊向右取右右右右邊緣填充算法缺點(diǎn)：每一個(gè)象素可能被訪問多次引入柵欄，以減少填充算法訪問象素的次數(shù)。柵欄：與掃描線垂直的直線，通常過一頂點(diǎn)，且把多邊形分為左右二半?；舅枷耄簰呙杈€與多邊形的邊求交，將交點(diǎn)與柵欄之間的象素取補(bǔ)。若交點(diǎn)位于柵欄左邊，則將交點(diǎn)之右，柵欄之左的所有象素取補(bǔ)；若交點(diǎn)位于柵欄右邊，則將交點(diǎn)之左，柵欄之右的所有象素取補(bǔ)。減少了象素重復(fù)訪問數(shù)目，但不徹底。柵欄填充算法6、邊界標(biāo)志算法基本思想：幀緩沖器中對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的象素打上標(biāo)志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個(gè)區(qū)段著上所需顏色。使用一個(gè)布爾量inside來指示當(dāng)前點(diǎn)是否在多邊形內(nèi)的狀態(tài)。voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)//兩個(gè)交點(diǎn)之間的區(qū)域填充inside=!(inside);if(inside！=FALSE)putpixel(x,y,color);elsedrawpixel(x,y,background); }}用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級。小結(jié)掃描線法可以實(shí)現(xiàn)已知多邊形域邊界的填充，多邊形域可以是凹的、凸的、還可以是帶孔的。該填充算法是按掃描線的順序，計(jì)算掃描線與待填充區(qū)域的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。這里區(qū)間的端點(diǎn)通過計(jì)算掃描線與多邊形邊界的交點(diǎn)獲得。所以待填充區(qū)域的邊界線必須事先知道，因此它的缺點(diǎn)是無法實(shí)現(xiàn)對未知邊界的區(qū)域填充。二、區(qū)域填充

區(qū)域填充是指將區(qū)域內(nèi)的一點(diǎn)(常稱種子點(diǎn))賦予給定顏色,然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過程。它是光柵計(jì)算機(jī)圖形學(xué)中的一個(gè)基本操作，在交互式圖形設(shè)計(jì)、動(dòng)畫、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域有著廣泛的應(yīng)用。區(qū)域---指已經(jīng)表示成點(diǎn)陣形式的填充圖形，是象素的集合。在光柵圖形學(xué)中，區(qū)域指的是已經(jīng)表示成點(diǎn)陣形式的象素的集合。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。

內(nèi)點(diǎn)表示：枚舉出區(qū)域內(nèi)部的所有像素，內(nèi)部的所有像素著同一個(gè)顏色，邊界像素著與內(nèi)部像素不同的顏色。

邊界表示：枚舉出邊界上的所有像素，邊界上的所有像素著同一個(gè)顏色，內(nèi)部像素著與邊界像素不同的顏色。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。四個(gè)方向運(yùn)動(dòng)八個(gè)方向運(yùn)動(dòng)四連通區(qū)域八連通區(qū)域區(qū)域填充算法要求區(qū)域是連通的，因?yàn)橹挥性谶B通區(qū)域中，才可能將種子點(diǎn)的顏色擴(kuò)展到區(qū)域內(nèi)的其它點(diǎn)。4向連通區(qū)域指的是從區(qū)域上一點(diǎn)出發(fā)，可通過四個(gè)方向，即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意象素；即：任取區(qū)域內(nèi)兩點(diǎn)，在該區(qū)域內(nèi)，通過上、下、左、右四個(gè)方向的運(yùn)動(dòng)，這兩點(diǎn)相互可達(dá)。8向連通區(qū)域指的是從區(qū)域內(nèi)每一象素出發(fā)，可通過八個(gè)方向，即上、下、左、右、左上、右上、左下、右下這八個(gè)方向的移動(dòng)的組合來到達(dá)。即：任取區(qū)域內(nèi)兩點(diǎn)，通過水平、垂直、兩個(gè)對角線八個(gè)方向的運(yùn)動(dòng)，這兩點(diǎn)相互可達(dá)。四連通區(qū)域八連通區(qū)域種子填充1、簡單四連通種子填充算法種子填充算法的原理是：假設(shè)在多邊形區(qū)域內(nèi)部有一像素已知，由此出發(fā)找到區(qū)域內(nèi)的所有像素，用一定的顏色或灰度來填充。假設(shè)區(qū)域采用邊界定義，即區(qū)域邊界上所有像素均具有某個(gè)特定值，區(qū)域內(nèi)部所有像素均不取這一特定值，而邊界外的像素則可具有與邊界相同的值。考慮區(qū)域的四向連通，即從區(qū)域上一點(diǎn)出發(fā)，可通過四個(gè)方向，即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素。可以使用棧結(jié)構(gòu)來實(shí)現(xiàn)簡單的種子填充算法。算法原理如下：種子像素入棧，當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：（1）棧頂像素出棧；（2）將出棧像素置成要填充色；（3）按左、上、右、下順序檢查與棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界且未置成填充色，則把該像素入棧。種子像素入棧，棧非空時(shí)重復(fù)執(zhí)行如下三步：（1）棧頂像素出棧；（2）將出棧像素置成要填充色；（3）按左、上、右、下順序檢查與棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界且未置成填充色，則把該像素入棧。掃描線填充算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若?？談t結(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）步。上述算法對于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。掃描線算法分析（舉例分析）該算法也可以填充有孔區(qū)域。像素中的序號標(biāo)指它所在區(qū)段位于堆棧中的位置掃描線算法分析（舉例分析）掃描線算法分析（舉例分析）掃描線算法分析（舉例分析）2、掃描填充與區(qū)域填充區(qū)別基本思想不同多邊形掃描轉(zhuǎn)換是指將多邊形的頂點(diǎn)表示轉(zhuǎn)化為點(diǎn)陣表示；區(qū)域填充只改變區(qū)域的填充顏色，不改變區(qū)域表示方法。對邊界的要求不同多邊形掃描轉(zhuǎn)換的掃描算法只要求一條掃描線與多邊形邊界的交點(diǎn)個(gè)數(shù)為偶數(shù)，多邊形的邊界可以不封閉；在區(qū)域填充算法中，為了防止遞歸填充時(shí)跨越區(qū)域的邊界，要求：區(qū)域的邊界是封閉基于的條件不同在區(qū)域填充算法中，要求給定區(qū)域內(nèi)一點(diǎn)作為種子點(diǎn)，然后從這一點(diǎn)根據(jù)連通性將新的顏色擴(kuò)散到整個(gè)區(qū)域；掃描轉(zhuǎn)換多邊形是從多邊形的邊界(頂點(diǎn))信息出發(fā)，利用多種形式的連貫性進(jìn)行填充的。4、填充圖元屬性控制填充一個(gè)定義的區(qū)域的選擇包括:選擇實(shí)區(qū)域顏色或圖案填充方式;選擇某種顏色和圖案。取決于可用軟件包的能力;這些填充選擇可應(yīng)用于多邊形區(qū)域或用曲線邊界定