201 Flood Fill Visualization

Description

Bonjour Rubyists,

This week’s quiz comes from Martin DeMello

Flood fill is a simple algorithm that colors 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 flood-fills the region containing that point.

Have Fun!

Summary

This quiz was submitted by Martin DeMello 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

Completed

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

Queue

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!)


Friday, April 17, 2009