1.3掃描線種子填充算法

1.1和1.2節(jié)介紹的兩種種子填充算法的優(yōu)點(diǎn)是非常簡(jiǎn)單，缺點(diǎn)是使用了遞歸算法，這不但需要大量?？臻g來(lái)存儲(chǔ)相鄰的點(diǎn)，而且效率不高。為了減少算法中的遞歸調(diào)用，節(jié)省?？臻g的使用，人們提出了很多改進(jìn)算法，其中一種就是掃描線種子填充算法。掃描線種子填充算法不再采用遞歸的方式處理“4-聯(lián)通”和“8-聯(lián)通”的相鄰點(diǎn)，而是通過(guò)沿水平掃描線填充像素段，一段一段地來(lái)處理“4-聯(lián)通”和“8-聯(lián)通”的相鄰點(diǎn)。這樣算法處理過(guò)程中就只需要將每個(gè)水平像素段的起始點(diǎn)位置壓入一個(gè)特殊的棧，而不需要象遞歸算法那樣將當(dāng)前位置周?chē)形刺幚淼乃邢噜忺c(diǎn)都?jí)喝攵褩?，從而可以?jié)省堆?？臻g。應(yīng)該說(shuō)，掃描線填充算法只是一種避免遞歸，提高效率的思想，前面提到的注入填充算法和邊界填充算法都可以改進(jìn)成掃描線填充算法，下面介紹的就是結(jié)合了邊界填充算法的掃描線種子填充算法。

掃描線種子填充算法的基本過(guò)程如下：當(dāng)給定種子點(diǎn)(x, y)時(shí)，首先分別向左和向右兩個(gè)方向填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，同時(shí)記下這個(gè)區(qū)段的范圍[xLeft, xRight]，然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。

掃描線種子填充算法可由下列四個(gè)步驟實(shí)現(xiàn)：

(1) 初始化一個(gè)空的棧用于存放種子點(diǎn)，將種子點(diǎn)(x, y)入棧；

(2) 判斷棧是否為空，如果棧為空則結(jié)束算法，否則取出棧頂元素作為當(dāng)前掃描線的種子點(diǎn)(x, y)，y是當(dāng)前的掃描線；

(3) 從種子點(diǎn)(x, y)出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xLeft和xRight；

(4) 分別檢查與當(dāng)前掃描線相鄰的y - 1和y + 1兩條掃描線在區(qū)間[xLeft, xRight]中的像素，從xLeft開(kāi)始向xRight方向搜索，若存在非邊界且未填充的像素點(diǎn)，則找出這些相鄰的像素點(diǎn)中最右邊的一個(gè)，并將其作為種子點(diǎn)壓入棧中，然后返回第（2）步；

這個(gè)算法中最關(guān)鍵的是第（4）步，就是從當(dāng)前掃描線的上一條掃描線和下一條掃描線中尋找新的種子點(diǎn)。這里比較難理解的一點(diǎn)就是為什么只是檢查新掃描線上區(qū)間[xLeft, xRight]中的像素？如果新掃描線的實(shí)際范圍比這個(gè)區(qū)間大（而且不連續(xù)）怎么處理？我查了很多計(jì)算機(jī)圖形學(xué)的書(shū)籍和論文，好像都沒(méi)有對(duì)此做過(guò)特殊說(shuō)明，這使得很多人在學(xué)習(xí)這門(mén)課程時(shí)對(duì)此有揮之不去的疑惑。本著“毀人”不倦的思想，本文就羅嗦解釋一下，希望能解除大家的疑惑。

如果新掃描線上實(shí)際點(diǎn)的區(qū)間比當(dāng)前掃描線的[xLeft, xRight]區(qū)間大，而且是連續(xù)的情況下，算法的第（3）步就處理了這種情況。如圖（4）所示：

圖（4） 新掃描線區(qū)間增大且連續(xù)的情況

假設(shè)當(dāng)前處理的掃描線是黃色點(diǎn)所在的第7行，則經(jīng)過(guò)第3步處理后可以得到一個(gè)區(qū)間[6,10]。然后第4步操作，從相鄰的第6行和第8行兩條掃描線的第6列開(kāi)始向右搜索，確定紅色的兩個(gè)點(diǎn)分別是第6行和第8行的種子點(diǎn)，于是按照順序?qū)ⅲ?, 10）和（8, 10）兩個(gè)種子點(diǎn)入棧。接下來(lái)的循環(huán)會(huì)處理（8, 10）這個(gè)種子點(diǎn)，根據(jù)算法第3步說(shuō)明，會(huì)從（8, 10）開(kāi)始向左和向右填充，由于中間沒(méi)有邊界點(diǎn)，因此填充會(huì)直到遇到邊界為止，所以盡管第8行實(shí)際區(qū)域比第7行的區(qū)間[6,10]大，但是仍然得到了正確的填充。

 如果新掃描線上實(shí)際點(diǎn)的區(qū)間比當(dāng)前掃描線的[xLeft, xRight]區(qū)間大，而且中間有邊界點(diǎn)的情況，算法又是怎么處理呢？算法描述中雖然沒(méi)有明確對(duì)這種情況的處理方法，但是第4步確定上、下相鄰掃描線的種子點(diǎn)的方法，以及靠右取點(diǎn)的原則，實(shí)際上暗含了從相鄰掃描線繞過(guò)障礙點(diǎn)的方法。下面以圖（5）為例說(shuō)明：

圖（5） 新掃描線區(qū)間增大且不連續(xù)的情況

