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. > > _______________________________________________ Image-SIG maillist - [email protected] http://mail.python.org/mailman/listinfo/image-sig
