Forum: Ruby Flood Fill Visualization (#201)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2.  Support Ruby Quiz by submitting ideas and responses
as often as you can!
Visit: <http://rubyquiz.strd6.com/suggestions>

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion.  Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Flood Fill Visualization (#201)

Bonjour Rubyists,

This week's quiz comes from [Martin DeMello][1]

[Flood fill][2] is a simple algorithm that colours in a connected
region of a bitmap. The algorithm looks for all nodes which are
connected to the start node by a path of the target color, and changes
them to the replacement color. (Check out the Wikipedia page for more
information.)

While simple, the algorithm is pretty satisfying to watch in action,
which brings us to the quiz: have a program accept a bitmap and a
starting point, and animate the algorithm as it floodfills the region
containing that point.

Have Fun!

[1]: http://zem.novylen.net
[2]: http://en.wikipedia.org/wiki/Flood_fill

My solution attached.

Thanks!
martin

Here's my solution - a bit quick-and-dirty, but I had fun writing it :)

martin

This quiz was submitted by Martin DeMello [1] using the submission
form: http://rubyquiz.strd6.com/suggestions. Please do submit quiz
ideas, Ruby Quiz thrives with support from the community!

Martin Boese provided a solution that animates the filling process by
printing the output to the console.

The core of Martin B.'s solution is this recursive fill method.

    def fill(x, y, target_color, replacement_color)
        return unless self[y][x]  # valid point?

        return if self[y][x] != target_color
        return if self[y][x] == replacement_color

        (dump; sleep(0.2)) if @options[:animation]

        self[y][x] = replacement_color
        fill(x+1, y, target_color, replacement_color)
        fill(x-1, y, target_color, replacement_color)
        fill(x, y+1, target_color, replacement_color)
        fill(x, y-1, target_color, replacement_color)
    end

The method begins with a few checks to determine if it should return.
The first check exits the method if the point is outside of the
canvas. The next check exits if the current point's color does not
match the target color, we don't want to fill just anything. The third
check exits if the current point's color is equal to the replacement
color, if we didn't then we would fill forever!

This part: `(dump; sleep(0.2))` is responsible for printing the state
of the operation to the console and waiting a little bit.

Partially Complete [2]

Completed [3]

The final section sets the color of the current point and recursively
calls `fill` on all adjacent points.

Martin DeMello submitted a Shoes App solution. Although Martin D.'s
solution didn't work for me exactly as submitted, with a little
tweaking I was able to get it to run. The neat part about Martin D.'s
solution is that, aside from being colorful Shoes App, it allows you
to view the animation when the cells are placed in a stack or a queue.

Here are two images showing the difference in how the fills proceed
when using a stack or a queue:

Stack [4]

Queue [5]

In both solution the starting canvas data was represented as characters 
like so:

    data = <<END
    ##############
    #   #        #
    #   #        #
    #  #      #  #
    ###      #   #
    #        #   #
    ##############
    END

Together these two solutions cover the major possible implementations
of the Flood Fill algorithm: recursively with an implicit stack (the
call stack) and iteratively with an explicit stack or queue.

I hope you find these solutions interesting and that they help you out
when you are making your next graphics application (maybe a future
quiz!)

[1]: http://zem.novylen.net
[2]: http://rubyquiz.strd6.com/quizzes/201/floodfill_1.png
[3]: http://rubyquiz.strd6.com/quizzes/201/floodfill_2.png
[4]: http://rubyquiz.strd6.com/quizzes/201/stack.png
[5]: http://rubyquiz.strd6.com/quizzes/201/queue.png

On Sun, Apr 26, 2009 at 2:07 AM, Daniel Moore <yahivin@gmail.com> wrote:
>
> Martin DeMello submitted a Shoes App solution. Although Martin D.'s
> solution didn't work for me exactly as submitted, with a little
> tweaking I was able to get it to run.

Yes, my bad. I built this against the latest shoes-git and ruby 1.9;
the scoping turned out to be slightly different for shoes built
against ruby 1.8

martin