洪水填充算法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組合填滿之前。

Answer 2

而不是遞歸，爲什麼不填充depth-first方式？無論如何，遞歸使用隱式堆棧，所以你沒有任何損失。

是的，正如評論中指出的，你應該檢查x和y是否超出界限。

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