Flood Fill in Python

Question

I'm complitely new to Flood Fill algorithm. I checked it out from Wikipedia (http://en.wikipedia.org/wiki/Flood_fill). But didn't become that much wiser. I'm trying to use it in following situation. I have a matrix:

matrix = [["a", "a", "b", "a", "a", "b"],
          ["a", "b", "b", "a", "b", "b"],
          ["b", "a", "b", "a", "a", "b"],
          ["b", "a", "b", "a", "b", "b"],
          ["a", "a", "b", "a", "a", "a"],
          ["a", "b", "b", "a", "a", "b"]]

Then I let user to decide one point from matrix. If in that given point is "b" nothing is done. In the other case if in the given point is "a" I want to change that given point and all surrounding or connected points with "a" to "c" with help of flood fill algorithm.

For example let's say user decides matrix[0][0]. Then new matrix would be:

matrix = [["c", "c", "b", "a", "a", "b"],
          ["c", "b", "b", "a", "b", "b"],
          ["b", "a", "b", "a", "a", "b"],
          ["b", "a", "b", "a", "b", "b"],
          ["a", "a", "b", "a", "a", "a"],
          ["a", "b", "b", "a", "a", "b"]]

Let's continue that example and say user decieds new point, matrix[3][1]. Then we would have:

matrix = [["c", "c", "b", "a", "a", "b"],
          ["c", "b", "b", "a", "b", "b"],
          ["b", "c", "b", "a", "a", "b"],
          ["b", "c", "b", "a", "b", "b"],
          ["c", "c", "b", "a", "a", "a"],
          ["c", "b", "b", "a", "a", "b"]]

I'm trying to build a function floodfill(matrix, x, y) and so far I have come up with this:

def floodfill(matrix, x, y):
    if matrix[y][x] == "b":
        return matrix
    elif matrix[y][x] == ".":
        stack = []

Do you have a way to lead me to proceed? Tried to look on flood fill examples on here SOF but they seemed not to fit my situation. At least I wasn't able to apply those examples to my code. Flood fill does not seem to be that popular subject here... But again, help would be highly appreciated!

Solution 1

Well, the idea of flood fill is:

1. Check if the point meet the criteria.
2. If it is, change it to "c" (in your case) - and invoke flood fill on all surrounding cells.

python-like pseudo code:

def floodfill(matrix, x, y):
    #"hidden" stop clause - not reinvoking for "c" or "b", only for "a".
    if matrix[x][y] == "a":  
        matrix[x][y] = "c" 
        #recursively invoke flood fill on all surrounding cells:
        if x > 0:
            floodfill(matrix,x-1,y)
        if x < len(matrix[y]) - 1:
            floodfill(matrix,x+1,y)
        if y > 0:
            floodfill(matrix,x,y-1)
        if y < len(matrix) - 1:
            floodfill(matrix,x,y+1)

Solution 2

There are several implementations of the flood fill algorithm in image processing libraries for Python. I'm aware of two: skimage.segmentation.flood and OpenCV's floodFill. The former is implemented in Python using an algorithm similar to the one in amit's answer above. The latter is implemented in C++ using a conceptually similar algorithm, but without recursion, making it much more efficient (about 25x for large images).

To use OpenCV's floodFill, you'd need to convert your matrix to an np.array of integers, which could be done as follows:

import numpy as np
import cv2

matrix_np = np.asarray(matrix)
numeric_matrix = np.where(matrix_np=="a", 255, 0).astype(np.uint8)
mask = np.zeros(np.asarray(numeric_matrix.shape)+2, dtype=np.uint8)
start_pt = (y,x)
if matrix_np[start_pt]:
  cv2.floodFill(numeric_matrix, mask, start_pt, 255, flags=4)
mask = mask[1:-1, 1:-1]
matrix_np[mask==1] = "c"
matrix = matrix_np.tolist()

With the example matrix you gave above and x,y=(0,0), this will set matrix to

[['c', 'c', 'b', 'a', 'a', 'b'],
 ['c', 'b', 'b', 'a', 'b', 'b'],
 ['b', 'a', 'b', 'a', 'a', 'b'],
 ['b', 'a', 'b', 'a', 'b', 'b'],
 ['a', 'a', 'b', 'a', 'a', 'a'],
 ['a', 'b', 'b', 'a', 'a', 'b']]

Comments

[rodrigo]

In the true branch of the if you return the matrix, but not in the false one, just like the OP did. The matrix is modified in place so there is no need to return it. Actually just comparing =="a" is enough.

[amit]

@rodrigo yea, thanks. I was taking his code and as said - just showed pseudo code of what the changes should look like. I fixed that issue.

[Waldema]

Hmm.. ok! Now I'm becoming to understand how this works. I tried this idea, and it worked just fine with matrix[0][0] to matrix[4][0], but matrix[5][0] gives an error IndexError: list index out of range

[Waldema]

Oh, sorry. I was a little unclear. With matrix above it works just fine, but if you take a 6x12 for example, this doesn't work. Gives the IndexError: list index out of range

[Waldema]

@rodrigo So I need to switch places between x:s and y:s in the code after if matrix[y][x] = "c"?

[rodrigo]

@Waldema: just some of them... just let me fix that, it looks like amit is AFK :-(

[amit]

@rodrigo thanks, was a bit busy. Didn't put much thought into the indices, that's why I explicitly metioned this is a python-like pseudo-code (thus is not 100% ready for run, but more than enough to understand the important issues).

[Waldema]

Thank you guys very much! Works just fine now!

[Waldema]

What do you think is there more preferable way to do this?