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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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)