# Implementing the flood fill algorithm

The flood fill algorithm is a method of determining connected regions in an array (e.g. for filling an area of pixels with a colour).

## Implementations

### Pseudocode

One implicitly stack-based recursion flood-fill implementation (for a two-dimensional array) goes as follows:

```Flood-fill (node, target-color, replacement-color):
1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.
3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the south of node, target-color, replacement-color).
4. Return.
```

An explicitly queue-based implementation might resemble the following:

```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 the end of Q.
4. For each element n of Q:
5.  Set the color of n to replacement-color.
6.  If the color of the node to the west of n is target-color, add that node to the end of Q.
If the color of the node to the east of n is target-color, add that node to the end of Q.
If the color of the node to the north of n is target-color, add that node to the end of Q.
If the color of the node to the south of n is target-color, add that node to the end of Q.
7. Continue looping until Q is exhausted.
8. Return.
```

Most practical implementations use a loop for the west and east directions as an optimization to avoid the overhead of queue management:

```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 the end of Q.
4. For each element n of Q:
5.  Set w and e equal to n.
6.  Move w to the west until the color of the node to the west of w no longer matches target-color.
7.  Move e to the east until the color of the node to the east of e no longer matches target-color.
8.  Set the color of nodes between w and e to replacement-color.
9.  For each node n between w and e:
10.   If the color of the node to the north of n is target-color, add that node to the end of Q.
If the color of the node to the south of n is target-color, add that node to the end of Q.
11. Continue looping until Q is exhausted.
12. Return.
```

Adapting the algorithm to use an additional array to store the shape of the region allows generalization to cover "fuzzy" flood filling, where an element can differ by up to a specified threshold from the source symbol. Using this additional array as an alpha channel allows the edges of the filled region to blend somewhat smoothly with the not-filled region.

### C

This code is adapted from a Tetris clone called "Tetanus On Drugs" by Damian Yerrick. It's licensed under the GNU Lesser General Public License.

``` #define BOARD_WIDTH  10
#define BOARD_HEIGHT 20

typedef struct MAP
{
unsigned char b[BOARD_HEIGHT][BOARD_WIDTH];
} MAP;

static void flood_loop(MAP *map, int x, int y,
unsigned int dst_c, unsigned  int src_c)
{
int fillL, fillR, i;
int in_line = 1;
//unsigned char c = src_c, fillC = dst_c;

/* find left side, filling along the way */
fillL = fillR = x;
while( in_line )
{
map->b[y][fillL] = dst_c;
fillL--;
in_line = (fillL < 0) ? 0 : (map->b[y][fillL] == src_c);
}
fillL++;

/* find right side, filling along the way */
in_line = 1;
while( in_line )
{
map->b[y][fillR] = dst_c;
fillR++;
in_line = (fillR > BOARD_WIDTH-1) ? 0 : (map->b[y][fillR] == src_c);
}
fillR--;

/* search top and bottom */
for(i = fillL; i <= fillR; i++)
{
if( y > 0 && map->b[y - 1][i] == src_c )
flood_loop(map, i, y - 1, dst_c, src_c);
if( y < BOARD_HEIGHT && map->b[y + 1][i] == src_c )
flood_loop(map, i, y + 1, dst_c, src_c);
}
}

void flood_fill(MAP *map, int x, int y, unsigned int c)
{
flood_loop(map, x, y, c, map->b[y][x]);
map->b[y][x] = c;  /* some buggy optimizers needed this line */
}
```

### Java

This is the same algorithm adapted by Claudio Santana for Java:

