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

[Bob Klimek]

The code is a direct implementation of the pseudo-code in Graphics Gems 
1. Nothing more, nothing less. I suppose that I could have gone to the 
next step and made it more "pythonic", but... it works! Personally I 
would love to see a better and faster version of flood-fill function in PIL.

Bob


Eric S. Raymond wrote:

>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.
>  
>