Implementing the flood fill algorithm

From CodeCodex

Revision as of 14:44, 7 November 2006 by Jdh30 (Talk | contribs)

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>