[图形算法]种子填充算法

种子填充算法
种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。
种子填充算法常用四连通域和八连通域技术进行填充操作。
从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。
从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。
一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图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模拟================================

/**
 * 填充算法
 * @author comic.sjtu.edu.cn
 *
 */
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);
        }
        
         /**
         * 种子填充算法(4向连通)
         * @param x 填充区域内一点的X坐标
         * @param y 填充区域内一点的Y坐标
         * @param FilledColor   要填充的颜色
         * @param BoundaryColor 边界的颜色
         */
        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);
                }
        }
        
         /**
         * 种子填充算法(8向连通) (72x72的都爆内存了)
         * @param x 填充区域内一点的X坐标
         * @param y 填充区域内一点的Y坐标
         * @param FilledColor   要填充的颜色
         * @param 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];
        }
        
}