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.
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