Flood Fill Algorithm in Computer Graphics

In this blog, we have covered everything you need to know about the flood fill algorithm. It will help you understand how the flood fill algorithm works and how we can implement it in code. We will also discuss the advantages and disadvantages of this algorithm.

Learn data structures and algorithms from this comprehensive video course:

What is the Flood Fill Algorithm?

The flood fill algorithm is a technique that is used in computer graphics to fill enclosed areas with a particular color. It starts with a pixel that we define as the start point and changes its color; after that, it proceeds by recursively visiting the starting pixel’s neighboring pixels and changing their color if they belong to the same area and have the same initial color. This process continues until all pixels in the enclosed area have been visited and filled with color. Flood fill is often used in paint programs to fill bounded regions with a specific color or pattern. It’s also utilized in various image processing and computer graphics applications for region filling and boundary detection.

Here are some characteristics of the flood fill algorithm that one must be aware of:

• Time Complexity: O(n), where n is the number of pixels in the region to be filled.
• Space Complexity: O(n) is the worst case space complexity for recursive implementations due to the use of stack data structures.
• Choice of Data Structure: Recursive implementation uses a stack data structure, while iterative implementation uses a queue or list.

These algorithms form the backbone of computer graphics, enabling the creation, manipulation, and rendering of visual content on computer screens and facilitating the development of diverse applications and experiences in various fields.

Join the Full Stack Developer Course to enhance your expertise. 

How Does the Flood Fill Algorithm Work?

The flood fill algorithm works by starting with a given pixel in an image and systematically examining neighboring pixels to determine whether they should be filled with a new color or pattern. The flood fill algorithm follows a depth-first search (DFS) or breadth-first search (BFS) approach to traverse through pixels and fill the enclosed area with the desired color. It is significant to implement boundary checks to avoid infinite loops and ensure that the algorithm terminates correctly.

Here are the basic steps of how the algorithm works:

Step 1: Picking Starting Pixels: The algorithm begins by choosing a starting pixel within the image that needs to be filled.

Step 2: Changing the Color of the Starting Pixel: Then, the starting pixel’s color is changed to the new desired color.

Step 3: Traversal of Neighboring Pixels: Then, it will examine the neighboring pixels of the starting pixel. For each neighbor, it checks if it’s within the bounds of the image and has the same color as the starting pixel’s original color.

Step 4: Changing the Color of Neighboring Pixels: If a neighboring pixel meets the criteria (same color as the starting pixel’s original color and within image bounds), it’s colored with the new color.

Step 5: Repetition of Step 4: This process continues recursively (using a stack or recursive function calls) or iteratively (using a queue or loop) for all eligible neighboring pixels.

Step 6: Final Filling of All Pixels: The algorithm keeps expanding outward and examines the neighboring pixels of the newly filled pixels. This process is continued until all pixels within the enclosed area with the original color have been filled with the new color.

Do you want a comprehensive list of interview questions? Here are the Full Stack Developer Interview Questions!

Pseudo Code of Flood Fill Algorithm

Here is a basic pseudo-code representation of the flood fill algorithm using a recursive approach:

procedure floodFill(x, y, newColor, originalColor):

    if pixel (x, y) is within image bounds and has originalColor:

        set pixel (x, y) to newColor

        floodFill(x + 1, y, newColor, originalColor)  // Check right neighbor

        floodFill(x - 1, y, newColor, originalColor)  // Check left neighbor

        floodFill(x, y + 1, newColor, originalColor)  // Check bottom neighbor

        floodFill(x, y - 1, newColor, originalColor)  // Check top neighbor

Let’s now understand how the above pseudocode works:

• ‘floodFill’ is a recursive function that starts at coordinates ‘(x, y)’ in the image.
• It checks if the pixel at ‘(x, y)’ is within the image bounds and has the ‘originalColor’.
• If true, it changes the pixel color to ‘newColor’ and recursively calls ‘floodFill’ on its neighboring pixels (right, left, bottom, top) to fill the enclosed area.
• This process continues until all adjacent pixels within the enclosed area with the ‘originalColor’ have been filled with the ‘newColor’.

Example of a Flood Fill Algorithm

This example demonstrates how to use the ‘flood_fill’ function to perform flood fill on a 2D matrix by replacing the target color (0 in this case) with the replacement color (2 in this case) starting from the specified coordinates ‘(start_x, start_y)’:

def flood_fill(matrix, x, y, target_color, replacement_color):

    # Check if the coordinates are within the matrix boundaries

    if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]):

        return

    # Check if the current cell has the target color

    if matrix[x][y] != target_color:

        return

    # Apply replacement color to the current cell

    matrix[x][y] = replacement_color

    # Apply flood fill to adjacent cells

    flood_fill(matrix, x + 1, y, target_color, replacement_color)  # Right

    flood_fill(matrix, x - 1, y, target_color, replacement_color)  # Left

    flood_fill(matrix, x, y + 1, target_color, replacement_color)  # Down

    flood_fill(matrix, x, y - 1, target_color, replacement_color)  # Up

# Example usage

matrix = [

    [1, 1, 1, 1, 1],

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

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

    [1, 1, 1, 1, 1],

]

start_x = 1

start_y = 2

target_color = 0

replacement_color = 2

flood_fill(matrix, start_x, start_y, target_color, replacement_color)

# Displaying the modified matrix after flood fill

for row in matrix:

    print(row)

In the above code, the Python function ‘flood_fill’ implements the flood fill algorithm recursively. It takes a ‘matrix’ as input, along with the coordinates ‘(x, y)’ where the flood fill should start, the ‘target_color’ to be replaced, and the ‘replacement_color’ to be applied. This function checks the boundaries of the matrix and the color of the current cell. If the current cell matches the target color, it replaces it with the replacement color and recursively performs flood fill on adjacent cells in four directions: right, left, down, and up.

Advantages and Disadvantages of the Flood Fill Algorithm

The flood fill algorithm is a very useful tool for image processing and graphics applications, but it is also important to consider its limitations and potential drawbacks to ensure efficient and accurate results. Here is a brief comparison of the pros and cons of the flood fill algorithm:

Also, read our blog on boundary fill algorithms, and master computer graphics.

Conclusion

The flood fill algorithm is a fundamental technique in computer graphics that efficiently fills enclosed areas with a specific color or pattern. Through recursive traversal of neighboring pixels, starting from a chosen point, it systematically changes their colors until the entire enclosed region is filled. This versatile algorithm is widely used in applications of paint tools, image processing, and graphics software. Its simplicity and effectiveness make it an efficient tool for boundary detection, region filling, and various other graphical applications that help in the manipulation and enhancement of digital images and graphics with precision.

Do you still have queries? You can post your doubts on our Community Page.