The Flood Fill algorithm is a simple but important technique that is used in computer graphics and image processing. It starts from a given pixel and fills a connected region of pixels with a new color, based on their similarity to the starting pixel. The algorithm recursively or iteratively visits neighboring pixels and changes their color until the entire connected region is filled, which makes it useful for tasks like filling shapes, removing backgrounds, or replacing colors in images. In this article, we’ll discuss all the methods, including brute force, and the most efficient way to solve this problem.
What is the Flood Fill Algorithm?
Flood fill, also known as seed fill, is a flooding algorithm that chooses and modifies the region in a multidimensional array associated to a specific node with a particular attribute. It is used in games like Go and Minesweeper to determine which pieces are cleared as well as in paint applications' "bucket" fill tool to fill connected, similarly colored areas with a distinct color.
The area connected to a given node but lacking a specific characteristic is what is meant by the variation known as border fill, which uses the same techniques. It should be noted that flood filling is not appropriate for creating filled polygons because it will miss some pixels in more sharp corners.
How does it work?
The solution is usually straightforward and consists of the following steps:
Consider the beginning point's location
Choose whether to travel in four directions (N, S, W, E) or eight directions (N, S, W, E, NW, NE, SW, SE)
Select a replacement and a target color
Go in those directions
If you land on a target tile, replace it with the desired color
Repeat steps 4 and 5 until you've visited every location inside the borders
Problem Statement For Flood Fill Algorithm
You are given a 2D screen arr[][] where each arr[i][j] is an integer representing the colour of that pixel, also given the location of a pixel (X, Y) and a new colour C. Your task is to replace the colour of the given pixel and all adjacent same-coloured pixels with the new colour.
Note: Here the Adjacent positions are (left, right, down, up), i.e. (x-1,y), (x+1,y), (x,y+1) and (x,y-1) respectively.
Let’s see the below example to understand the problem statement better:
Given array is a 2-D array of order (3*3), and the location of the pixel provided is (1,1).
The pixel’s colour is ‘1,’ and the new colour to be changed is ‘2.
Solution
1. Note the pixel location; its colour is ‘1,’ and the new colour to be changed is ‘2.’2. So, first, change the colour of the pixel at location (1,1).3. Now, check the adjacent locations with the same colour and replace them with ‘2.’4. So, following this procedure the colour of pixels at locations (0,0), (0,1), (0,2), (1,0), (1,1), (2,0) will be changed.
You might wonder why the colour of the pixel at location (2,2) is not changed?
The reason is that location (2,2) is not adjacent to the provided location by any means so, it will not be changed.
If the idea behind solving the problem is clear, let’s head on to the methods to solve the “Flood fill Algorithm” problem.
Method 1: Brute force (Using Recursion)
Here, the idea will be that we will first replace the colour of a given pixel’s location and then call the function recursively to change all the adjacent pixels with the same colour.
Algorithm For Brute Force
Let us assume that the position of the pixel is given as (x,y).
If any of ‘x’ or ‘y’ is outside the screen, simply return.
Also, if the screen colour at location (x,y) is the same as the provided colour (in this case, the provided colour is 2), then return.
Else, change the colour of the given location pixel and call the function recursively for its adjacent positions (left ,right,down,up), i.e. on(x-1,y), (x+1,y), (x,y+1) and (x,y-1) respectively.
Remember, diagonal positions are not adjacent.
Below, C++ code is given for your better understanding:
Code for Brute Force
C++
C++
#include<iostream> using namespace std; //make the dimensions as you wish #define M 3 #define N 3
void floodFillAlgo(int arr[M][N], int x, int y, int preColor, int newColor) { // if x or y is out of the screen if (x < 0 || x >= M || y < 0 || y >= N) return; //if the colour already at position is not the same as the previous colour if (arr[x][y] != preColor) return; //if the colour is already the same as the new colour if (arr[x][y] == newColor) return;
// Replace the colour at (x, y) arr[x][y] = newColor;
//Call the function recursively for the adjacent positions floodFillAlgo(arr, x+1, y, preColor, newColor); floodFillAlgo(arr, x-1, y, preColor, newColor); floodFillAlgo(arr, x, y+1, preColor, newColor); floodFillAlgo(arr, x, y-1, preColor, newColor); }
//Function to know what the previous colour was void Fill(int arr[M][N], int x, int y, int newColor) { int preColor = arr[x][y]; //check if the previous colour is not the same as the new colour if(preColor==newColor) return; //if the colour asked is different floodFillAlgo(arr, x, y, preColor, newColor); }
int main() { int arr[M][N] = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1},}; int x = 1, y = 1, newColor = 2; Fill(arr, x, y, newColor);
cout <<"The screen after implementing the Flood fill algo will be: \n"; for (int i=0; i<M; i++) { for (int j=0; j<N; j++) cout << arr[i][j] << " "; cout << endl; } }
You can also try this code with Online C++ Compiler
The screen after implementing the Flood fill Algo will be:
2 2 2
2 2 0
2 0 1
Complexity Analysis for Brute Force
Time Complexity: O(M*N)
It will be proportional to the number of pixels in the filled area. So, at max M*N pixels can be traversed. Here, M and N are the numbers of rows and columns, respectively.
Thus, the complexity will be O(M*N).
Space Complexity: O(M*N)
Here, M and N are the numbers of rows and columns respectively.
In the worst case, O(M * N) extra space is required by the recursion stack. Hence the overall space complexity is O(M * N).
Here in this method to implement the Flood fill algorithm, we will use the idea of “Breadth-First Search.”
Algorithm For BFS Approach
Create a queue that will have pairs.
Create a Matrix (Visit[M][N]).
Insert the provided location as the initial index into the queue.
Now, mark the initial index as visited in a newly created Visit Matrix.
While the queue is not empty, follow the below steps:
Pop-out the first element from the queue.
Store this value as this would act like the previous colour of the pixel at that location.
Now change the colour of the index that is being popped out from the queue.
Check for its all possible adjacent indexes (x,y+1), (x,y-1), (x+1,y) and (x-1,y) whether they exist or not.
If yes, then check the colour at that index, and it should be equal to the previous colour since it is not changed, so its value in the Visited Matrix should be ‘0’ as it is not visited yet.
Now, if all steps are true, push the index or location into the queue and mark its corresponding position in the Visited Matrix as ‘1’.
Print out the matrix after the above implementation for the flood fill algorithm.
Below is the C++ code for your better understanding:
Code for BFS Approach
C++
C++
#include <bits/stdc++.h> using namespace std;
//check if the coordinate is valid or not int checkCoord(int x, int y, int N, int M) { if (x < 0 || y < 0) { return 0; } if (x >= N || y >= M) { return 0; } return 1; }
//Using BFS to implement flood fill algo void BFS(int N, int M, int arr[3][3], int x, int y, int newcolour) { //array to mark visited and non visited by 1 and 0 respectively int visit[100][100];
// Initialing all to zero means non visited memset(visit, 0, sizeof(visit));
// Creating queue for bfs queue<pair<int, int> > q;
// Pushing the given index as (x, y) q.push({ x, y });
// Mark (x, y) as visited visit[x][y] = 1;
// Until queue is not empty while (q.empty() != 1) {//taking out queue front pair<int, int> coor = q.front(); int x = coor.first; int y = coor.second; int preColor = arr[x][y]; //changing the colour to newcolour arr[x][y] = newcolour;
// Poping front pair of queue q.pop();
// check for upper pixel if (checkCoord(x + 1, y, N, M) && visit[x + 1][y] == 0 && arr[x + 1][y] == preColor) { q.push({ x + 1, y }); visit[x + 1][y] = 1; }
// check for down pixel if (checkCoord(x - 1 , y , N , M) && visit[x - 1][y] == 0 && arr[x - 1][y] == preColor) { q.push({ x - 1, y }); visit[x - 1][y] = 1; }
//check for Right side pixel if (checkCoord(x, y + 1, N, M) && visit[x][y + 1] == 0 && arr[x][y + 1] == preColor) { q.push({ x, y + 1 }); visit[x][y + 1] = 1; }
//check for Left side Pixel if (checkCoord(x, y - 1, N, M) && visit[x][y - 1] == 0 && arr[x][y - 1] == preColor) { q.push({ x, y - 1 }); visit[x][y - 1] = 1; } } //print the final matrix after change cout<<"Final screen after implementing flood fill algo will be:"<<endl; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cout << arr[i][j] <<" "; } cout << endl; } cout << endl; }
int main() { int N, M, x, y, newcolour; N = 3; M = 3;
int arr[3][3] = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}, }; x = 1, y = 1, newcolour = 3;
BFS(N, M, arr, x, y, newcolour); return 0; }
You can also try this code with Online C++ Compiler
Final screen after implementing flood fill algo will be:
3 3 3
3 3 0
3 0 1
Complexity Analysis For BFS Approach
Time Complexity: O(M*N)
Here, M and N are the numbers of rows and columns, respectively.
In the worst case, each pixel or element of the screen or array may be traversed hence, making the complexity to the order of (M*N).
Space Complexity: O(M*N)
Here, M and N are the numbers of rows and columns in the image, respectively.
In the worst case, O(M * N) extra space is required by the queue. Hence the overall space complexity is O(M * N).
Note: If you’ve ever used the bucket fill tool in MS paint or photo editing software like Photoshop or Gimp, you’re already familiar with the flood fill algorithm.
That’s shocking, isn’t it? Because you may not have realised it previously.
Indeed learning these algorithms is critical if you want to work in software companies as a technophile because you are constantly surrounded by them unknowingly.
Frequently Asked Questions
What is a real-life example of a flood fill algorithm?
A real-life example of the flood fill algorithm is the "bucket fill" tool in graphic design software like Adobe Photoshop. This tool fills all connected pixels of a similar color with a new color, effectively recoloring an area in an image.
Is the flood fill algorithm recursive?
Yes, the flood fill algorithm can be implemented recursively. It repeatedly applies the fill operation to neighboring pixels until all connected pixels of the target color have been changed, using recursive calls to spread to adjacent pixels.
Is flood fill the same as BFS?
Flood fill is not the same as Breadth-First Search (BFS), but it can utilize BFS principles. While BFS explores nodes level by level, flood fill specifically targets and alters the colors of connected components in graphics.
What does it mean by a non-recursive flood fill algorithm?
You can implement the BFS approach of flood fill algorithm non-recursively by taking the help of an implicit stack.
Conclusion
The flood fill algorithm is a multi-dimensional array technique that determines a bounded area associated with a given node. It is similar to the bucket tool in paint programs. The flood fill algorithm has numerous applications, including image segmentation, image editing, and solving problems like maze traversal or connected component labeling. Its simplicity and effectiveness make it a valuable tool in various domains. Implementing the flood fill algorithm requires careful consideration of boundary conditions and stack or queue data structures to efficiently manage the pixel visits and ensure a complete and accurate fill operation.