概述
填充算法是計算機算法的一種分類，是一個將指定不規則區域內部像素填充為填充色的過程，在計算機輔助設計和圖像處理等領域有廣泛套用。包括了注入填充區域算法、種子填充算法、掃描線填充算法、邊填充算法等。注入填充區域算法
注入填充算法(FloodFill Algorithm)用於內部定義區域，以改變整個區域的顏色屬性，它把區域內的原像素點值改變成另一種像素點值。算法3.2用於填充八連通的內部定義區域。算法中，read ¡ pixel(x; y)表示讀出像素點(x; y)像素點值。old-value為像素點的原值, new-value為將要填充的新值。[算法3.2] 注入填充區域算法。
Procedure flood-fill-8(x,y,old-value,new-value)
BEGIN
IF read-pixel(x,y)=old-value THEN
BEGIN
write-pixel(x,y,new-value)
flood-fill-8(x,y-1,old-value,new-value)
flood-fill-8(x,y+1,old-value,new-value)
flood-fill-8(x-1,y,old-value,new-value)
flood-fill-8(x+1,y,old-value,new-value)
flood-fill-8(x+1,y-1,old-value,new-value)
flood-fill-8(x+1,y+1,old-value,new-value)
flood-fill-8(x-1,y-1,old-value,new-value)
flood-fill-8(x-1,y+1,old-value,new-value)
END
ENDIF
END
此算法所採用的基本方法是首先確定(x; y)點的像素點是否在區域內尚未被訪問過的那一部分之中，也就是說，如果這個像素點的值是原始值old-value，則需要把它改為填充的值new-value，然後按八連通區域性質先後訪問其八個相鄰的像素點，當訪問其中每一個近鄰像素點時，都要進行遞歸調用。此算法通過在四個方向而不是八個方向上擴展，就可以用來填充一個內部定義的四連通式區域。這時程式只要有前面四個flood-fill-8(...)語句就可以了.
種子填充算法
種子填充算法又稱為邊界填充算法。其基本思想是：從多邊形區域的一個內點開始，由內向外用給定的顏色畫點直到邊界為止。如果邊界是以一種顏色指定的，則種子填充算法可逐個像素地處理直到遇到邊界顏色為止。種子填充算法常用四連通域和八連通域技術進行填充操作。
從區域內任意一點出發，通過上、下、左、右四個方向到達區域內的任意像素。用這種方法填充的區域就稱為四連通域；這種填充方法稱為四向連通算法。
從區域內任意一點出發，通過上、下、左、右、左上、左下、右上和右下八個方向到達區域內的任意像素。用這種方法填充的區域就稱為八連通域；這種填充方法稱為八向連通算法。
一般來說，八向連通算法可以填充四向連通區域，而四向連通算法有時不能填充八向連通區域。例如，八向連通填充算法能夠正確填充如圖2.4a所示的區域的內部，而四向連通填充算法只能完成如圖2.4b的部分填充。
圖2.4 四向連通填充算法
a) 連通域及其內點 b) 填充四連通域
四向連通填充算法：
a） 種子像素壓入棧中；
b） 如果棧為空，則轉e)；否則轉c)；
c） 彈出一個像素，並將該像素置成填充色；並判斷該像素相鄰的四連通像素是否為邊界色或已經置成多邊形的填充色，若不是，則將該像素壓入棧；
d） 轉b）；
e） 結束。
四向連通填充方法可以用遞歸函式實現如下：
算法2.3 四向連通遞歸填充算法：
void BoundaryFill4(int x, int y, long FilledColor, long BoundaryColor)
{
long CurrentColor;
CurrentColor = GetPixelColor(x,y);
if (CurrentColor != BoundaryColor && CurrentColor != FilledColor)
{
SetColor(FilledColor);
SetPixel (x,y);
BoundaryFill4(x+1, y, FilledColor, BoundaryColor);
BoundaryFill4(x-1, y, FilledColor, BoundaryColor);
BoundaryFill4(x, y+1, FilledColor, BoundaryColor);
BoundaryFill4(x, y-1, FilledColor, BoundaryColor);
}
}
上述算法的優點是非常簡單，缺點是需要大量棧空間來存儲相鄰的點。一個改進的方法就是：通過沿掃描線填充水平像素段，來處理四連通或八連通相鄰點，這樣就僅僅只需要將每個水平像素段的起始位置壓入棧，而不需要將當前位置周圍尚未處理的相鄰像素都壓入棧，從而可以節省大量的棧空間。