算法第3步處理完第5行后，確定了區(qū)間[7, 9]，相鄰的第4行雖然實(shí)際范圍比區(qū)間[7, 9]大，但是因?yàn)楸唬?, 6）這個(gè)邊界點(diǎn)阻礙，使得在確定種子點(diǎn)（4, 9）后向左填充只能填充右邊的第7列到第10列之間的區(qū)域，而左邊的第3列到第5列之間的區(qū)域沒(méi)有填充。雖然作為第5行的相鄰行，第一次對(duì)第4行的掃描根據(jù)靠右原則只確定了（4, 9）一個(gè)種子點(diǎn)。但是對(duì)第3行處理完后，第4行的左邊部分作為第3行下邊的相鄰行，再次得到掃描的機(jī)會(huì)。第3行的區(qū)間是[3, 9]，向左跨過(guò)了第6列這個(gè)障礙點(diǎn)，第2次掃描第4行的時(shí)候就從第3列開(kāi)始，向右找，可以確定種子點(diǎn)（4, 5）。這樣第4行就有了兩個(gè)種子點(diǎn)，就可以被完整地填充了。

 由此可見(jiàn)，對(duì)于有障礙點(diǎn)的行，通過(guò)相鄰邊的關(guān)系，可以跨越障礙點(diǎn)，通過(guò)多次掃描得到完整的填充，算法已經(jīng)隱含了對(duì)這種情況的處理。根據(jù)本節(jié)總結(jié)的四個(gè)步驟，掃描線種子填充算法的實(shí)現(xiàn)如下：

void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
 int y, int new_color, int boundary_color)
 {
 int xt = xLeft;
 bool findNewSeed = false; 
 while(xt <= xRight)
 {
 findNewSeed = false;

 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
 {
 findNewSeed = true;
 xt++;
 }
 if(findNewSeed)
 {
 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))

 stk.push(Point(xt, y));
 else
 stk.push(Point(xt - 1, y));
 }
 
 /*向右跳過(guò)內(nèi)部的無(wú)效點(diǎn)（處理區(qū)間右端有障礙點(diǎn)的情況）*/
 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
 xt += (xspan == 0) ? 1 : xspan;
 /*處理特殊情況,以退出while(x<=xright)循環(huán)*/
 }
}

FillLineRight()和FillLineLeft()兩個(gè)函數(shù)就是從種子點(diǎn)分別向右和向左填充顏色，直到遇到邊界點(diǎn)，同時(shí)返回填充的點(diǎn)的個(gè)數(shù)。這兩個(gè)函數(shù)返回填充點(diǎn)的個(gè)數(shù)是為了正確調(diào)整當(dāng)前種子點(diǎn)所在的掃描線的區(qū)間[xLeft, xRight]。

SearchLineNewSeed()函數(shù)完成算法第4步所描述的操作，就是在新掃描線上尋找種子點(diǎn)，并將種子點(diǎn)入棧，新掃描線的區(qū)間是xLeft和xRight參數(shù)確定的：

void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
 int y, int new_color, int boundary_color)
 {
 int xt = xLeft;
 bool findNewSeed = false; 
 while(xt <= xRight)
 {
 findNewSeed = false;

 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
 {
 findNewSeed = true;
 xt++;
 }
 if(findNewSeed)
 {
 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))

 stk.push(Point(xt, y));
 else
 stk.push(Point(xt - 1, y));
 }
 
 /*向右跳過(guò)內(nèi)部的無(wú)效點(diǎn)（處理區(qū)間右端有障礙點(diǎn)的情況）*/
 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
 xt += (xspan == 0) ? 1 : xspan;
 /*處理特殊情況,以退出while(x<=xright)循環(huán)*/
 }
}

最外層的while循環(huán)是為了保證區(qū)間[xLeft, xRight]右端被障礙點(diǎn)分隔成多段的情況能夠得到正確處理，通過(guò)外層while循環(huán)，可以確保為每一段都找到一個(gè)種子點(diǎn)（對(duì)于障礙點(diǎn)在區(qū)間左端的情況，請(qǐng)參考圖（5）所示實(shí)例的解釋?zhuān)请[含在算法中完成的）。內(nèi)層的while循環(huán)只是為了找到每一段最右端的一個(gè)可填充點(diǎn)作為種子點(diǎn)。SkipInvalidInLine()函數(shù)的作用就是跳過(guò)區(qū)間內(nèi)的障礙點(diǎn)，確定下一個(gè)分隔段的開(kāi)始位置。循環(huán)內(nèi)的最后一行代碼有點(diǎn)奇怪，其實(shí)只是用了一個(gè)小“詭計(jì)”，確保在遇到真正的邊界點(diǎn)時(shí)循環(huán)能夠正確退出。這不是一個(gè)值得稱(chēng)道的做法，實(shí)現(xiàn)此類(lèi)軟件控制有更好的方法，本文這樣做的目的只是為了使代碼簡(jiǎn)短一些，讓讀者把注意力集中在算法處理邏輯上，而不是冗雜難懂的循環(huán)控制條件上。

算法的實(shí)現(xiàn)其實(shí)就在ScanLineSeedFill()和SearchLineNewSeed()兩個(gè)函數(shù)中，神秘的掃描線種子填充算法也并不復(fù)雜，對(duì)吧？至此，種子填充算法的幾種常見(jiàn)算法都已經(jīng)介紹完畢，接下來(lái)將介紹兩種適合矢量圖形區(qū)域填充的填充算法，分別是掃描線算法和邊標(biāo)志填充算法，注意適合矢量圖形的掃描線填充算法有時(shí)又被稱(chēng)為“有序邊表法”，和掃描線種子填充算法是有區(qū)別的。