Non-recursive implementation of Flood Fill algorithm?

Aviv Cohn picture Aviv Cohn · Feb 18, 2014 · Viewed 17.1k times · Source

I'm working on a small drawing application in Java. I'm trying to create a 'bucket-fill' tool by implementing the Flood Fill algorithm.

I tried using a recursion implementation, but it was problematic. Anyway, I searched around the web and it seems that for this purpose, a non-recursive implementation of this algorithm is recommended.

So I ask you:

Could you describe a non-recursive implementation of the Flood Fill algorithm? An actual code example, some pseudo-code, or even a general explanation will all be welcome.

I'm looking for simplest, or the most efficient implementation you can think of.

(Doesn't have to be Java specific).

Thank you

Answer

sukunrt picture sukunrt · Feb 18, 2014

I'm assuming that you have some sort of a grid where you receive the coordinates of the location from where you would like to fill the area.

Recursive flood fill algorithm is DFS. You can do a BFS to convert it to nonrecursive.

Basically the idea is similar in both the algorithms. You have a bag in which the nodes that are yet to be seen are kept. You remove a node from the bag and put the valid neighbors of the node back into the bag. If the bag is a stack you get a DFS. If it's a queue you get a BFS.

the pseudocode is roughly this.

flood_fill(x,y, check_validity)
   //here check_validity is a function that given coordinates of the point tells you whether
   //the point should be colored or not
   Queue q
   q.push((x,y))
   while (q is not empty)
       (x1,y1) = q.pop()
       color(x1,y1)

       if (check_validity(x1+1,y1))
            q.push(x1+1,y1)
       if (check_validity(x1-1,y1))
            q.push(x1-1,y1)
       if (check_validity(x1,y1+1))
            q.push(x1,y1+1)
       if (check_validity(x1,y1-1))
            q.push(x1,y1-1)

NOTE: make sure that check_validity takes into account whether the point is already colored or not.


  • DFS: Depth First Search
  • BFS: Breadth First Search