填充演演算法

注入填充演演算法(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);

}

}

上述演演算法的優點是非常簡單，缺點是需要大量棧空間來存儲相鄰的點。一個改進的方法就是：通過沿掃描線填充水平像素段，來處理四連通或八連通相鄰點，這樣就僅僅只需要將每個水平像素段的起始位置壓入棧，而不需要將當前位置周圍尚未處理的相鄰像素都壓入棧，從而可以節省大量的棧空間。