We all are known to the “Bucket” tool of Microsoft Paint which is used
to fill an area with single specific color. But do we know how it actually
works? Well, Let’s discuss this.
to fill an area with single specific color. But do we know how it actually
works? Well, Let’s discuss this.
Yeah you read it right. We are going to discuss the algorithm behind the bucket tool. And this particular algorithm is known as Flood Fill Algorithm.
Problem Description:
A two dimensional array will be given with all the different color values in it. The starting point and the new color value will also be given. All we need to do is to fill the section with the new color where the bucket tool is clicked. We can consider the following image as an example.
We can represent the above images with two dimensional arrays.
Here the Green color is represented with the value 1, Red color with the value 2, Yellow color with the value 3 and Orange color with the value 4 in it. Now we have to take the bucket tool and select a new color and if we click on the red section, it will be colored with the new selected color. Let the new color is Blue and its value is 5.
How to solve:
We need to find the pixels with red color values, means the indexes with the value 2 and then replace them with the new color. We will solve this problem using a Recursive Function.
A function that calls itself during execution is known
as Recursive Function.
If we have clear concept on Recursion or Recursive Function, then the problem is very easy to solve.
Let, the image matrix as image[row][col] and the starting position is (2,4). So, we will start checking from the position image[2][4]. The idea is simple. At first we replace the color of current pixel and then we will go in 8 directions(N, S, W, E, NW, NE, SW, SE) and convert all the previous color values into the new color values.
//Pseudo code of the recursive function
floodFill(image[row][col], x, y, prevColor, newColor)
1. If x or y is outside the image, then return.
2. If image[x][y] is not same as previous color value, then return.
3. Call the function for north, south, east, west, north-west, north-east, south-west, south-east.
FloodFill(image, x+1, y, prevColor, newColor);
FloodFill(image, x, y+1, prevColor, newColor);
FloodFill(image, x-1, y, prevColor, newColor);
FloodFill(image, x, y-1, prevColor, newColor);
FloodFill(image, x+1, y+1, prevColor, newColor);
FloodFill(image, x+1, y-1, prevColor, newColor);
FloodFill(image, x-1, y+1, prevColor, newColor);
FloodFill(image, x-1, y-1, prevColor, newColor);Then we will get the image with new color.
Implemention :
The following is the implementation of above algorithm.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int image[1000][1000];
int row,col;
bool valid(int i,int j)
{
if(i<0 || i>=row || j<0 || j>=col)
return false;
else
return true;
}
void floodFill(int x, int y, int prevColor, int newColor)
{
if(valid(x,y) == false) //Base Case
return;
if(image[x][y] != prevColor)
return;
if(image[x][y] == newColor)
return;
if(image[x][y] == prevColor)
image[x][y] = newColor; //Converting the previous color into new color
floodFill(x-1,y,prevColor,newColor);
floodFill(x+1,y,prevColor,newColor);
floodFill(x,y-1,prevColor,newColor);
floodFill(x,y+1,prevColor,newColor);
floodFill(x-1,y-1,prevColor,newColor);
floodFill(x-1,y+1,prevColor,newColor);
floodFill(x+1,y-1,prevColor,newColor);
floodFill(x+1,y+1,prevColor,newColor);
}
int main()
{
int x, y, prevColor, newColor;
cout<<"Enter row and column number for the image matrix : ";
cin>>row>>col;
cout<<"Enter the image matrix : "<<endl;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
cin>>image[i][j];
}
}
cout<<"Enter the starting position : ";
cin>>x>>y;
cout<<"Enter the new color value : ";
cin>>newColor;
prevColor = image[x-1][y-1];
floodFill(x,y,prevColor,newColor);
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
cout<<image[i][j]<< " ";
}
cout<<endl;
}
return 0;
}Again we can be asked for calculating the number of pixels each color covers. We can solve this problem simply using the Flood Fill Algorithm.
Implementation of this problem is here.
Implementation of this problem is here.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int cnt = 0, row, col;
int image[1000][1000];
bool visited[1000][1000];
int res[1000];
bool valid(int i,int j)
{
if(i<0 || i>=r || j<0 || j>=c)
return false;
else
return true;
}
void floodFill(int i, int j, int idxValue)
{
if(valid(i,j) == false) //Base case
return;
if(image[i][j] != idxValue)
return;
if(image[i][j] == idxValue)
cnt++;
visited[i][j] = 1; //Current node is marked as visited.
image[i][j] = -100;
floodFill(i-1,j,idxValue);
floodFill(i+1,j,idxValue);
floodFill(i,j-1,idxValue);
floodFill(i,j+1,idxValue);
floodFill(i-1,j-1,idxValue);
floodFill(i-1,j+1,idxValue);
floodFill(i+1,j-1,idxValue);
floodFill(i+1,j+1,idxValue);
}
int main()
{
memset(visited, 0, sizeof visited);
cin>>row>>col;
set <int> st;
set <int> :: iterator it;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
cin>>image[i][j];
}
}
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(visited[i][j]==0 && image[i][j]>=0)
{
cnt = 0;
int x = image[i][j];
floodFill(i,j,image[i][j]);
int retCount = cnt;
res[x] += retCount; //Storing the pixel counts.
}
}
}
for(int i=0;i<1000;i++)
{
if(res[i]>0)
cout<<"The color with value "<<i<<" covers "<<res[i]<<" pixels."<<endl;
}
return 0;
}Input :
5 7
1 1 1 1 2 2 2
1 1 1 1 2 2 2
1 1 1 1 2 2 2
1 1 1 1 3 3 3
1 1 1 1 3 3 3
Output :
The color with value 1 covers 20 pixels.
The color with value 2 covers 9 pixels.
The color with value 3 covers 6 pixels.
This is all about Flood Fill Algorithm. For any type of confusion I would request you to ask questions in comment section.
Stay Home. Stay Safe.
Happy Coding!