I am implementing a flood fill algorithm using Python and NumPy. I have written the following fill function which works fine:
def fill(self, data, xsize, ysize, x_start, y_start):
stack = [(x_start, y_start)]
while stack:
x, y, stack = stack[0][0], stack[0][1], stack[1:]
if data[x, y] == 1:
data[x, y] = 2
if x > 0:
stack.append((x - 1, y))
if x < (xsize - 1):
stack.append((x + 1, y))
if y > 0:
stack.append((x, y - 1))
if y < (ysize - 1):
stack.append((x, y + 1))
I wanted to implement a way that would eliminate the need to re-check a point if it had already been checked. By creating a new list of checked points and then comparing to see if the current point is already in that list, but this ended up making it slower and I wanted to understand if there is a more efficient way to improve upon my existing implementation.