Massive Algorithms: Flood fill

Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color

Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在GNU Go和扫雷中，Flood Fill算法被用来计算需要被清除的区域。

最简单的实现方法是采用深度优先搜索的递归方法，也可以采用广度优先搜索的迭代来实现。

除提出连通区域外，还可以应用于计算从某一节点开始，到可能到达其他所有节点的距离。比如解决像走迷宫这类的问题。

4-Way Recursive Method (floodFill4)
http://lodev.org/cgtutor/floodfill.html

//Recursive 4-way floodfill, crashes if recursion stack is full 
void floodFill4(int x, int y, int newColor, int oldColor) 
{ 
    if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor) 
    { 
        screenBuffer[x][y] = newColor; //set color before starting recursion
        
        floodFill4(x + 1, y,     newColor, oldColor);
        floodFill4(x - 1, y,     newColor, oldColor);
        floodFill4(x,     y + 1, newColor, oldColor);
        floodFill4(x,     y - 1, newColor, oldColor);
    }     
}

8-Way Recursive Method (floodFill8)
http://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm

Its weaknesses: repeated sampling of pixels, recursion (may overflow stack), and it is designed to leak on the diagonals.

Note: This is what I call an abnormal flood fill method. Since it is designed to leak on the diagonals, it has very limited use.

//Recursive 8-way floodfill, crashes if recursion stack is full
void floodFill8(int x, int y, int newColor, int oldColor)
{
    if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
    {
        screenBuffer[x][y] = newColor; //set color before starting recursion!
        
        floodFill8(x + 1, y,     newColor, oldColor);
        floodFill8(x - 1, y,     newColor, oldColor);
        floodFill8(x,     y + 1, newColor, oldColor);
        floodFill8(x,     y - 1, newColor, oldColor);
        floodFill8(x + 1, y + 1, newColor, oldColor);
        floodFill8(x - 1, y - 1, newColor, oldColor);
        floodFill8(x - 1, y + 1, newColor, oldColor);
        floodFill8(x + 1, y - 1, newColor, oldColor);
    }    
}

Java code
Iterative Version: http://rosettacode.org/wiki/Bitmap/Flood_fill#Java
Recursive version http://www.cis.upenn.edu/~cis110/13fa/hw/hw08/FloodFill.java

    private static void flood(Picture img, boolean[][] mark,
                             int row, int col, Color srcColor, Color tgtColor) {
        // make sure row and col are inside the image
        if (row < 0) return;
        if (col < 0) return;
        if (row >= img.height()) return;
        if (col >= img.width()) return;
        
        // make sure this pixel hasn't been visited yet
        if (mark[row][col]) return;
        
        // make sure this pixel is the right color to fill
        if (!img.get(col, row).equals(srcColor)) return;
        
        // fill pixel with target color and mark it as visited
        img.set(col, row, tgtColor);
        mark[row][col] = true;

        // animate
        img.show();
        sleep(25);
        
        // recursively fill surrounding pixels
        // (this is equivelant to depth-first search)
        flood(img, mark, row - 1, col, srcColor, tgtColor);
        flood(img, mark, row + 1, col, srcColor, tgtColor);
        flood(img, mark, row, col - 1, srcColor, tgtColor);
        flood(img, mark, row, col + 1, srcColor, tgtColor);
    }

        for (int row = 0; row < img.height(); row++) {
            for (int col = 0; col < img.width(); col++) {
                flood(img, mark, row, col,
                      Color.BLACK, Color.RED);
            }
        }

BFS: Using Queue

flood_fill(x,y, check_validity)

   Queue q
   q.push((x,y))
   while (q is not empty)
       (x1,y1) = q.pop()
       if (check_validity(x1+1,y1))
            color(x1,y1)
            q.push(x1+1,y1)
       if (check_validity(x1-1,y1))
            color(x1,y1)
            q.push(x1-1,y1)
       if (check_validity(x1,y1+1))
            color(x1,y1)
            q.push(x1,y1+1)
       if (check_validity(x1,y1-1))
            color(x1,y1)
            q.push(x1,y1-1)

http://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/
Read full article from Flood fill - Wikipedia, the free encyclopedia

Flood fill

Labels

Popular Posts