填充算法是計算機算法的一種分類，是一個將指定不規則區域內部像素填充為填充色的過程，在計算機輔助設計和圖像處理等領域有廣泛應用。包括了種子填充算法、掃描綫填充算法、邊填充算法等。
種子填充算法
種子填充算法又稱為邊界填充算法。其基本思想是：從多邊形區域的一個內點開始，由內嚮外用給定的顔色畫點直到邊界為止。如果邊界是以一種顔色指定的，則種子填充算法可逐個像素地處理直到遇到邊界顔色為止。
種子填充算法常用四連通域和八連通域技術進行填充操作。
從區域內任意一點出發，通過上、下、左、右四個方向到達區域內的任意像素。用這種方法填充的區域就稱為四連通域；這種填充方法稱為四嚮連通算法。
從區域內任意一點出發，通過上、下、左、右、左上、左下、右上和右下八個方向到達區域內的任意像素。用這種方法填充的區域就稱為八連通域；這種填充方法稱為八嚮連通算法。
一般來說，八嚮連通算法可以填充四嚮連通區域，而四嚮連通算法有時不能填充八嚮連通區域。例如，八嚮連通填充算法能夠正確填充如圖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);
}
}
上述算法的優點是非常簡單，缺點是需要大量棧空間來存儲相鄰的點。一個改進的方法就是：通過沿掃描綫填充水平像素段，來處理四連通或八連通相鄰點，這樣就僅僅衹需要將每個水平像素段的起始位置壓入棧，而不需要將當前位置周圍尚未處理的相鄰像素都壓入棧，從而可以節省大量的棧空間。 |