Flood Fill Algorithmus-Python

Python hat eine Tendenz zu werfen maximum recursion depth exceeded Fehler, auch wenn der Algorithmus nicht recurse unendlich und würde schließlich den halt auf seinen eigenen. Es gibt zwei Lösungen: erhöhen Sie die Rekursion begrenzen, oder wechseln Sie zu einem iterativen Algorithmus.

Können Sie erhöhen Ihr Rekursion Grenze mit sys.setrecursionlimit. Wählen Sie eine Nummer höher als die worst-case-Rekursionstiefe des Algorithmus. In deinem Fall wäre die Anzahl der Pixel im Bild, length * height.

Ändern Ihren Algorithmus in einen iterativen eines ist ziemlich einfach, da ist es eigentlich egal, in welcher Reihenfolge Sie die Farbe der Pixel, so lange, wie Sie Sie bekommen alle mindestens einmal. Ein set ist sehr gut geeignet, um zu halten die einzigartige nicht-geordnete Daten, verwenden wir also, dass zum speichern der Pixel, die wir brauchen, um zu malen.

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

Wenn Sie verwenden den iterative Methode, sicher sein, setzen Sie gebunden Check-in es. Sonst könnte es laufen, für immer! Oder zumindest, bis Ihre Festplatte ist gefüllt von einem riesigen toFill gesetzt.

Wurde dies nicht getestet, sondern basiert größtenteils aus dem code, den Sie zur Verfügung gestellt. Es sollte funktionieren und stellt eine alternative Methode zur Umsetzung der floodfill Algorithmus. Die Funktion könnte effizienter sein.

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)