Flood Fill Algorithm

Flood-fill: wikipeida

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, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.

recursive flood-fill with 4 directions

recursive flood-fill with 8 directions

One implicitly stack-based (recursive) flood-fill implementation (for a two-dimensional array) goes as follows:

Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return.

How to use flood fill algorithm in Android?

You need the the co-ordinates of x and y touch and you can use asynctask to floofill a closed area. Use a progressdialog untill the floodfill fills the closed area with replacement color.

Note: I have faced problem when coloring large closed are. It took lot of time. I am not sure if using asynctask is the beast way. I hope someone can clarify on that part

You can modify the below according to your needs.

final Point p1 = new Point();
p1.x=(int) x; //x co-ordinate where the user touches on the screen
p1.y=(int) y; //y co-ordinate where the user touches on the screen  

FloodFill f= new FloodFill(); 
f.floodFill(bmp,pt,targetColor,replacementColor);

FloodFill algorithm to fill a closed area

    public class FloodFill {
public void floodFill(Bitmap  image, Point node, int targetColor,
        int replacementColor) {
    int width = image.getWidth();
    int height = image.getHeight();
    int target = targetColor;
    int replacement = replacementColor;
    if (target != replacement) {
        Queue<Point> queue = new LinkedList<Point>();
        do {
            int x = node.x;
            int y = node.y;
            while (x > 0 && image.getPixel(x - 1, y) == target) {
                x--;
            }
            boolean spanUp = false;
            boolean spanDown = false;
            while (x < width && image.getPixel(x, y) == target) {
                image.setPixel(x, y, replacement);
                if (!spanUp && y > 0 && image.getPixel(x, y - 1) == target) {
                    queue.add(new Point(x, y - 1));
                    spanUp = true;
                } else if (spanUp && y > 0
                        && image.getPixel(x, y - 1) != target) {
                    spanUp = false;
                }
                if (!spanDown && y < height - 1
                        && image.getPixel(x, y + 1) == target) {
                    queue.add(new Point(x, y + 1));
                    spanDown = true;
                } else if (spanDown && y < height - 1
                        && image.getPixel(x, y + 1) != target) {
                    spanDown = false;
                }
                x++;
            }
        } while ((node = queue.poll()) != null);
    }
}
}

 

Fill the complete canvas but keep the bound fill area as it is like circle, rectangle

 

Android: How to fill color to the specific part of the Image only?

J. Dunlap’s Queue-Linear Flood Fill Algorithm to android here. I’ve tried it and it’s pretty fast.

I’ve modified the copyImage() method which originally makes use of a class called Utilities which the author hasn’t provided.