Non-recursive implementation of Flood Fill algorithm?

Question

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 1

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