``` int checkPixel(int[] oldPix, int[] newPix)
{
return (newPix[0] == oldPix[0] &&
newPix[1] == oldPix[1]	&&
newPix[2] == oldPix[2]  &&
newPix[3] == oldPix[3] ? 1:0);
}

void floodLoop(WritableRaster raster, int x, int y, int[] fill, int[] old)
{
int fillL, fillR,i;
int in_line=1;
int[] aux =	{255,255,255,255};

Rectangle d = raster.getBounds();

// find left side, filling along the way
fillL = fillR = x;
while(in_line!=0)
{
int[] p = raster.getPixel(fillL,y,aux);
raster.setPixel(fillL,y,fill);
fillL--;
in_line = (fillL < 0) ? 0 : checkPixel(raster.getPixel(fillL,y,aux),old);
}
fillL++;

// find right side, filling along the way
in_line = 1;
while (in_line!=0)
{
raster.setPixel(fillR,y,fill);
fillR++;
in_line = (fillR > d.width-1) ? 0 : checkPixel(raster.getPixel(fillR,y,aux),old);
}
fillR--;

// look up and down
for( i=fillL; i<=fillR; i++ )
{
if ( y>0 && checkPixel(raster.getPixel(i,y-1,aux),old)!=0 )
floodLoop(raster,i,y-1,fill,old);
if ( y<d.height-1 && checkPixel(raster.getPixel(i,y+1,aux),old)!=0 )
floodLoop(raster,i,y+1,fill,old);
}

}

// Initial method you must call
void floodLoop(WritableRaster raster, int x, int y, int[] fill)
{
int[] aux = new int[] {255,255,255,255};

// validation so we don't fall in an infinite loop trying to
// paint in the same color
if ( checkPixel(raster.getPixel(x,y,aux),fill)!=0 )
return;

floodLoop(raster,x,y,fill,raster.getPixel(x,y,aux) );
}
```

### OCaml

Naive non-tail-recursive implementation (this is more than adequate in practice because OCaml only allocates tiny stack frames, allowing deep recursion):

```# let rec flood img targ repl (x, y) =
match try Some img.(x).(y) with _ -> None with
| Some color when color = targ ->
img.(x).(y) <- repl;
let f = flood img targ repl in
f(x-1, y); f(x+1, y); f(x, y-1); f(x, y+1)
| _ -> ();;
val flood : 'a array array -> 'a -> 'a -> int * int -> unit = <fun>
```

For example:

```# let test =
Array.init 10 (fun y -> Array.init 10 (fun x -> if (x+1)/(y+1)<2 then 1 else 0));;
val test : int array array =
[|[|1; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|1; 1; 1; 0; 0; 0; 0; 0; 0; 0|];
[|1; 1; 1; 1; 1; 0; 0; 0; 0; 0|];
[|1; 1; 1; 1; 1; 1; 1; 0; 0; 0|];
[|1; 1; 1; 1; 1; 1; 1; 1; 1; 0|];
[|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
[|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
[|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
[|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
[|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|]|]
# flood test 1 2 (0,0); test;;
- : int array array =
[|[|2; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|2; 2; 2; 0; 0; 0; 0; 0; 0; 0|];
[|2; 2; 2; 2; 2; 0; 0; 0; 0; 0|];
[|2; 2; 2; 2; 2; 2; 2; 0; 0; 0|];
[|2; 2; 2; 2; 2; 2; 2; 2; 2; 0|];
[|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
[|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
[|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
[|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
[|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|]|]
```

Queue-based version:

```# let rec flood img targ repl = function
| [] -> ()
| (x, y) :: t ->
match try Some img.(x).(y) with _ -> None with
| Some color when color = targ ->
img.(x).(y) <- repl;
flood img targ repl
((x-1, y) :: (x+1, y) :: (x, y-1) :: (x, y+1) :: t)
| _ -> flood img targ repl t;;
val flood : 'a array array -> 'a -> 'a -> (int * int) list -> unit = <fun>
```

Continuation passing style (CPS) uses a stack of closures which is shorter but slower than the explicit queue:

```# let rec flood img targ repl (x, y) k () =
match try Some img.(x).(y) with _ -> None with
| Some color when color = targ ->
img.(x).(y) <- repl;
let f = flood img targ repl in
f(x-1, y) (f(x+1, y) (f(x, y-1) (f(x, y+1) k))) ()
| _ -> k();;
val flood : 'a array array -> 'a -> 'a -> int * int -> unit = <fun>
```