0
public void floodFill(Bitmap bitmap, Point point, int i, int j) {
    int k = bitmap.getWidth();
    int l = bitmap.getHeight();
    if (i != j) {
        LinkedList linkedlist = new LinkedList();
        do {
            int i1 = point.x;
            int j1;
            for (j1 = point.y; i1 > 0 && !isBlack(bitmap.getPixel(i1 - 1, j1),j); i1--) {
            }
            boolean flag = false;
            boolean flag1 = false;
            while (i1 < k && !isBlack(bitmap.getPixel(i1, j1), j)) {
                bitmap.setPixel(i1, j1, j); //main

                if (!flag && j1 > 0 && !isBlack(bitmap.getPixel(i1, j1 - 1), j)) {
                    linkedlist.add(new Point(i1, j1 - 1));
                    flag = true;
                } else if (flag && j1 > 0 && isBlack(bitmap.getPixel(i1, j1 - 1), j)) {
                    flag = false;
                }

                if (!flag1 && j1 < l - 1 && !isBlack(bitmap.getPixel(i1, j1 + 1), j)) {
                    linkedlist.add(new Point(i1, j1 + 1));
                    flag1 = true;
                } else if (flag1 && j1 < l - 1 && isBlack(bitmap.getPixel(i1, j1 + 1), j)) {
                    flag1 = false;
                }

                i1++;
            }

            point = (Point) linkedlist.poll();
        } while (point != null);
    }
}

private boolean isBlack(int i, int j) {
    while (Color.red(i) == Color.green(i) && 
            Color.green(i) == Color.blue(i) && 
            Color.red(i) < 100 || i == j) {
        return true;
    }
    return false;
}

I am using this code to fill the shape with respective colours on click of any portion of image. It is working absolutely fine without leaving white edges at the border, but the issue with this is its working too slow. how can I speed it up?

Vincent van der Weele
  • 12,927
  • 1
  • 33
  • 61
N.R
  • 191
  • 1
  • 13

2 Answers2

1

You can try different ways to speed thins up:

  1. Change the algorithm itself
  2. make little optiomizations that might speed things a bit.

As always for optimization: Profile the code before and after each optimization attempt to see if you gained anything.

Related to 1.
If you have big black areas, you could try:

  1. downscale your image and fill the downscaled image (but not up to the borders) and apply the filling in big rectangles to the original image.

  2. fill in the original image next to one of the big rectangles filled in step 1 (to sill the border and all details)

Related to 2.

  • maybe you can add a 1 pixel black border around your image. This way you can remove all your border checks:

    public void floodFill(Bitmap bitmap, Point point, int i, int j) {
int k = bitmap.getWidth();
int l = bitmap.getHeight();
if (i != j) {
    LinkedList linkedlist = new LinkedList();
    do {
        int i1 = point.x;
        int j1;
        for (j1 = point.y; i1 > 0 && !isBlack(bitmap.getPixel(i1 - 1, j1),j); i1--) {
        }
        boolean flag = false;
        boolean flag1 = false;
        while (i1 < k && !isBlack(bitmap.getPixel(i1, j1), j)) {
            bitmap.setPixel(i1, j1, j); //main

            if (!flag && !isBlack(bitmap.getPixel(i1, j1 - 1), j)) {
                linkedlist.add(new Point(i1, j1 - 1));
                flag = true;
            } else if (flag && isBlack(bitmap.getPixel(i1, j1 - 1), j)) {
                flag = false;
            }

            if (!flag1 && !isBlack(bitmap.getPixel(i1, j1 + 1), j)) {
                linkedlist.add(new Point(i1, j1 + 1));
                flag1 = true;
            } else if (flag1 && j1 < l - 1 && isBlack(bitmap.getPixel(i1, j1 + 1), j)) {
                flag1 = false;
            }
            i1++;
        }

        point = (Point) linkedlist.poll();
    } while (point != null);
}

// maybe even reorder the conditions:
// If conditions are equal hard to compute:
// for || always do the mostlikely satisfied condition to the front
// for && always do the mostlikely to fail condition to the front



private boolean isBlack(int i, int j) {
    float r= Color.red(i);
    float g= Color.green(i);
    float b= Color.blue(i);
    retrun (r == g && g == b && r < 100 || i == j) ;
}
MrSmith42
  • 9,961
  • 6
  • 38
  • 49
  • I have same issue, this is good, you have done in isBlack(...) method, but still it needs to fill the area more quickly. I think we should put the Queue functionality in it, then the performance may be better, but didn't understand how to do it, As did in this thread https://stackoverflow.com/questions/40895477/white-spaces-left-in-coloring-using-queuelinearfloodfillalgorithm It is fast but it leaves some white spaces, thats y I didn't use it, can you please embed these two with each other to get the best Algorithm for Flood Filling. Thanks – Zia Ur Rahman Mar 10 '18 at 02:17
0

I'm very late, but this works slow because you are using linked lists. You should have used a dynamic array with some reserved size like 64KB, and increase by 64KB each time the buffer is full. Moreover, each call to linkedlist.add() would take about 20 times more cpu cycles than a simple array with direct access. And that's for the function call only: each new item in the list also requires some malloc, whereas you should malloc as few as possible (hence the reserved 64KB memory block).

Garrigue
  • 1