種子填充算法
種子填充算法又稱為邊界填充算法。其基本思想是:從多邊形區域的一個内點開始,由内向外用給定的顔色畫點直到邊界為止。如果邊界是以一種顔色指定的,則種子填充算法可逐個像素地處理直到遇到邊界顔色為止。
種子填充算法常用四連通域和八連通域技術進行填充操作。
從區域内任意一點出發,通過上、下、左、右四個方向到達區域内的任意像素。用這種方法填充的區域就稱為四連通域;這種填充方法稱為四向連通算法。
從區域内任意一點出發,通過上、下、左、右、左上、左下、右上和右下八個方向到達區域内的任意像素。用這種方法填充的區域就稱為八連通域;這種填充方法稱為八向連通算法。
一般來說,八向連通算法可以填充四向連通區域,而四向連通算法有時不能填充八向連通區域。例如,八向連通填充算法能夠正确填充如圖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);
}
}
上述算法的優點是非常簡單,缺點是需要大量棧空間來存儲相鄰的點。一個改進的方法就是:通過沿掃描線填充水準像素段,來處理四連通或八連通相鄰點,這樣就僅僅隻需要将每個水準像素段的起始位置壓入棧,而不需要将目前位置周圍尚未處理的相鄰像素都壓入棧,進而可以節省大量的棧空間。
以上原文引自: http://comic.sjtu.edu.cn/thucs/GD_jsj_027y/text/chapter2/section5/part01/l1_bq2.htm#2
====================================J2ME模拟================================
public class FillAlgorithm {
private int[] RGBdata;
private int imgW;
private int imgH;
public FillAlgorithm(Image img){
imgW = img.getWidth();
imgH = img.getHeight();
RGBdata = new int[imgW*imgH];
img.getRGB(RGBdata, 0, imgW, 0, 0, imgW, imgH);
}
public void BoundaryFill4(int x, int y, int FilledColor, int BoundaryColor){
int CurrentColor;
CurrentColor = GetPixelColor(x,y);
if (CurrentColor != BoundaryColor && CurrentColor != FilledColor)
{
SetPixelColor(x,y,FilledColor);
BoundaryFill4(x+1, y, FilledColor, BoundaryColor);
BoundaryFill4(x-1, y, FilledColor, BoundaryColor);
BoundaryFill4(x, y+1, FilledColor, BoundaryColor);
BoundaryFill4(x, y-1, FilledColor, BoundaryColor);
}
}
public void BoundaryFill8(int x, int y, int FilledColor, int BoundaryColor){
int CurrentColor;
CurrentColor = GetPixelColor(x,y);
if (CurrentColor != BoundaryColor && CurrentColor != FilledColor)
{
SetPixelColor(x,y,FilledColor);
BoundaryFill8(x+1, y, FilledColor, BoundaryColor);
BoundaryFill8(x-1, y, FilledColor, BoundaryColor);
BoundaryFill8(x, y+1, FilledColor, BoundaryColor);
BoundaryFill8(x, y-1, FilledColor, BoundaryColor);
BoundaryFill8(x+1, y-1, FilledColor, BoundaryColor);
BoundaryFill8(x-1, y-1, FilledColor, BoundaryColor);
BoundaryFill8(x+1, y+1, FilledColor, BoundaryColor);
BoundaryFill8(x-1, y+1, FilledColor, BoundaryColor);
}
}
public Image getImage(boolean alphas){
return Image.createRGBImage(RGBdata, imgW, imgH, alphas);
}
public int[] getRgbData(){
return RGBdata;
}
private void SetPixelColor(int x, int y, int filledColor) {
if(x<0 || x>=imgW || y<0 || y>=imgH)
return;
RGBdata[y*imgW+x] = filledColor;
}
private int GetPixelColor(int x, int y) {
if(x<0 || x>=imgW || y<0 || y>=imgH)
return -1;
return RGBdata[y*imgW+x];
}
}