बाढ़ भरें एल्गोरिदम पाइथन

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

पायथन में 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 सेट से भर जाती है।

Answer 2

प्रत्यावर्तन के बजाय

, क्यों नहीं एक depth-first ढंग के बाढ़ भरने? रिकर्सन किसी भी तरह के स्टैक का उपयोग करता है, इसलिए आपके पास खोने के लिए कुछ भी नहीं है।

और हां, जैसा टिप्पणियों में बताया गया है, आपको एक्स और वाई को सीमा से बाहर होने की जांच करनी चाहिए।

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)