Flood fill for 2d int array optimization in Java

Question

I am writing my own implementation of the Flood Fill.

I came up with this code:

  public static void fillArea(int x, int y, int original, int fill, int[][] arr) {
        Stack<int[]> q = new Stack<int[]>();
        int[] w = new int[2]; //to the west
        int[] e = new int[2]; //to the east

        if (arr[x][y] != original) {
            return;
        }

        q.push(new int[]{x, y});

        while (!q.isEmpty()) {
            int[] pos = (int[]) q.pop();
            int i = pos[0];
            int j = pos[1];
            if (arr[i][j] == original) {
                e[0] = i;
                e[1] = j;
                w[0] = i;
                w[1] = j;
            }


            while (w[1] > 0 && arr[w[0]][w[1] - 1] == original) { // to the west
                w[1] -= 1;
            }

            while (e[1] < arr[0].length - 1 && arr[e[0]][e[1] + 1] == original) { // to the east
                e[1] += 1;
            }

            for (int a = w[1]; a <= e[1]; a++) { // for every point between west and east
                arr[w[0]][a] = fill;


                if (w[0] > 0 && arr[w[0] - 1][a] == original) { //check if we can go north
                    q.push(new int[]{(w[0] - 1), a});
                }

                if (w[0] < arr.length - 1 && arr[w[0] + 1][a] == original) {//check if we can go south 
                    q.push(new int[]{(w[0] + 1), a});
                }

            }


        }
        return;
    }

Params are:

start point coords, value we want to change, new value we want to see as a result of filling, original array.

It is implementation of Wiki pseudocode:

Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. If the color of node is not equal to target-color, return.
 3. Add node to Q.
 4. For each element N of Q:
 5.     If the color of N is equal to target-color:
 6.         Set w and e equal to N.
 7.         Move w to the west until the color of the node to the west of w no longer matches target-color.
 8.         Move e to the east until the color of the node to the east of e no longer matches target-color.
 9.         For each node n between w and e:
10.             Set the color of n to replacement-color.
11.             If the color of the node to the north of n is target-color, add that node to Q.
12.             If the color of the node to the south of n is target-color, add that node to Q.
13. Continue looping until Q is exhausted.
14. Return.

I am using Stack instead of Queue, because it seems that Stack is much faster, or I have a problem with my code.

The problem is : it is very slow.
Is there anything I can do about performance? I can trade memory for the performance, but native recursion get me stackoverflow.

Answer 1

This version is even faster

public static void floodFill(int y, int x, byte originalvalue, byte newvalue, byte[][] arr) {
    Deque queue = new ArrayDeque();
    queue.add(new int[]{y, x});
    while (!queue.isEmpty()) {
        int[] t = (int[]) queue.poll();
        y = t[0];
        x = t[1];
        if (arr[y][x] == originalvalue) {
            arr[y][x] = newvalue;
            for (int i = 0; i
                    < 8; i++) {
                if (x + dx[i] < arr[0].length && y + dy[i] < arr.length && x + dx[i] > -1 && y + dy[i] > -1 && arr[y + dy[i]][x + dx[i]] == originalvalue) {
                    queue.add(new int[]{y + dy[i], x + dx[i]});
                }
            }
        }
    }
}

Answer 2

Ok, here we go :). I simulated stack with array, which I hope would be much faster. I did not followed exactly the pseudocode, but it works and I think it should be fast.

public static void main(String[] args) {
    int testArray[][] = new int[10][10];
    for (int i = 0; i < 10; i++) {
        testArray[i][i] = 1;
        testArray[9-i][i] = 1;
    }
    testArray[4][7] = 1;

    System.out.println("Array before");

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            System.out.print(testArray[j][i] + " ");
        }
        System.out.println("");
    }

    fillArea(6,8,0,7,testArray);

    System.out.println("Array after");
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            System.out.print(testArray[j][i] + " ");
        }
        System.out.println("");
    }
}

 public static void fillArea(int x, int y, int original, int fill, int[][] arr) {
     int maxX = arr.length - 1;
     int maxY = arr[0].length - 1;
     int[][] stack = new int[(maxX+1)*(maxY+1)][2];
     int index = 0;         

     stack[0][0] = x;
     stack[0][1] = y;
     arr[x][y] = fill;

     while (index >= 0){
         x = stack[index][0];
         y = stack[index][1];
         index--;            

         if ((x > 0) && (arr[x-1][y] == original)){
             arr[x-1][y] = fill;
             index++;
             stack[index][0] = x-1;
             stack[index][1] = y;
         }

         if ((x < maxX) && (arr[x+1][y] == original)){
             arr[x+1][y] = fill;
             index++;
             stack[index][0] = x+1;
             stack[index][1] = y;
         }

         if ((y > 0) && (arr[x][y-1] == original)){
             arr[x][y-1] = fill;
             index++;
             stack[index][0] = x;
             stack[index][1] = y-1;
         }                

         if ((y < maxY) && (arr[x][y+1] == original)){
             arr[x][y+1] = fill;
             index++;
             stack[index][0] = x;
             stack[index][1] = y+1;
         }                          
     }
 }

This code having this output :

Array before
1 0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 1 0 1 0 0 1 0 0 
0 1 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 0 1 
Array after
1 0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 1 7 7 1 0 0 0 
0 0 1 7 1 7 7 1 0 0 
0 1 7 7 7 7 7 7 1 0 
1 7 7 7 7 7 7 7 7 1