洪水填充算法Python

Question

所以我正在尝试创建一个泛洪填充算法,并且我不断得到一个递归错误.该算法似乎具有无限递归,我无法确定原因.我已经浏览了整个互联网,我无法找到解决方案,因为根据大多数消息来源,我的程序似乎是正确的.然而,似乎有些不对劲.这是代码的编辑版本.错误消息仍然是最大递归.

我可以得到一些帮助吗？

    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有抛出maximum recursion depth exceeded错误的倾向,即使算法无法无限递归并且最终会自行停止.有两种解决方案:增加递归限制,或切换到迭代算法.

您可以使用提高递归限制sys.setrecursionlimit.选择一个高于算法最差情况递归深度的数字.在您的情况下,这将是您的图像中的像素数,length * height.

将算法更改为迭代算法非常简单,因为绘制像素的顺序并不重要,只要您至少获得一次.A set非常适合保存唯一的非有序数据,因此我们使用它来存储我们需要绘制的像素.

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

如果使用迭代方法,请务必将绑定检查放入其中.否则,它可能会永远运行!或者至少在您的硬盘驱动器被一个巨大的toFill装置填满之前.