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

enter image description here

 

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.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

生活在西班牙

自己动手丰衣足食

BlueAsteroid

Just another WordPress.com site

Jing's Blog

Just another WordPress.com site

Start from here......

我的心情魔方

天才遠私廚

希望能做一個分享各種資訊的好地方

语义噪声

西瓜大丸子汤的博客

笑对人生,傲立寰宇

Just another WordPress.com site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision

datarazzi

Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness

槑烎

1,2,∞

Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: