Python Flood Fill Algorithm

Question

So, I'm trying to create a fill filling algorithm, and I get a recursion error all the time. The algorithm has infinite recursion, and I cannot pinpoint why. I looked all over the Internet and I can’t find a solution, because it seems that my program is correct in accordance with most sources. However, something seems to be wrong. This is an edited version of the code. The error message is still the maximum recursion.

Can i get help?

from Tkinter import * from PIL import Image, ImageTk from random import * w= 75 h= w flood = Image.new("RGB", (w,h), (0,0,0)) x = 0 y = 0 count = 0 colorlist = [] i = 0 while x < w -1: y = 0 while y < h-1: r = random() if r < .25: flood.putpixel((x,y), (0,0,0)) else: flood.putpixel((x,y), (255,255,255)) y += 1 x += 1 x = 0 y = 0 while x < w-1: y = 0 while y < h-1: r = random() if x == 0 or y == 0 or x == w-1 or y ==h-1: flood.putpixel((x,y), (0,0,0)) y += 1 x += 1 def floodfill(x,y, d,e,f, g,h,i, image, count): count+=1 (a,b,c) = image.getpixel((x,y)) if (a,b,c) == (255,255,255): (j,k,l) = image.getpixel((x-1,y)) (m,n,o) = image.getpixel((x+1, y)) (p,q,r) = image.getpixel((x,y-1)) (s,t,u) = image.getpixel((x,y+1)) if count > 990: return if (a,b,c) == (255,255,255): image.putpixel((x,y), (g,h,i)) floodfill(x-1, y, d,e,f, g,h,i, image, count) floodfill(x+1, y, d,e,f, g,h,i, image, count) floodfill(x, y-1, d,e,f, g,h,i, image, count) floodfill(x, y+1, d,e,f, g,h,i, image,count) floodfill(2,2, 0,0,0,255,0,0,flood, 0) flood.save("flood.png") print "done" 

Answer 1

Python tends to throw a maximum recursion depth exceeded error, even if the algorithm doesn’t solve endlessly and eventually stops by itself. There are two solutions for this: increase the recursion limit or go to an iterative algorithm.

You can increase the recursion limit with sys.setrecursionlimit . Choose a number that exceeds the recursion depth of the worst case scenario of your algorithm. In your case, this will be the number of pixels in your image, length * height .

Changing your algorithm in iterative order is quite simple, as it really doesn't matter in which order you draw pixels until you get them at least once. A set very suitable for storing unique unordered data, so let's use them to store the pixels we need to draw.

 def floodFill(x,y, d,e,f, g,h,i, image): toFill = set() toFill.add((x,y)) while not toFill.empty(): (x,y) = toFill.pop() (a,b,c) == image.getpixel((x,y)) if not (a,b,c) == (255, 255, 255): continue image.putpixel((x,y), (g,h,i)) toFill.add((x-1,y)) toFill.add((x+1,y)) toFill.add((x,y-1)) toFill.add((x,y+1)) image.save("flood.png") 

If you use an iterative method, be sure to set the binding to it. Otherwise, it can go on forever! Or at least until your hard drive is filled with one giant set of toFill .

Answer 2

Instead of recursion, why not fill the depth-first fill? In any case, recursion uses an implicit stack, so you have nothing to lose.

And yes, as stated in the comments, you should check that x and y are out of bounds.

Answer 3

This was not tested, but was based mainly on the code you provided. It should work and provides an alternative method for implementing the floodfill algorithm. Function may be more efficient.

 import PIL import random import collections WHITE = 255, 255, 255 BLACK = 0, 0, 0 RED = 255, 0, 0 def main(width, height): flood = PIL.Image.new('RGB', (width, height), BLACK) # Create randomly generated walls for x in range(width): for y in range(height): flood.putpixel((x, y), BLACK if random.random() < 0.15 else WHITE) # Create borders for x in range(width): for y in range(height): if x in {0, width - 1} or y in {0, height - 1}: flood.putpixel((x, y), BLACK) floodfill(50, 25, RED, image) # Save image image.save('flood.png') def floodfill(x, y, color, image): # if starting color is different from desired color # create a queue of pixels that need to be changed # while there are pixels that need their color changed # change the color of the pixel to what is desired # for each pixel surrounding the curren pixel # if the new pixel has the same color as the starting pixel # record that its color needs to be changed source = image.getpixel((x, y)) if source != color: pixels = collections.deque[(x, y)] while pixels: x, y = place = pixels.popleft() image.putpixel(place, color) for x_offset in -1, 1: x_offset += x for y_offset in -1, 1: y_offset += y new_place = x_offset, y_offset if image.getpixel(new_place) == source: pixels.append(new_place) if __name__ == '__main__': main(100, 50)