5 Best Ways to Implement a Flood Fill with Color in Python

by

💡 Problem Formulation: You need to dynamically fill an area in a data structure, such as an image or a grid, with a specific color. This process is known as a flood fill operation. For instance, imagine a digital image as a 2D matrix with each cell representing a pixel; the goal is to change the color of an area connected to a given pixel (x,y) to a new specified color.

Method 1: Recursive Flood Fill

The recursive method implements the flood fill algorithm by calling a function recursively to color an area connected to a specified pixel. The base case for the recursion is when the pixel is already the target color or is a border color that should not be changed.

Here’s an example:

def flood_fill_recursive(image, x, y, newColor, oldColor=None):
    if oldColor is None:
        oldColor = image[x][y]
    if oldColor == newColor or image[x][y] != oldColor:
        return
    image[x][y] = newColor
    if x > 0: flood_fill_recursive(image, x-1, y, newColor, oldColor)
    if y > 0: flood_fill_recursive(image, x, y-1, newColor, oldColor)
    if x < len(image)-1: flood_fill_recursive(image, x+1, y, newColor, oldColor)
    if y < len(image[0])-1: flood_fill_recursive(image, x, y+1, newColor, oldColor)

#An example usage
grid = [[1,1,1],[1,1,0],[1,0,1]]
flood_fill_recursive(grid, 1, 1, 2)
print(grid)

Output:

[[2, 2, 2], [2, 2, 0], [2, 0, 1]]

This code replaces all connected cells that have the same color as the original color at the starting cell (1,1) to the new color, 2. The function checks adjacent cells (up, down, left, right) and calls itself recursively to color all the connected areas. This method can lead to a maximum recursion depth error on large data.

Method 2: Stack-Based Flood Fill

The stack-based method uses a data stack to perform the flood fill algorithm iteratively. This avoids the potential stack overflow issue of the recursive approach by using your own stack on the heap instead of the call stack.

Here’s an example:

def flood_fill_stack(image, x, y, newColor):
    oldColor = image[x][y]
    if oldColor == newColor:
        return image
    stack = [(x, y)]
    while stack:
        x, y = stack.pop()
        if image[x][y] == oldColor:
            image[x][y] = newColor
            if x > 0: stack.append((x-1, y))
            if y > 0: stack.append((x, y-1))
            if x < len(image)-1: stack.append((x+1, y))
            if y < len(image[0])-1: stack.append((x, y+1))
    return image

#An example usage
grid = [[1,1,1],[1,1,0],[1,0,1]]
flood_fill_stack(grid, 1, 1, 2)
print(grid)

Output:

[[2, 2, 2], [2, 2, 0], [2, 0, 1]]

This method iteratively changes the color of connected pixels using an explicit stack to track the pixels that need to be updated. It’s an effective approach for large images because it bypasses the risk of stack overflow associated with recursive algorithms.

Method 3: Breadth-First Search (BFS) Flood Fill

BFS flood fill uses a queue to perform the flood fill algorithm layer by layer. This approach often traverses fewer nodes than depth-first strategies such as stack-based and recursive methods when dealing with large, connected areas.

Here’s an example:

from collections import deque

def flood_fill_bfs(image, x, y, newColor):
    oldColor = image[x][y]
    if oldColor == newColor:
        return image
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        if image[x][y] == oldColor:
            image[x][y] = newColor
            if x > 0: queue.append((x-1, y))
            if y > 0: queue.append((x, y-1))
            if x < len(image)-1: queue.append((x+1, y))
            if y < len(image[0])-1: queue.append((x, y+1))
    return image

#An example usage
grid = [[1,1,1],[1,1,0],[1,0,1]]
flood_fill_bfs(grid, 1, 1, 2)
print(grid)

Output:

[[2, 2, 2], [2, 2, 0], [2, 0, 1]]

This example uses a queue to iteratively visit and update pixels in a breadth-first manner, colorizing all contiguous pixels with the old color until the entire area is filled with the new color. This method ensures a broader coverage before going deeper and can be more memory efficient on some datasets.

Method 4: OpenCV Library

OpenCV is a highly optimized library that includes methods specifically for image processing tasks, including a flood fill operation. Utilizing OpenCV can lead to more efficient and concise code, particularly for image data.

Here’s an example:

import cv2
import numpy as np

# Create an example image
image = np.array([[1,1,1],[1,1,0],[1,0,1]]).astype(np.uint8)
newColor = 2

# Coordinates of the seed point
x, y = 1, 1

# Apply the floodFill operation
cv2.floodFill(image, None, (y, x), newColor)

print(image)

Output:

[[2 2 2]
 [2 2 0]
 [2 0 1]]

In this example, OpenCV’s floodFill function is used to replace the color. The function parameters include the image to be modified, a mask, the seed point’s coordinates, and the new color. OpenCV handles the low-level implementations, making this method fast and robust for practical applications.

Bonus One-Liner Method 5: Using NumPy

For simple cases with 2D arrays, NumPy can be employed to perform operations that resemble a flood fill by directly manipulating the array.

Here’s an example:

import numpy as np

def numpy_flood_fill(image, x, y, newColor):
    oldColor = image[x,y]
    image[image == oldColor] = newColor
    return image

#An example usage
grid = np.array([[1,1,1],[1,1,0],[1,0,1]])
numpy_flood_fill(grid, 1, 1, 2)
print(grid)

Output:

[[2 2 2]
 [2 2 0]
 [2 0 1]]

This one-liner approach uses NumPy’s powerful array indexing to change the color of all elements in the array that have the same value as the element at the given coordinates. Note that this doesn’t consider connectivity and changes all matching elements regardless of their position.

Summary/Discussion

  • Method 1: Recursive Flood Fill. Simple and straightforward. Susceptible to maximum recursion depth errors on large data sets.
  • Method 2: Stack-Based Flood Fill. Iterative and capable of handling larger images without stack overflows. Slightly more complex implementation than the recursive approach.
  • Method 3: BFS Flood Fill. Executes a flood fill layer by layer using a queue. It often accesses fewer nodes and can be more memory-efficient on specific data sets.
  • Method 4: OpenCV Library. Highly efficient for image processing. Requires external library installation but provides fast and robust flood filling capabilities.
  • Bonus Method 5: Using NumPy. Quick and easy for simple scenarios. Doesn’t account for connectivity, which may not be suitable for all flood fill situations.