引言

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

常用填充算法

填充算法有很多種，他們適合不同的場景津辩，效率也有所不同克婶，有逐點判斷算法、種子填充算法丹泉、掃描線種子填充算法和活性邊表算法情萤，其中掃描線種子填充算法是繪圖軟件常采用的，也是本文要介紹的摹恨。下面先簡要介紹下其它3種算法：

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

掃描線種子填充算法

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

繼續(xù)，下一步就應(yīng)該是像素點3出棧勒虾，搜索邊界[xl,xr]纺阔，填充區(qū)段，向上修然，向下笛钝，其中向上的時候發(fā)現(xiàn)整行都被填充過了，所以該行沒有新種子點入棧低零，而向下的時候發(fā)現(xiàn)4正好屬于內(nèi)點婆翔、在最右側(cè)拯杠、不超過xr掏婶，因此4入棧。下一步又是4出棧潭陪，同3的情況一樣雄妥，最后進行到下圖所示情況。

• 像素點入棧次序：應(yīng)該是先向上探索，還是先向下探索薇溃，新種子點入棧有沒有先后順序要求菌赖，答案是沒有，隨意沐序。
• 搜索時遇到內(nèi)部邊界：在向上琉用、向下探索時，很容易遇到內(nèi)部邊界策幼，比如上圖中的像素點1在向下探索時邑时，生成了像素點2和3，而他倆中間其實是隔了3個顏色為X的邊界像素點的特姐，這個時候直接跳過它們即可刁愿。
• 搜索時遇到內(nèi)部孔洞：有人這時可能要質(zhì)疑了，上面那種情況太特殊了到逊，是滿滿的邊界顏色铣口，要是遇到“空心”的情況怎么辦呢？比如2下面那一行觉壶？其實仔細想想脑题，這種情況根本不存在，因為任何一個孔洞铜靶，它必然會有一個臨界叔遂，這個臨界就是掃描線在初遇到它的時候，本身完整的一個區(qū)段會被劃分為左右區(qū)段（比如上圖紅色起點所在行的一整條掃描線争剿，在向下探索時被劃分成了2已艰、3所在的兩個區(qū)段），或左中右區(qū)段蚕苇，甚至更多子區(qū)段的那個邊界點哩掺，或邊界線，上面那種情況就是邊界線涩笤。而一旦被劃分成多個區(qū)段后嚼吞，[xl,xr]自然都會縮小，而算法對新種子點又有<=xr的限制蹬碧，因此根本不用去考慮舱禽。
• 填充起點不同：經(jīng)過測試，只要按照算法的限定和要求來執(zhí)行恩沽，用戶指定的填充起點不同對算法正確性毫無影響誊稚，只是掃描的次序會有不同。
  不難看出，掃描線填充算法中種子點入棧次數(shù)與掃描線條數(shù)相同里伯，較種子填充算法大大減少了堆棧操作绽昏，時空開銷均有降低，效率都較高俏脊。所以該算法是繪圖軟件中常常采用的全谤，非常高效。

算法描述

為了實現(xiàn)爷贫，我們進一步整理一下认然，把掃描線填充算法歸納為以下4個步驟實現(xiàn):

1. 初始化: 堆棧置空。將種子點(x, y) 入棧漫萄；
2. 出棧: 若椌碓保空則結(jié)束。否則取棧頂元素(x, y) , 以y 作為當(dāng)前掃描線腾务；
3. 填充并確定種子點所在區(qū)段: 從種子點(x, y) 出發(fā), 沿當(dāng)前掃描線向左毕骡、右兩個方向填充, 直到邊界。分別標(biāo)記區(qū)段的左岩瘦、右端點坐標(biāo)為xl和xr未巫；
4. 確定新的種子點: 在區(qū)間[xl,xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的像素启昧。若存在非邊界叙凡、未填充的像素, 則把每一區(qū)間的最右像素作為種子點壓入堆棧, 返回2。

填充效果

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

結(jié)語

本文只給出了該算法文字描述刹碾，但真正編程實現(xiàn)起來還是有很多細節(jié)需要注意燥撞，您可以去我的GitHub上下載FillAlgorithms，里面有上面所提到的算法實現(xiàn)教硫。注意：因為當(dāng)時需求所限叨吮，均是基于Android平臺實現(xiàn)的，但核心是用Java寫的瞬矩，只需要把Android SDK中的畫布、著色锋玲、畫線等相關(guān)方法轉(zhuǎn)換成JDK中的對應(yīng)方法即可景用。
另外，本章最開頭提到的“活性邊表算法”也是非常神奇的一個算法，這個算法稍微復(fù)雜一些伞插，所以本章也就不作詳述了割粮，如果您感興趣，可以在我的GitHub上找到“一種強魯棒性自適應(yīng)活性邊表算法”這篇論文媚污，上面不僅有基本算法的實現(xiàn)思路舀瓢，還有對該算法的改進實現(xiàn)，代碼包含在上面那個填充算法集合里面耗美。
“Android繪圖軟件開發(fā)”這個系列就這么多內(nèi)容啦京髓，主要對繪圖軟件的開發(fā)思路、技術(shù)框架商架、核心功能堰怨、難點功能進行了著重闡述，因為篇幅有限蛇摸，對于界面备图、交互以及額外功能等就不做闡述啦。本人水平有限赶袄，如果有哪里寫得不對懇請各路大神批評指正揽涮，又如果您看過該文之后有所啟發(fā)，那就歡迎您繼續(xù)關(guān)注我的博客哦~