10

そのため、フラッド フィル アルゴリズムを作成しようとしていますが、これで再帰エラーが発生し続けます。アルゴリズムには無限再帰があるようで、その理由を特定できません。私はインターネット全体を見てきましたが、ほとんどの情報源によると私のプログラムは正しいように見えるため、解決策が見つかりません。ただし、何か問題があるようです。これはコードの編集バージョンです。エラーメッセージはまだ最大再帰です。

助けてもらえますか？

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

3 に答える 3

12

maximum recursion depth exceededアルゴリズムが無限に再帰せず、最終的には自然に停止する場合でも、Python はエラーをスローする傾向があります。これには 2 つの解決策があります。再帰制限を増やすか、反復アルゴリズムに切り替えます。

で再帰制限を上げることができますsys.setrecursionlimit。アルゴリズムの最悪の場合の再帰の深さよりも大きい数値を選択してください。あなたの場合、それは画像のピクセル数になりますlength * height。

アルゴリズムを反復アルゴリズムに変更するのは非常に簡単です。少なくとも 1 回すべてのピクセルを取得する限り、ピクセルをペイントする順序は重要ではないからです。Asetは一意の順序付けられていないデータを保持するのに非常に適しているため、それを使用して、ペイントする必要があるピクセルを格納しましょう。

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

反復法を使用する場合は、必ず境界チェックを入れてください。そうしないと、永遠に実行される可能性があります。または、少なくともハード ドライブが 1 つの巨大なtoFillセットでいっぱいになるまで。

于 2012-07-31T19:26:52.823 に答える
3

再帰の代わりに、深さ優先の方法でフラッド フィルを実行してみませんか? とにかく再帰は暗黙のスタックを使用するので、失うものは何もありません。

はい、コメントで指摘されているように、 x と y が範囲外であることを確認する必要があります。

于 2012-07-31T19:21:13.173 に答える
3

これはテストされていませんが、主に提供されたコードに基づいています。floodfillそれは機能し、アルゴリズムを実装する代替方法を提供するはずです。関数はより効率的である可能性があります。

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)
于 2012-07-31T19:32:48.647 に答える