需要帮助实施泛洪填充算法 [英] Need help implementing flood-fill algorithm

问题描述

所以我试图创建一个泛洪填充算法，但我一直收到递归错误。这个算法似乎有无限的递归，我不知道为什么。我已经在互联网上找遍了，但我找不到解决方案，因为根据大多数来源，我的程序似乎是正确的。然而，这似乎有些不对劲。这是代码的编辑版本。错误消息仍然是最大递归次数。

我能得到一些帮助吗？

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

推荐答案

有抛出maximum recursion depth exceeded错误的倾向，即使算法不会无限递归并且最终会自行停止。此问题有两种解决方案：增加递归限制，或切换到迭代算法。

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

将您的算法更改为迭代算法相当简单，因为绘制像素的顺序并不重要，只要您至少获得一次。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集填满。

这篇关于需要帮助实施泛洪填充算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！