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;
}
}
}
如果您不希望 UI 等待图像被填充，您也可以使用线程。
public class FloodFillThread extends Thread {
ProgressDialog mProgressDialog;
Bitmap mBitmap;
int mTargetColor;
int mNewColor;
Point mPoint;
Runnable mCallback;
public FloodFillThread(ProgressDialog pd, Runnable callback, Bitmap bitmap,
Point pt, int targetColor, int newColor) {
mBitmap = bitmap;
mPoint = pt;
mTargetColor = targetColor;
mNewColor = newColor;
mProgressDialog = pd;
mCallback = callback;
}
@Override
public void run() {
QueueLinearFloodFiller filler = new QueueLinearFloodFiller(mBitmap, mTargetColor, mNewColor);
filler.setTolerance(10);
filler.floodFill(mPoint.x, mPoint.y);
handler.sendEmptyMessage(0);
}
private Handler handler = new Handler() {
@Override
public void handleMessage(Message msg) {
mProgressDialog.dismiss();
mCallback.run();
}
};
}
Somebody ported 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.
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;
}
}
}
You could also use a thread if you don't want the UI to wait for the image to be filled.
public class FloodFillThread extends Thread {
ProgressDialog mProgressDialog;
Bitmap mBitmap;
int mTargetColor;
int mNewColor;
Point mPoint;
Runnable mCallback;
public FloodFillThread(ProgressDialog pd, Runnable callback, Bitmap bitmap,
Point pt, int targetColor, int newColor) {
mBitmap = bitmap;
mPoint = pt;
mTargetColor = targetColor;
mNewColor = newColor;
mProgressDialog = pd;
mCallback = callback;
}
@Override
public void run() {
QueueLinearFloodFiller filler = new QueueLinearFloodFiller(mBitmap, mTargetColor, mNewColor);
filler.setTolerance(10);
filler.floodFill(mPoint.x, mPoint.y);
handler.sendEmptyMessage(0);
}
private Handler handler = new Handler() {
@Override
public void handleMessage(Message msg) {
mProgressDialog.dismiss();
mCallback.run();
}
};
}
public void setTargetColor(int targetColor) {
/*Same as before....*/
startColor[3] = Color.alpha(targetColor);
}
public void setTolerance(int value) {
tolerance = new int[] { value, value, value, value };
}
protected boolean CheckPixel(int px) {
int red = (pixels[px] >>> 16) & 0xff;
int green = (pixels[px] >>> 8) & 0xff;
int blue = pixels[px] & 0xff;
int alpha = (Color.alpha(pixels[px]));
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])
&& alpha >= (startColor[3] - tolerance[3]) && alpha <= (startColor[3] + tolerance[3]));
}
The highest ranked answer (by Shubhadeep Chaudhuri) can't handle transparent backgrounds. In order to do that you need to add an alpha check. Here are the changes needed to do that:
//resize the picture that you want to fill to fit the whole display.
bitmap=Bitmap.createScaledBitmap(bitmap, canvas.getWidth(),canvas.getHeight(), true);
/*get the same bitmap flood fill it. we reassign the bit map to iself to keep it for the next and another flood fill
currently_selected_point is a variable/object of type Point.
use the Point object to save your onTouchEvent(Event event) finger coordinates.
I used the Color.RED as a replacement color.
the target color is the color of the selected point currently_selected_point.
*/
bitmap=FloodFill(bitmap, currently_selected_point, bitmap.getPixel(currently_selected_point.x, currently_selected_point.y), Color.RED);
canvas.drawBitmap(bitmap,0,0, paint);
its better that you make FloodFill() a method return a Bitmap object. make it a method of the custom View class. you know the custom View class has. the onDraw(Canvas canvas) method. in the onDraw(Canvas c), use FloodFill() like the following:
//resize the picture that you want to fill to fit the whole display.
bitmap=Bitmap.createScaledBitmap(bitmap, canvas.getWidth(),canvas.getHeight(), true);
/*get the same bitmap flood fill it. we reassign the bit map to iself to keep it for the next and another flood fill
currently_selected_point is a variable/object of type Point.
use the Point object to save your onTouchEvent(Event event) finger coordinates.
I used the Color.RED as a replacement color.
the target color is the color of the selected point currently_selected_point.
*/
bitmap=FloodFill(bitmap, currently_selected_point, bitmap.getPixel(currently_selected_point.x, currently_selected_point.y), Color.RED);
canvas.drawBitmap(bitmap,0,0, paint);
发布评论
评论（5）
有人移植了 J. Dunlap 的 队列线性洪水填充算法到 android 这里。我已经尝试过并且速度相当快。
我修改了
copyImage()方法，该方法最初使用了作者未提供的名为 Utilities 的类。如果您不希望 UI 等待图像被填充，您也可以使用线程。
Somebody ported 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.You could also use a thread if you don't want the UI to wait for the image to be filled.
排名最高的答案（由 Shubhadeep Chaudhuri 提供）无法处理透明背景。为此，您需要添加 alpha 检查。以下是执行此操作所需的更改：
更新私有成员
更新方法
The highest ranked answer (by Shubhadeep Chaudhuri) can't handle transparent backgrounds. In order to do that you need to add an alpha check. Here are the changes needed to do that:
Update Private Members
Update Methods
这个算法对我来说效果很好。
this algorithm worked good for me.
我使上面的算法更快。
使用
getPixels()和setPixels()而不是重复调用getPixel()。但这里有一个延迟。
该算法为数组
int[bmp.width * bmp.height]使用了更多内存空间。如果您想使用“容差”选项，请使用下面的代码。
I made the algorithm above faster.
Use
getPixels()andsetPixels()instead of callinggetPixel()repeatedly.But here is a tarde off.
This algorithm uses more memory space for an array
int[bmp.width * bmp.height].If you want to use the "Tolerance" option, use this code below.
最好让
FloodFill()方法返回Bitmap对象。使其成为自定义View类的方法。你知道自定义View类有。onDraw(Canvas canvas)方法。在onDraw(Canvas c)中，使用FloodFill()，如下所示：its better that you make
FloodFill()a method return aBitmapobject. make it a method of the customViewclass. you know the customViewclass has.the onDraw(Canvas canvas)method. in theonDraw(Canvas c), useFloodFill()like the following: