Algoritmo de inundación de Android

¿Alguien conoce un algoritmo iterativo y eficiente para llenar inundaciones?

¿O hay alguna forma de implementar el algoritmo de floodfill recursiva sin error de desbordamiento de stack?

Intenté usar el relleno @Flood utilizando una stack, pero no puedo encontrar una manera de trabajar en la imagen en blanco y negro.

Alguien portó el algoritmo Queue-Linear Flood Fill de J. Dunlap a android aquí . Lo probé y es bastante rápido.

copyImage() método copyImage() que originalmente hace uso de una clase llamada Utilities que el autor no ha proporcionado.

 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 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(); } // 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; } } } 

También puede usar un hilo si no desea que la IU espere a que se llene la imagen.

 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(); } }; } 

La respuesta mejor clasificada (por Shubhadeep Chaudhuri) no puede manejar fondos transparentes. Para hacer eso, necesitas agregar un control alfa. Aquí están los cambios necesarios para hacer eso:

Actualizar miembros privados

 protected int[] tolerance = new int[] { 0, 0, 0, 0 }; protected int[] startColor = new int[] { 0, 0, 0, 0 }; 

Métodos de actualización

 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])); } 

este algoritmo funcionó bien para mí.

 private void FloodFill(Bitmap bmp, Point pt, int targetColor, int replacementColor) { Queue q = new LinkedList(); q.add(pt); while (q.size() > 0) { Point n = q.poll(); if (bmp.getPixel(nx, ny) != targetColor) continue; Point w = n, e = new Point(nx + 1, ny); while ((wx > 0) && (bmp.getPixel(wx, wy) == targetColor)) { bmp.setPixel(wx, wy, replacementColor); if ((wy > 0) && (bmp.getPixel(wx, wy - 1) == targetColor)) q.add(new Point(wx, wy - 1)); if ((wy < bmp.getHeight() - 1) && (bmp.getPixel(wx, wy + 1) == targetColor)) q.add(new Point(wx, wy + 1)); wx--; } while ((ex < bmp.getWidth() - 1) && (bmp.getPixel(ex, ey) == targetColor)) { bmp.setPixel(ex, ey, replacementColor); if ((ey > 0) && (bmp.getPixel(ex, ey - 1) == targetColor)) q.add(new Point(ex, ey - 1)); if ((ey < bmp.getHeight() - 1) && (bmp.getPixel(ex, ey + 1) == targetColor)) q.add(new Point(ex, ey + 1)); e.x++; } } } 

es mejor que haga que FloodFill() un método devuelva un objeto Bitmap . convertirlo en un método de la clase de View personalizada. usted sabe la clase de View personalizada tiene. the onDraw(Canvas canvas) . en el onDraw(Canvas c) , use FloodFill() la siguiente manera:

 //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); 

El método setPixel llamado cientos o miles de veces no es muy eficiente. Es mejor mover el algoritmo a C ++ a través de JNI. Aquí está mi biblioteca simple que puedes usar. Es increíblemente mucho más rápido que la implementación pura de Java.

https://github.com/mar3kk/threekkapps_library/

solo llama

 JniBitmap.floodFill(bitmap,x,y,color); 

Hice el algoritmo anterior más rápido.
Use getPixels() y setPixels() lugar de llamar a getPixel() repetidamente.

