How to use flood fill algorithm in Android?
android using flood fill algorithm getting out of memory exception. Check the link has an example.
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);
}
}
}
Edit:
Edit 8-7-2014 :
Filling a small closed area works fine with the above flood fill algorithm. However for large area the algorithm works slow and consumes lot of memory. Recently i came across a post which uses QueueLinear Flood Fill which is way faster that the above.
Source :
http://www.codeproject.com/Articles/16405/Queue-Linear-Flood-Fill-A-Fast-Flood-Fill-Algorith
Code :
public class QueueLinearFloodFiller {
protected Bitmap image = null;
protected int[] tolerance = new int[] { 0, 0, 0 };
protected int width = 0;
protected int height = 0;
protected int[] pixels = null;
protected int fillColor = 0;
protected int[] startColor = new int[] { 0, 0, 0 };
protected boolean[] pixelsChecked;
protected Queue<FloodFillRange> ranges;
// Construct using an image and a copy will be made to fill into,
// Construct with BufferedImage and flood fill will write directly to
// provided BufferedImage
public QueueLinearFloodFiller(Bitmap img) {
copyImage(img);
}
public QueueLinearFloodFiller(Bitmap img, int targetColor, int newColor) {
useImage(img);
setFillColor(newColor);
setTargetColor(targetColor);
}
public void setTargetColor(int targetColor) {
startColor[0] = Color.red(targetColor);
startColor[1] = Color.green(targetColor);
startColor[2] = Color.blue(targetColor);
}
public int getFillColor() {
return fillColor;
}
public void setFillColor(int value) {
fillColor = value;
}
public int[] getTolerance() {
return tolerance;
}
public void setTolerance(int[] value) {
tolerance = value;
}
public void setTolerance(int value) {
tolerance = new int[] { value, value, value };
}
public Bitmap getImage() {
return image;
}
public void copyImage(Bitmap img) {
// Copy data from provided Image to a BufferedImage to write flood fill
// to, use getImage to retrieve
// cache data in member variables to decrease overhead of property calls
width = img.getWidth();
height = img.getHeight();
image = Bitmap.createBitmap(width, height, Bitmap.Config.RGB_565);
Canvas canvas = new Canvas(image);
canvas.drawBitmap(img, 0, 0, null);
pixels = new int[width * height];
image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
}
public void useImage(Bitmap img) {
// Use a pre-existing provided BufferedImage and write directly to it
// cache data in member variables to decrease overhead of property calls
width = img.getWidth();
height = img.getHeight();
image = img;
pixels = new int[width * height];
image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
}
protected void prepare() {
// Called before starting flood-fill
pixelsChecked = new boolean[pixels.length];
ranges = new LinkedList<FloodFillRange>();
}
// Fills the specified point on the bitmap with the currently selected fill
// color.
// int x, int y: The starting coords for the fill
public void floodFill(int x, int y) {
// Setup
prepare();
if (startColor[0] == 0) {
// ***Get starting color.
int startPixel = pixels[(width * y) + x];
startColor[0] = (startPixel >> 16) & 0xff;
startColor[1] = (startPixel >> 8) & 0xff;
startColor[2] = startPixel & 0xff;
}
// ***Do first call to floodfill.
LinearFill(x, y);
// ***Call floodfill routine while floodfill ranges still exist on the
// queue
FloodFillRange range;
while (ranges.size() > 0) {
// **Get Next Range Off the Queue
range = ranges.remove();
// **Check Above and Below Each Pixel in the Floodfill Range
int downPxIdx = (width * (range.Y + 1)) + range.startX;
int upPxIdx = (width * (range.Y - 1)) + range.startX;
int upY = range.Y - 1;// so we can pass the y coord by ref
int downY = range.Y + 1;
for (int i = range.startX; i <= range.endX; i++) {
// *Start Fill Upwards
// if we're not above the top of the bitmap and the pixel above
// this one is within the color tolerance
if (range.Y > 0 && (!pixelsChecked[upPxIdx])
&& CheckPixel(upPxIdx))
LinearFill(i, upY);
// *Start Fill Downwards
// if we're not below the bottom of the bitmap and the pixel
// below this one is within the color tolerance
if (range.Y < (height - 1) && (!pixelsChecked[downPxIdx])
&& CheckPixel(downPxIdx))
LinearFill(i, downY);
downPxIdx++;
upPxIdx++;
}
}
image.setPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
}
// Finds the furthermost left and right boundaries of the fill area
// on a given y coordinate, starting from a given x coordinate, filling as
// it goes.
// Adds the resulting horizontal range to the queue of floodfill ranges,
// to be processed in the main loop.
// int x, int y: The starting coords
protected void LinearFill(int x, int y) {
// ***Find Left Edge of Color Area
int lFillLoc = x; // the location to check/fill on the left
int pxIdx = (width * y) + x;
while (true) {
// **fill with the color
pixels[pxIdx] = fillColor;
// **indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
// **de-increment
lFillLoc--; // de-increment counter
pxIdx--; // de-increment pixel index
// **exit loop if we're at edge of bitmap or color area
if (lFillLoc < 0 || (pixelsChecked[pxIdx]) || !CheckPixel(pxIdx)) {
break;
}
}
lFillLoc++;
// ***Find Right Edge of Color Area
int rFillLoc = x; // the location to check/fill on the left
pxIdx = (width * y) + x;
while (true) {
// **fill with the color
pixels[pxIdx] = fillColor;
// **indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
// **increment
rFillLoc++; // increment counter
pxIdx++; // increment pixel index
// **exit loop if we're at edge of bitmap or color area
if (rFillLoc >= width || pixelsChecked[pxIdx] || !CheckPixel(pxIdx)) {
break;
}
}
rFillLoc--;
// add range to queue
FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
ranges.offer(r);
}
// Sees if a pixel is within the color tolerance range.
protected boolean CheckPixel(int px) {
int red = (pixels[px] >>> 16) & 0xff;
int green = (pixels[px] >>> 8) & 0xff;
int blue = pixels[px] & 0xff;
return (red >= (startColor[0] - tolerance[0])
&& red <= (startColor[0] + tolerance[0])
&& green >= (startColor[1] - tolerance[1])
&& green <= (startColor[1] + tolerance[1])
&& blue >= (startColor[2] - tolerance[2]) && blue <= (startColor[2] + tolerance[2]));
}
// Represents a linear range to be filled and branched from.
protected class FloodFillRange {
public int startX;
public int endX;
public int Y;
public FloodFillRange(int startX, int endX, int y) {
this.startX = startX;
this.endX = endX;
this.Y = y;
}
}
}
Android flood-fill algorithm
this algorithm worked good for me.
private void FloodFill(Bitmap bmp, Point pt, int targetColor, int replacementColor)
{
Queue<Point> q = new LinkedList<Point>();
q.add(pt);
while (q.size() > 0) {
Point n = q.poll();
if (bmp.getPixel(n.x, n.y) != targetColor)
continue;
Point w = n, e = new Point(n.x + 1, n.y);
while ((w.x > 0) && (bmp.getPixel(w.x, w.y) == targetColor)) {
bmp.setPixel(w.x, w.y, replacementColor);
if ((w.y > 0) && (bmp.getPixel(w.x, w.y - 1) == targetColor))
q.add(new Point(w.x, w.y - 1));
if ((w.y < bmp.getHeight() - 1)
&& (bmp.getPixel(w.x, w.y + 1) == targetColor))
q.add(new Point(w.x, w.y + 1));
w.x--;
}
while ((e.x < bmp.getWidth() - 1)
&& (bmp.getPixel(e.x, e.y) == targetColor)) {
bmp.setPixel(e.x, e.y, replacementColor);
if ((e.y > 0) && (bmp.getPixel(e.x, e.y - 1) == targetColor))
q.add(new Point(e.x, e.y - 1));
if ((e.y < bmp.getHeight() - 1)
&& (bmp.getPixel(e.x, e.y + 1) == targetColor))
q.add(new Point(e.x, e.y + 1));
e.x++;
}
}
}
Iterative queue-based flood fill algorithm 'expandToNeighborsWithMap()' function is unusually slow
How I fixed it:
- Getting rid of the
toList()calls. - Creating an
convertXYPositionToIndex()function.
Here is my new code:
Tools.FILL_TOOL -> {
val seedColor = instance.rectangles[rectTapped]?.color ?: Color.WHITE
val queue = LinkedList<XYPosition>()
val spanCount = instance.spanCount.toInt()
queue.offer(MathExtensions.convertIndexToXYPosition(rectangleData.indexOf(rectTapped), spanCount))
val selectedColor = getSelectedColor()
while (queue.isNotEmpty() && seedColor != selectedColor) {
val current = queue.poll()
val color = instance.rectangles[rectangleData[convertXYDataToIndex(spanCount, current)]]?.color ?: Color.WHITE
if (color != seedColor) {
continue
}
instance.rectangles[rectangleData[convertXYDataToIndex(spanCount, current)]] = defaultRectPaint // Colors in pixel with defaultRectPaint
instance.extraCanvas.drawRect(rectangleData[MathExtensions.convertXYPositionToIndex(current, spanCount)], defaultRectPaint)
for (index in expandToNeighborsWithMap(spanCount, current)) {
val candidate = MathExtensions.convertIndexToXYPosition(index, spanCount)
queue.offer(candidate)
}
}
val timeTakenForThis = (System.currentTimeMillis()-startTime)
totalTime += timeTakenForThis
}
Expand to neighbors func:
fun expandToNeighborsWithMap(spanCount: Int, from: XYPosition): List<Int> {
val toReturn = mutableListOf<Int>()
if (from.x > 1) {
toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x - 1, from.y), spanCount))
}
if (from.x < spanCount) {
toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x + 1, from.y), spanCount))
}
if (from.y > 1) {
toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x, from.y - 1), spanCount))
}
if (from.y < spanCount) {
toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x, from.y + 1), spanCount))
}
return toReturn
}
It takes less than a second for canvas sizes of 100 by 100 and 200 by 200, so I'd say it's in the usable stage now.
I would say this is one of the simplest Android flood fill algorithms out there to understand, so if anyone is making an app similar to mine and they want a flood fill tool they can copy my code.
A guy in the comments called EvilTalk helped me with this.
flood fill coloring on android
Problem solved. Bitmap where i used floodfill was RGB_565. I just convert it to ARGB_8888 and everything work fine.
Filling pattern in stead of a color using flood fill algroithim android
Well after a little workaround I was able to fill the pattern in the closed region using Flood Fill Algorithm. Below is what I did.
1.Introduced a new bitmap with the pattern as u can see below.
bitmapPattern = BitmapFactory.decodeResource(getResources(),R.drawable.pattern1).copy(Bitmap.Config.ARGB_8888, true);
And passed this bitmapPattern to the Flood Fill Algorithm as follows.
FloodFillPattern f = new FloodFillPattern();
f.floodFillPattern(bmp, pt, targetColor, replacementColor, pattern);Note you have to scale this bitmap equal to the size of your image in which you will fill this pattern.
Then simply replace the pixels of your original image with the pixels of the pattern bitmap in the flood fill algorithm. As Follows:
image.setPixel(x, y, pattern.getPixel(x,y));
pattern is the patternBitmap you passed.
May it help someone :)
White spaces left in coloring using QueueLinearFloodFillAlgorithm
The white/grey pixels are a result of anti-aliasing, which is used to smooth the edges of the lines. To avoid these artifacts, you could simply not use anti-aliasing when creating the images, or else you could use a two-step tolerance: a lower tolerance value for propagating the flood fill, and a higher one for coloring the pixels but not propagating the fill any further.
However both of these approaches will destroy the anti-aliasing in the image, which will reduce image quality. Another approach is to do another pass over the image and process the pixels bordering the fill (those where pixelsChecked is false but there is at least one neighbour where pixelsChecked is true) and compute an anti-aliased pixel value, assuming that the pixels are being anti-aliased against a black line.
public boolean isFilled(int x, int y)
{
if((x < 0) || (y < 0) || (x >= width) || (y >= height))
return false;
return pixelsChecked[(width * y) + x];
}
public boolean isNeighbourFilled(int x, int y)
{
// return true if at least one neighbour is filled:
for(int offsetY = -1; offsetY <= 1; offsetY++)
{
for(int offsetX = -1; offsetX <= 1; offsetX++)
{
if((offsetX != 0) && (offsetY != 0) &&
isFilled(x + offsetX, y + offsetY))
return true;
}
}
return false;
}
public void antiAliasFillOutline()
{
for(int y = 0; y < height; y++)
{
for(int x = 0; x < width; x++)
{
// if pixel is not filled by neighbour is then it's on the border
if(!isFilled(x, y) && isNeighbourFilled(x, y))
{
// compute an anti-aliased pixel value:
antiAliasPixel(x, y);
}
}
}
}
public void antiAliasPixel(int x, int y)
{
int pixel = pixels[(width * y) + x];
int red = (pixel >>> 16) & 0xff;
int green = (pixel >>> 8) & 0xff;
int blue = pixel & 0xff;
int fillred = (fillColor >>> 16) & 0xff;
int fillgreen = (fillColor >>> 8) & 0xff;
int fillblue = fillColor & 0xff;
// work out how much to anti-alias from 0 to 256:
int amount = ((red + green + blue) * 256) /
(startColor[0] + startColor[1] + startColor[2]);
if(amount > 256)
amount = 256;
red = (fillred * amount) >> 8;
green = (fillgreen * amount) >> 8;
blue = (fillblue * amount) >> 8;
pixels[(width * y) + x] = 0xff000000 | (red << 16) | (green << 8) | blue;
}
Call antiAliasFillOutline() at the end of the flood fill.
You could speed it up a bit (at the expense of readability) by inlining some of the function calls and removing the bounds checks on pixelsChecked:
public void antiAliasFillOutlineFaster()
{
for(int y = 1; y < height - 1; y++)
{
int i = (y * width) + 1;
for(int x = 1; x < width - 1; x++)
{
// if pixel is not filled by neighbour is then it's on the border
if(!pixelsChecked[i] &&
(pixelsChecked[i-1] || pixelsChecked[i+1] ||
pixelsChecked[i-width-1] || pixelsChecked[i-width] || pixelsChecked[i-width+1] ||
pixelsChecked[i+width-1] || pixelsChecked[i+width] || pixelsChecked[i+width+1]))
{
// compute an anti-aliased pixel value:
antiAliasPixel(x, y);
}
i++;
}
}
}
You could also try just checking the 4 neighbouring pixels instead of the 8 neighbours including diagonals. Also, values like fillred etc and (startColor[0] + startColor[1] + startColor[2]) could be computed once and stored in member variables.
Related Topics
How to Instantiate an Abstract Class Directly
Does Proguard Work to Obfuscate Static String Constants
Sqliteopenhelper Failing to Call Oncreate
Custom Progress Bar in Android
Android: Changing Background-Color of the Activity (Main View)
Portrait for Phone, Landscape for Tablet (Android-Layout)
Android - How to Change Fragments in the Navigation Drawer
How to Create Button Dynamically in Android
Spannable on Android for Textview
How to Launch Home Screen Programmatically in Android
How to Crop a Bitmap for Imageview
No Resource Identifier Found for Attribute 'Layout_Behavior' in Package
What Is the Use of Basecolumns in Android