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!

Vulpine

not much. I updated it to my first post. All I know now is that I have to build a stack. – Vulpine

For an actual Python implementation - Flood fill NumPy Array. – Carmoncarmona

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

Sleepless

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. – Briton

@Briton 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. – Sleepless

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 – Vulpine

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 – Vulpine

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

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

@Briton 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). – Sleepless

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

Answer 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']]

Knack

Answer 3

For Deep understanding, you can consider my code (It is easy and most understandable)

I hope you understand it :)

from pprint import pprint

print("Input 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"]]

pprint(matrix)

# USER INPUT 
row = 3
col = 1

given_item = matrix[row][col]

# MASK PATTERN 
mask = "c"


print("\n")
print("Changing only inner matrix items and skiping items where index is Negative := ")
if (row + col+1) >= 0:
  right = matrix[row][col+1]
  print("right")
else:
  right = "NA"


if (row + col-1) >= 0:
  left = matrix[row][col-1]
  print("left")
else:
  left = "NA"

if (row-1 + col) >= 0:
  top = matrix[row-1][col]
  print("top")
else:
  top = "NA"

if (row+1 + col) >= 0:
  bottom = matrix[row+1][col]
  print("bottom")
else:
  bottom = "NA"


pattern = f"""
            {top}
          {left} {given_item} {right}
            {bottom}
          """

print(pattern)

if right == given_item:
  print(f"masking right {mask}")
  matrix[row][col+1] = mask

if left == given_item:
   print(f"masking left {mask}")
   matrix[row][col-1] = mask

if top == given_item:
   print(f"masking top {top}")
   matrix[row-1][col] = mask

if bottom == given_item:
   print(f"masking bottom {bottom}")
   matrix[row+1][col] = mask

matrix[row][col] = mask

del right
del left
del top
del bottom 

print("Output Matrix :")
pprint(matrix)

Output:= row:3 , col : 1

Input 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']]


Changing only inner matrix items and skiping items where index is Negative := 
right
left
top
bottom

            a
          b a b
            a
          
masking top a
masking bottom a
Output Matrix :
[['a', 'a', 'b', 'a', 'a', 'b'],
 ['a', 'b', 'b', 'a', 'b', 'b'],
 ['b', 'c', 'b', 'a', 'a', 'b'],
 ['b', 'c', 'b', 'a', 'b', 'b'],
 ['a', 'c', 'b', 'a', 'a', 'a'],
 ['a', 'b', 'b', 'a', 'a', 'b']]

Output := row :0 , col :0

Input 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']]


Changing only inner matrix items and skiping items where index is Negative := 
right
bottom

            NA
          NA a a
            a
          
masking right c
masking bottom a
Output 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']]

Parathion

Answer 4

Here is a floodfill that uses an array instead of recursion so you wont blow a stack

#########################################################################
# FloodFill
#
# flood fill a bitmap given a start point
# uses an array instead of recursion
#########################################################################
def FloodFill(bitmap: list[list[tuple]], point: tuple) -> None:
    i: int = 0
    length: int = 1
    fillQue: list[tuple] = [point]

    maxRow = len(bitmap)
    maxCol = len(bitmap[0])

    while i < length:
        r: int = fillQue[i][0]
        c: int = fillQue[i][1]
        i += 1

        if r < 0 or r >= maxRow or c < 0 or c >= maxCol:
           continue

        if bitmap[r][c] == 0:
            bitmap[r][c] = 2

            fillQue.append((r, c + 1))
            fillQue.append((r + 1, c))
            fillQue.append((r, c -1))
            fillQue.append((r -1, c))
            
            length += 4

Hibbard