1.3掃描線種子填充算法
1.1和1.2節介紹的兩種種子填充算法的優點是非常簡單，缺點是使用了遞歸算法，這不但需要大量棧空間來存儲相鄰的點，而且效率不高。為了減少算法中的遞歸調用，節省棧空間的使用，人們提出了很多改進算法，其中一種就是掃描線種子填充算法。掃描線種子填充算法不再采用遞歸的方式處理“4-聯通”和“8-聯通”的相鄰點，而是通過沿水準掃描線填充像素段，一段一段地來處理“4-聯通”和“8-聯通”的相鄰點。這樣算法處理過程中就隻需要将每個水準像素段的起始點位置壓入一個特殊的棧，而不需要象遞歸算法那樣将目前位置周圍尚未處理的所有相鄰點都壓入堆棧，進而可以節省堆棧空間。應該說，掃描線填充算法隻是一種避免遞歸，提高效率的思想，前面提到的注入填充算法和邊界填充算法都可以改進成掃描線填充算法，下面介紹的就是結合了邊界填充算法的掃描線種子填充算法。
掃描線種子填充算法的基本過程如下：當給定種子點(x, y)時，首先分别向左和向右兩個方向填充種子點所在掃描線上的位于給定區域的一個區段，同時記下這個區段的範圍[xLeft, xRight]，然後确定與這一區段相連通的上、下兩條掃描線上位于給定區域内的區段，并依次儲存下來。反複這個過程，直到填充結束。
掃描線種子填充算法可由下列四個步驟實作：
(1) 初始化一個空的棧用于存放種子點，将種子點(x, y)入棧；
(2) 判斷棧是否為空，如果棧為空則結束算法，否則取出棧頂元素作為目前掃描線的種子點(x, y)，y是目前的掃描線；
(3) 從種子點(x, y)出發，沿目前掃描線向左、右兩個方向填充，直到邊界。分别标記區段的左、右端點坐标為xLeft和xRight；
(4) 分别檢查與目前掃描線相鄰的y - 1和y + 1兩條掃描線在區間[xLeft, xRight]中的像素，從xLeft開始向xRight方向搜尋，若存在非邊界且未填充的像素點，則找出這些相鄰的像素點中最右邊的一個，并将其作為種子點壓入棧中，然後傳回第（2）步；
這個算法中最關鍵的是第（4）步，就是從目前掃描線的上一條掃描線和下一條掃描線中尋找新的種子點。這裡比較難了解的一點就是為什麼隻是檢查新掃描線上區間[xLeft, xRight]中的像素？如果新掃描線的實際範圍比這個區間大（而且不連續）怎麼處理？我查了很多計算機圖形學的書籍和論文，好像都沒有對此做過特殊說明，這使得很多人在學習這門課程時對此有揮之不去的疑惑。本着“毀人”不倦的思想，本文就羅嗦解釋一下，希望能解除大家的疑惑。
如果新掃描線上實際點的區間比目前掃描線的[xLeft, xRight]區間大，而且是連續的情況下，算法的第（3）步就處理了這種情況。如圖（4）所示：
圖（4） 新掃描線區間增大且連續的情況
假設目前處理的掃描線是黃色點所在的第7行，則經過第3步處理後可以得到一個區間[6,10]。然後第4步操作，從相鄰的第6行和第8行兩條掃描線的第6列開始向右搜尋，确定紅色的兩個點分别是第6行和第8行的種子點，于是按照順序将（6, 10）和（8, 10）兩個種子點入棧。接下來的循環會處理（8, 10）這個種子點，根據算法第3步說明，會從（8, 10）開始向左和向右填充，由于中間沒有邊界點，是以填充會直到遇到邊界為止，是以盡管第8行實際區域比第7行的區間[6,10]大，但是仍然得到了正确的填充。
如果新掃描線上實際點的區間比目前掃描線的[xLeft, xRight]區間大，而且中間有邊界點的情況，算法又是怎麼處理呢？算法描述中雖然沒有明确對這種情況的處理方法，但是第4步确定上、下相鄰掃描線的種子點的方法，以及靠右取點的原則，實際上暗含了從相鄰掃描線繞過障礙點的方法。下面以圖（5）為例說明：
圖（5） 新掃描線區間增大且不連續的情況
算法第3步處理完第5行後，确定了區間[7, 9]，相鄰的第4行雖然實際範圍比區間[7, 9]大，但是因為被（4, 6）這個邊界點阻礙，使得在确定種子點（4, 9）後向左填充隻能填充右邊的第7列到第10列之間的區域，而左邊的第3列到第5列之間的區域沒有填充。雖然作為第5行的相鄰行，第一次對第4行的掃描根據靠右原則隻确定了（4, 9）一個種子點。但是對第3行處理完後，第4行的左邊部分作為第3行下邊的相鄰行，再次得到掃描的機會。第3行的區間是[3, 9]，向左跨過了第6列這個障礙點，第2次掃描第4行的時候就從第3列開始，向右找，可以确定種子點（4, 5）。這樣第4行就有了兩個種子點，就可以被完整地填充了。
由此可見，對于有障礙點的行，通過相鄰邊的關系，可以跨越障礙點，通過多次掃描得到完整的填充，算法已經隐含了對這種情況的處理。根據本節總結的四個步驟，掃描線種子填充算法的實作如下：
| 263 void ScanLineSeedFill(int x, int y, int new_color, int boundary_color) 264 { 265 std::stack<Point> stk; 266 267 stk.push(Point(x, y)); //第1步，種子點入站 268 while(!stk.empty()) 269 { 270 Point seed = stk.top(); //第2步，取目前種子點 271 stk.pop(); 272 273 //第3步，向左右填充 274 int count = FillLineRight(seed.x, seed.y, new_color, boundary_color);//向'cf?右'd3?填'cc?充'b3? 275 int xRight = seed.x + count - 1; 276 count = FillLineLeft(seed.x - 1, seed.y, new_color, boundary_color);//向'cf?左'd7?填'cc?充'b3? 277 int xLeft = seed.x - count; 278 279 //第4步，處理相鄰兩條掃描線 280 SearchLineNewSeed(stk, xLeft, xRight, seed.y - 1, new_color, boundary_color); 281 SearchLineNewSeed(stk, xLeft, xRight, seed.y + 1, new_color, boundary_color); 282 } 283 } |
FillLineRight()和FillLineLeft()兩個函數就是從種子點分别向右和向左填充顔色，直到遇到邊界點，同時傳回填充的點的個數。這兩個函數傳回填充點的個數是為了正确調整目前種子點所在的掃描線的區間[xLeft, xRight]。SearchLineNewSeed()函數完成算法第4步所描述的操作，就是在新掃描線上尋找種子點，并将種子點入棧，新掃描線的區間是xLeft和xRight參數确定的：
| 234 void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight, 235 int y, int new_color, int boundary_color) 236 { 237 int xt = xLeft; 238 bool findNewSeed = false; 239 240 while(xt <= xRight) 241 { 242 findNewSeed = false; 243 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight)) 244 { 245 findNewSeed = true; 246 xt++; 247 } 248 if(findNewSeed) 249 { 250 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight)) 251 stk.push(Point(xt, y)); 252 else 253 stk.push(Point(xt - 1, y)); 254 } 255 256 257 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color); 258 xt += (xspan == 0) ? 1 : xspan; 259 260 } 261 } |
最外層的while循環是為了保證區間[xLeft, xRight]右端被障礙點分隔成多段的情況能夠得到正确處理，通過外層while循環，可以確定為每一段都找到一個種子點（對于障礙點在區間左端的情況，請參考圖（5）所示執行個體的解釋，是隐含在算法中完成的）。内層的while循環隻是為了找到每一段最右端的一個可填充點作為種子點。SkipInvalidInLine()函數的作用就是跳過區間内的障礙點，确定下一個分隔段的開始位置。循環内的最後一行代碼有點奇怪，其實隻是用了一個小“詭計”，確定在遇到真正的邊界點時循環能夠正确退出。這不是一個值得稱道的做法，實作此類軟體控制有更好的方法，本文這樣做的目的隻是為了使代碼簡短一些，讓讀者把注意力集中在算法處理邏輯上，而不是冗雜難懂的循環控制條件上。
算法的實作其實就在ScanLineSeedFill()和SearchLineNewSeed()兩個函數中，神秘的掃描線種子填充算法也并不複雜，對吧？至此，種子填充算法的幾種常見算法都已經介紹完畢，接下來将介紹兩種适合矢量圖形區域填充的填充算法，分别是掃描線算法和邊标志填充算法，注意适合矢量圖形的掃描線填充算法有時又被稱為“有序邊表法”，和掃描線種子填充算法是有差別的。
<下一篇：掃描線算法（有序邊表法）>