引言

填充，是繪圖軟件極為重要的一個(gè)功能。用戶通過點(diǎn)擊某空白區(qū)域內(nèi)任一點(diǎn)，即可為該區(qū)域著色，系統(tǒng)能自動(dòng)識(shí)別邊界線，最后停止填充。本章我們就講解下填充算法的實(shí)現(xiàn)思路。

常用填充算法

填充算法有很多種，他們適合不同的場(chǎng)景，效率也有所不同，有逐點(diǎn)判斷算法、種子填充算法、掃描線種子填充算法和活性邊表算法，其中掃描線種子填充算法是繪圖軟件常采用的，也是本文要介紹的。下面先簡(jiǎn)要介紹下其它3種算法：

• 逐點(diǎn)判斷算法：該算法對(duì)繪圖窗口內(nèi)每一像素點(diǎn)進(jìn)行射線環(huán)繞探測(cè)來實(shí)現(xiàn)內(nèi)點(diǎn)判定，孤立地考慮像素點(diǎn)與區(qū)域間的關(guān)系，計(jì)算量較大，一般不采用。
• 種子填充算法：該算法事先給定一像素點(diǎn)作為種子點(diǎn)，再以該種子點(diǎn)為起點(diǎn)朝四連通或八連通方向遞歸填充，如下圖所示，左邊為四連通填充效果，右邊為八連通填充效果。但這種算法它仍基于像素，且區(qū)域內(nèi)每一像素點(diǎn)均需入棧，易堆棧溢出，所以一般也不采用。
  
• 活性邊表算法：該算法充分挖掘了邊的連貫性和頂點(diǎn)間的約束關(guān)系，通過掃描線自下而上掃描圖形，并利用相交邊的斜率關(guān)系快速定位下次掃描的邊界點(diǎn)，進(jìn)而實(shí)現(xiàn)快速填充，如下圖所示。該算法在速度上比其它算法都快，但弊端是需要事先將圖形近似化成多邊形，并存儲(chǔ)關(guān)鍵點(diǎn)的坐標(biāo)數(shù)據(jù)，且不能由用戶指定填充內(nèi)點(diǎn)，自由度很低。故繪圖軟件中往往也不采用。
  

掃描線種子填充算法

先大致說下這個(gè)算法的主要思想，好有一個(gè)直觀的感受：該算法需事先指定一個(gè)種子點(diǎn)，然后分別水平向右和向左地探測(cè)得到圖形邊界點(diǎn)，填充兩端點(diǎn)之間的線段（邊界為[xl,xr]），并讓該線段之上和之下的不超過xr的最右側(cè)內(nèi)點(diǎn)入棧，繼而棧頂像素點(diǎn)出棧作為新的種子點(diǎn)，重復(fù)上述操作至?？?。
現(xiàn)在，假設(shè)我們要在下面的繪圖空間內(nèi)，填充邊界顏色為X的區(qū)域，紅色是用戶點(diǎn)擊的填充起點(diǎn)，陰影是填充后的顏色。那么按照上面所述思路，第一個(gè)種子點(diǎn)分別向左、向右找到邊界，然后填充該區(qū)段后的效果就應(yīng)該如下圖所示。不僅填充了該區(qū)段，還把與自己向上緊鄰的1像素、向下緊鄰的1像素所在區(qū)段不超過xr的最右側(cè)內(nèi)點(diǎn)坐標(biāo)壓入了棧中。

繼續(xù)，下一步就應(yīng)該是像素點(diǎn)3出棧，搜索邊界[xl,xr]，填充區(qū)段，向上，向下，其中向上的時(shí)候發(fā)現(xiàn)整行都被填充過了，所以該行沒有新種子點(diǎn)入棧，而向下的時(shí)候發(fā)現(xiàn)4正好屬于內(nèi)點(diǎn)、在最右側(cè)、不超過xr，因此4入棧。下一步又是4出棧，同3的情況一樣，最后進(jìn)行到下圖所示情況。

