Algoritmo de relleno de inundación Python

Question

Estoy intentando crear un algoritmo de relleno de inundación y sigo obteniendo un error de recursión con esto. El algoritmo parece tener recursión infinita y no puedo precisar por qué. He buscado en Internet y no puedo encontrar una solución, ya que parece que mi programa es correcto según la mayoría de las fuentes. Sin embargo, parece haber algo mal. Esta es la versión editada del código. El mensaje de error sigue siendo recursiones máximas.

¿Se puede obtener ayuda?

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 tiene una tendencia a arrojar un error maximum recursion depth exceeded, incluso si el algoritmo no se repite infinitamente y eventualmente se detendrá por sí mismo. Hay dos soluciones para esto: aumentar el límite de recursión o cambiar a un algoritmo iterativo.

Puede aumentar su límite de recursividad con sys.setrecursionlimit. Elija un número más alto que la peor profundidad de recursión de su algoritmo. En su caso, ese sería el número de píxeles en su imagen, length * height.

Cambiar su algoritmo en uno iterativo es bastante simple, ya que realmente no importa en qué orden usted pinta los píxeles, siempre y cuando los obtenga todos al menos una vez. Un set es muy adecuado para almacenar datos únicos no ordenados, así que vamos a usar eso para almacenar los píxeles que necesitamos para pintar.

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

Si utiliza el método iterativo, asegúrese de poner la comprobación de cota en ella. De lo contrario, podría funcionar para siempre! O al menos hasta que su disco duro se llene con un gigantesco conjunto de toFill.

Answer 2

En lugar de recursividad, por qué no llenar las inundaciones de manera depth-first? Recursion usa una pila implícita de todos modos para que no tenga nada que perder.

Y sí, como se señala en los comentarios, debe comprobar si xey están fuera de los límites.

Answer 3

Esto no se ha probado, pero se basa principalmente en el código que proporcionó. Debería funcionar y proporciona un método alternativo para implementar el algoritmo floodfill. La función podría ser más eficiente.

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)