一、引言
區(qū)域填充是指先將區(qū)域內(nèi)的一個(gè)像素 ，一般稱為種子點(diǎn)賦予給定的顏色和輝亮，然后將該顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過(guò)程。
二、已有的填充算法及缺點(diǎn)
1．掃描線法
掃描線法可以實(shí)現(xiàn)已知多邊形域邊界的填充，多邊形域可以是凹的、凸的、還可以是帶孔的。該填充方法是按掃描線的順序，計(jì)算掃描線與待填充區(qū)域的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。這里區(qū)間的端點(diǎn)通過(guò)計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。所以待填充區(qū)域的邊界線必須事先知道，因此它的缺點(diǎn)是無(wú)法實(shí)現(xiàn)對(duì)未知邊界的區(qū)域填充。
2．邊填充算法
邊填充的基本思想是：對(duì)于每一條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。對(duì)多邊形的每條邊作些處理，多邊形的順序隨意。該算法適用于具有幀緩沖器的圖形系統(tǒng)，按任意順序處理多邊形的邊。處理每條邊時(shí)，僅訪問(wèn)與該邊有交的掃描線上交點(diǎn)右方的像素。所有的邊都被處理之后，按掃描線順序讀出幀緩沖器的內(nèi)容，送入顯示設(shè)備。該算法的優(yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是對(duì)于復(fù)雜圖形，每一像素可能被訪問(wèn)多次，重要的是必須事先知道待填充多邊形的邊界，所以在填充未知邊界的區(qū)域時(shí)不適用。
3．遞歸算法
遞歸算法的優(yōu)點(diǎn)是編程實(shí)現(xiàn)時(shí)，語(yǔ)言簡(jiǎn)潔。但在VB6.0實(shí)際編程實(shí)現(xiàn)時(shí)，這種遞歸算法填充稍稍大一些的圖形就會(huì)出現(xiàn)堆棧溢出現(xiàn)象，據(jù)我們的實(shí)踐證明，遞歸算法只能連續(xù)遞歸深度在2090次左右，也就是說(shuō)，如果待填充的圖形大于二千多個(gè)像素那么堆棧溢出。下面給出八連通填充方法的VB程序?qū)崿F(xiàn)(四連通算法同理)。
Public Sub area(p, q As Integer)
If ((imagepixels(0, p, q) = red1) And (imagepixels(1, p, q) = green1) And (imagepixels(2, p, q) = blue1)) Then
imagepixels(0, p, q) = 0： imagepixels(2, p, q) = 0： imagepixels(1, p, q) = 0
Picture1.PSet (p, q), RGB(0, 0, 0)
Call area(p + 1, q)： Call area(p, q + 1)
Call area(p - 1, q)： Call area(p, q - 1)
Call area(p + 1, q + 1)： Call area(p + 1, q - 1)
Call area(p - 1, q + 1)： Call area(p - 1, q - 1)
Else: Exit Sub
End If
End Sub
三、 算法的基本思想
本算法采用兩個(gè)隊(duì)列（FIFO）filled和unfilled來(lái)實(shí)現(xiàn)區(qū)域填充。設(shè)計(jì)步驟如下：
1． 找出該區(qū)域內(nèi)部任意一點(diǎn)，作為填充種子。
2． 填充該點(diǎn),并把該點(diǎn)存入隊(duì)列filled。
3． 按逆時(shí)針，判斷該點(diǎn)的上、右、下、左鄰像素是否在filled隊(duì)列內(nèi)。如果在filled，說(shuō)明該相鄰點(diǎn)已填充，若不在filled隊(duì)列內(nèi)，則判斷該相鄰點(diǎn)在未填充隊(duì)列unfilled，如果不在則將該相鄰點(diǎn)存入unfilled。
4． 判斷未填充隊(duì)列是否為空，若不空，則從隊(duì)列unfilled中取出頭元素，轉(zhuǎn)向第三步。若為空則表示已完成所有像素填充，結(jié)束程序。
四、 程序?qū)崿F(xiàn)及說(shuō)明
本算法定義的隊(duì)列突破了遞歸算法中受堆�？臻g大小的限制的束縛，因?yàn)樗�直接占用�?nèi)存空間，與堆棧大小無(wú)關(guān)。以下源程序在Window 2000環(huán)境下用VB6.0編程實(shí)現(xiàn)。
建立如圖所示標(biāo)準(zhǔn)窗體并畫上控件-2個(gè)CommandButton控件和一個(gè)PictureBox控件,調(diào)整大小,并設(shè)置控件的屬性。
4.1 通用聲明
Dim Xx As Integer, Yy As Integer
Dim Array1(9000, 2), Array2(9000, 2) As Integer
4.2 采集
Private Sub Command1_Click()
Picture1.MousePointer = 2
End Sub
4.3 選取種子
Private Sub Picture1_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)
Xx = X '選擇并記錄種子點(diǎn)的位置
Yy = Y
End Sub
4.4 區(qū)域填充
Private Sub Command2_Click()
Dim i, j, k As Integer, BoundPoint1, BoundPoint2 As Integer
Dim Flag As Boolean, Pixel As Long
Dim Red, Green, Blue As Integer, Bound As Boolean
Flag = True '初始化
i = Xx: j = Yy: BoundPoint1 = 1
Array1(1, 1) = i
Array1(1, 2) = j
'搜索邊界點(diǎn)
Do While BoundPoint1 > 0
BoundPoint2 = 0
For k = 1 To BoundPoint1
i = Array1(k, 1)
j = Array1(k, 2)
'搜索右點(diǎn)
Pixel& = Picture1.Point(i, j + 1)
Call IsBound(Pixel&, Bound)
If Not Bound Then
BoundPoint2 = BoundPoint2 + 1
Array2(BoundPoint2, 1) = i
Array2(BoundPoint2, 2) = j + 1
Picture1.PSet (i, j + 1), RGB(255, 255, 255)
End If
'搜索左鄰點(diǎn)
Pixel& = Picture1.Point(i, j - 1)
Call IsBound(Pixel&, Bound)
If Not Bound Then
BoundPoint2 = BoundPoint2 + 1
Array2(BoundPoint2, 1) = i
Array2(BoundPoint2, 2) = j - 1
Picture1.PSet (i, j - 1), RGB(255, 255, 255)
End If
'搜索上鄰點(diǎn)
Pixel& = Picture1.Point(i - 1, j)
Call IsBound(Pixel&, Bound)
If Not Bound Then
BoundPoint2 = BoundPoint2 + 1
Array2(BoundPoint2, 1) = i - 1
Array2(BoundPoint2, 2) = j
Picture1.PSet (i - 1, j), RGB(255, 255, 255)
End If
'搜索下鄰點(diǎn)
Pixel& = Picture1.Point(i + 1, j)
Call IsBound(Pixel&, Bound)
If Not Bound Then
BoundPoint2 = BoundPoint2 + 1
Array2(BoundPoint2, 1) = i + 1
Array2(BoundPoint2, 2) = j
Picture1.PSet (i + 1, j), RGB(255, 255, 255)
End If
Next k
'數(shù)組array2 中的數(shù)據(jù)傳給array1
BoundPoint1 = BoundPoint2
For k = 1 To BoundPoint1
Array1(k, 1) = Array2(k, 1)
Array1(k, 2) = Array2(k, 2)
Next k
Picture1.Refresh
Loop
End Sub
Public Sub IsBound(P As Long, Bound As Boolean) '判斷P是否為邊界點(diǎn)
Red = P& Mod 256
Bound = False
Green = ((P& And &HFF00) / 256&) Mod 256&
Blue = (P& And &HFF0000) / 65536
If Red = 255 And Green = 255 And Blue = 255 Then
Bound = True
End If
End Sub
五、 結(jié)束語(yǔ)
本算法實(shí)現(xiàn)了在對(duì)填充區(qū)域的形狀、大小均未知的情況下，以種子點(diǎn)開(kāi)始向四周對(duì)該區(qū)域進(jìn)行“擴(kuò)散式”的填充。本算法解決了傳統(tǒng)的遞歸算法在填充較大區(qū)域時(shí)（本例中填充區(qū)約9800Pixels）堆棧溢出的缺點(diǎn)。我們的實(shí)驗(yàn)結(jié)果顯示，本算法就填充區(qū)域大小和運(yùn)算速度而言，都遠(yuǎn)遠(yuǎn)超過(guò)了傳統(tǒng)的遞歸算法。