• 像素點(diǎn)入棧次序：應(yīng)該是先向上探索，還是先向下探索，新種子點(diǎn)入棧有沒有先后順序要求，答案是沒有，隨意。
• 搜索時(shí)遇到內(nèi)部邊界：在向上、向下探索時(shí)，很容易遇到內(nèi)部邊界，比如上圖中的像素點(diǎn)1在向下探索時(shí)，生成了像素點(diǎn)2和3，而他倆中間其實(shí)是隔了3個(gè)顏色為X的邊界像素點(diǎn)的，這個(gè)時(shí)候直接跳過它們即可。
• 搜索時(shí)遇到內(nèi)部孔洞：有人這時(shí)可能要質(zhì)疑了，上面那種情況太特殊了，是滿滿的邊界顏色，要是遇到“空心”的情況怎么辦呢？比如2下面那一行？其實(shí)仔細(xì)想想，這種情況根本不存在，因?yàn)槿魏我粋€(gè)孔洞，它必然會(huì)有一個(gè)臨界，這個(gè)臨界就是掃描線在初遇到它的時(shí)候，本身完整的一個(gè)區(qū)段會(huì)被劃分為左右區(qū)段（比如上圖紅色起點(diǎn)所在行的一整條掃描線，在向下探索時(shí)被劃分成了2、3所在的兩個(gè)區(qū)段），或左中右區(qū)段，甚至更多子區(qū)段的那個(gè)邊界點(diǎn)，或邊界線，上面那種情況就是邊界線。而一旦被劃分成多個(gè)區(qū)段后，[xl,xr]自然都會(huì)縮小，而算法對(duì)新種子點(diǎn)又有<=xr的限制，因此根本不用去考慮。
• 填充起點(diǎn)不同：經(jīng)過測(cè)試，只要按照算法的限定和要求來執(zhí)行，用戶指定的填充起點(diǎn)不同對(duì)算法正確性毫無影響，只是掃描的次序會(huì)有不同。
  不難看出，掃描線填充算法中種子點(diǎn)入棧次數(shù)與掃描線條數(shù)相同，較種子填充算法大大減少了堆棧操作，時(shí)空開銷均有降低，效率都較高。所以該算法是繪圖軟件中常常采用的，非常高效。

算法描述

為了實(shí)現(xiàn)，我們進(jìn)一步整理一下，把掃描線填充算法歸納為以下4個(gè)步驟實(shí)現(xiàn):

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。

填充效果

我們導(dǎo)入了一些較為復(fù)雜的圖形進(jìn)行填充測(cè)試，得到如下的效果。第一幅圖的時(shí)間只用了1秒左右，事實(shí)證明該算法不僅正確，而且非常高效，給用戶的自由度也很高。

結(jié)語

本文只給出了該算法文字描述，但真正編程實(shí)現(xiàn)起來還是有很多細(xì)節(jié)需要注意，您可以去我的GitHub上下載FillAlgorithms，里面有上面所提到的算法實(shí)現(xiàn)。注意：因?yàn)楫?dāng)時(shí)需求所限，均是基于Android平臺(tái)實(shí)現(xiàn)的，但核心是用Java寫的，只需要把Android SDK中的畫布、著色、畫線等相關(guān)方法轉(zhuǎn)換成JDK中的對(duì)應(yīng)方法即可。
另外，本章最開頭提到的“活性邊表算法”也是非常神奇的一個(gè)算法，這個(gè)算法稍微復(fù)雜一些，所以本章也就不作詳述了，如果您感興趣，可以在我的GitHub上找到“一種強(qiáng)魯棒性自適應(yīng)活性邊表算法”這篇論文，上面不僅有基本算法的實(shí)現(xiàn)思路，還有對(duì)該算法的改進(jìn)實(shí)現(xiàn)，代碼包含在上面那個(gè)填充算法集合里面。
“Android繪圖軟件開發(fā)”這個(gè)系列就這么多內(nèi)容啦，主要對(duì)繪圖軟件的開發(fā)思路、技術(shù)框架、核心功能、難點(diǎn)功能進(jìn)行了著重闡述，因?yàn)槠邢?，?duì)于界面、交互以及額外功能等就不做闡述啦。本人水平有限，如果有哪里寫得不對(duì)懇請(qǐng)各路大神批評(píng)指正，又如果您看過該文之后有所啟發(fā)，那就歡迎您繼續(xù)關(guān)注我的博客哦~