Pero aquí hay una tarde libre.
Este algoritmo usa más espacio de memoria para una matriz int[bmp.width * bmp.height] .

 private void floodFill_array(Bitmap bmp, Point pt, int targetColor, int replacementColor) { if(targetColor == replacementColor) return; int width, height; int[] arrPixels; width = bmp.getWidth(); height = bmp.getHeight(); arrPixels = new int[width*height]; bmp.getPixels(arrPixels, 0, width, 0, 0, width, height); Queue q = new LinkedList(); q.add(pt); while (q.size() > 0) { Point n = q.poll(); if (arrPixels[width*ny + nx] != targetColor) continue; Point w = n, e = new Point(nx + 1, ny); while ((wx > 0) && (arrPixels[width*wy + wx] == targetColor)) { arrPixels[width*wy + wx] = replacementColor; // setPixel if ((wy > 0) && (arrPixels[width*(wy-1) + wx] == targetColor)) q.add(new Point(wx, wy - 1)); if ((wy < height - 1) && (arrPixels[width*(w.y+1) + wx] == targetColor)) q.add(new Point(wx, wy + 1)); wx--; } while ((ex < width - 1) && (arrPixels[width*ey + ex] == targetColor)) { arrPixels[width*ey + ex] = replacementColor; // setPixel if ((ey > 0) && (arrPixels[width*(ey-1) + ex] == targetColor)) q.add(new Point(ex, ey - 1)); if ((ey < height - 1) && (arrPixels[width*(e.y+1) + ex] == targetColor)) q.add(new Point(ex, ey + 1)); e.x++; } } bmp.setPixels(arrPixels, 0, width, 0, 0, width, height); } 

Si desea usar la opción "Tolerancia", use este código a continuación.

 int minR, maxR, minG, maxG, minB, maxB; // instance values private void floodFill_array(Bitmap bmp, Point pt, int targetColor, int replacementColor, int tolerance) { if(targetColor == replacementColor) return; /* tolerable values */ minR = ((targetColor & 0xFF0000) >> 16) - tolerance; if(minR < 0) minR = 0; else minR = minR << 16; maxR = ((targetColor & 0xFF0000) >> 16) + tolerance; if(maxR > 0xFF) maxR = 0xFF0000; else maxR = maxR << 16; minG = ((targetColor & 0x00FF00) >> 8) - tolerance; if(minG < 0) minG = 0; else minG = minG << 8; maxG = ((targetColor & 0x00FF00) >> 8) + tolerance; if(maxG > 0xFF) maxG = 0x00FF00; else maxG = maxG << 8; minB = (targetColor & 0x0000FF) - tolerance; if(minB < 0) minB = 0; maxB = (targetColor & 0x0000FF) + tolerance; if(maxB > 0xFF) maxB = 0x0000FF; /* tolerable values */ int width, height; int[] arrPixels; width = bmp.getWidth(); height = bmp.getHeight(); arrPixels = new int[width*height]; bmp.getPixels(arrPixels, 0, width, 0, 0, width, height); Queue q = new LinkedList(); q.add(pt); while (q.size() > 0) { Point n = q.poll(); if(!isTolerable(arrPixels[width*ny + nx])) continue; Point w = n, e = new Point(nx + 1, ny); while ((wx > 0) && isTolerable(arrPixels[width*wy + wx])) { arrPixels[width*wy + wx] = replacementColor; // setPixel if ((wy > 0) && isTolerable(arrPixels[width*(wy-1) + wx])) q.add(new Point(wx, wy - 1)); if ((wy < height - 1) && isTolerable(arrPixels[width*(w.y+1) + wx])) q.add(new Point(wx, wy + 1)); wx--; } while ((ex < width - 1) && isTolerable(arrPixels[width*ey + ex])) { arrPixels[width*ey + ex] = replacementColor; // setPixel if ((ey > 0) && isTolerable(arrPixels[width*(ey-1) + ex])) q.add(new Point(ex, ey - 1)); if ((ey < height - 1) && isTolerable(arrPixels[width*(e.y+1) + ex])) q.add(new Point(ex, ey + 1)); e.x++; } } bmp.setPixels(arrPixels, 0, width, 0, 0, width, height); } /** * If the passed color is tolerable, return true. */ private boolean isTolerable(int currentColor){ int r = currentColor & 0xFF0000; int g = currentColor & 0x00FF00; int b = currentColor & 0x0000FF; if(rmaxR || gmaxG || bmaxB) return false; // less than or grater than tolerable values else return true; }