[Image-SIG] Here's a better flood-fill technique

[Eric S. Raymond]

On 25 June 2005 William Baxter posted a request for a flood-fill
algorithm in Python, The following day Bob Klimek posted an effective
but extremely complex implementation to this list.

At the time I was not interested in this problem.  In the last few
days I have become so.  I'm translating some old C graphics code of
mine into Python, and my naive recursive flood-fill blew the
interpreter stack.

I found Mr. Klimek's answer while Googling for a Python flood-fill.  I
looked at the code, went "Bletch! This is complicated!  I don't want
to maintain this!" and decided to invent a simpler way.

With all due respect to Mr. Klimek, he wasn't thinking like a Python
programmer.  The right thing to do is exploit Python's list-handling.
Here is the code:

def __flood_fill(image, x, y, value):
    "Flood fill on a region of non-BORDER_COLOR pixels."
    if not image.within(x, y) or image.get_pixel(x, y) == BORDER_COLOR:
        return
    edge = [(x, y)]
    image.set_pixel(x, y, value)
    while edge:
        newedge = []
        for (x, y) in edge:
            for (s, t) in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                if image.within(s, t) and \
                	image.get_pixel(s, t) not in (BORDER_COLOR, value):
                    image.set_pixel(s, t, value)
                    newedge.append((s, t))
        edge = newedge

At each step there is a list of edge pixels for the flood-filled 
region.  You check every pixel adjacent to the edge; for each, if it is
eligible to be colored, you color it and add it to a new edge list.
Then you replace the old edge list with the new one.  Stop when the
list is empty.

(The methods have slightly different names than in PIL because I'm
using a thin wrapper class around Image.  Translation is trivial.)

This is nonrecursive and the storage requirement is bounded by the
number of pixels in the region perimeter.  Each pixel will be accessed
at most three times and set just once.  It's simple and efficient.
Even, dare I say it, elegant.

The lesson: when writing Python, don't forget that you have dynamic
data types!

Frederik, say the word and I'll ship you a generalized version for PIL.
-- 
		<a href="http://www.catb.org/~esr/">Eric S. Raymond</a>

The abortion rights and gun control debates are twin aspects of a deeper
question --- does an individual ever have the right to make decisions
that are literally life-or-death?  And if not the individual, who does?