Flood Fill Algorithm

Photo by Joshua Reddekopp on Unsplash

We all have used Microsoft paint or similar software in our childhood. There we used to have a tool named fill colour in the shape of a bucket. Whenever we take that too to a bounded region and click it with the desired colour, the area would get coloured with the requires colour. This sparked the curiosity in me that what makes this feature possible and how does it recognise the area to be coloured.

Explanation

Let's have a look at the following scenario.

Here we have to colour the area A in the following figure as shown. The moment we take our fill colour tool, it gets transformed into this. The tool automatically senses the bounded area and colours the required area.

Let's Visualise this

We all know that 8-bit displays are prevalent in today's world even though professionals use 10-bit and 16-bit raw images also. these bits contain information such as RGB values, depth, contrast etc.

Here we can see a 16-bit image at the top without any banding effect whereas an 8-bit image at the bottom has a very evident banding effect. For simplicity, let's take a coloured pixel as 1 and a blank pixel as 0. So we will have the following resultant picture

Here we need to take an initial seed position (x,y) inside the area we want to colour. Now, we will take our filler and apply it to the seed position.

This Plus shaped filler will select (x+1,y) ,(x,y+1) ,(x,y) ,(x-1,y) and (x,y-1) pixels and check whether they are coloured or not. if they not, They get coloured else they are left unaltered.

After some steps, our image looks like this

Here the inner pixels are being coloured with the filler. But an interesting question arises at this point. why is filler having a plus shape and not having diagonal components?

Technically adding diagonal components will increase the area of filler and make it more efficient but it has a disadvantage. Let's see

Here if we apply filler at Y, by the virtue of diagonal components in our filler, position X will also be coloured but here as we can see, X lies outside of our area and should not be altered. Hence we don't take diagonal components for our filler.

PSEUDO CODE

The following algorithm can be implemented both in a recursive and iterative manner.

Let's have a look at the Pseudo Code for recursive implementation

// A recursive function to replace
// previous color ‘prevColor’ at ‘(x, y)’
// and all surrounding pixels of (x, y)
// with new color ‘newColor’ and
floodFil(screen[M][N], x, y, prevC, newC)
1) If x or y is outside the screen, then return.
2) If color of screen[x][y] is not same as prevC, then return
3) Recur for north, south, east and west.
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);

The time complexity of the flood fill algorithm is O(N*M) and 0(N²) if M=N.

IMPLEMENTATION

Following is the implementation of this algorithm in C++.

// A C++ program to implement flood fill algorithm
#include<iostream>
using namespace std;

// Dimentions of paint screen
#define M 8
#define N 8

// A recursive function to replace previous color ‘prevC’ at ‘(x, y)’
// and all surrounding pixels of (x, y) with new color ‘newC’ and
void floodFillUtil(int screen[][N], int x, int y, int prevC, int newC)
{
// Base cases
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (screen[x][y] != prevC)
return;
if (screen[x][y] == newC)
return;

// Replace the color at (x, y)
screen[x][y] = newC;

// Recur for north, east, south and west
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);
}

// It mainly finds the previous color on (x, y) and
// calls floodFillUtil()
void floodFill(int screen[][N], int x, int y, int newC)
{
int prevC = screen[x][y];
floodFillUtil(screen, x, y, prevC, newC);
}

// Driver code
int main()
{
int screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
int x = 4, y = 4, newC = 9;
floodFill(screen, x, y, newC);

cout << “Updated screen after call to floodFill: \n”;
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
cout << screen[i][j] << “ “;
cout << endl;
}
}

Here, we start with an initial seed of 4,4. Our goal is to change all the pixels with an initial value of 2 to the value 9. Here, the final result looks like this

Here, we can clearly see that all the places where the value was 2 inscribed in the required area have been changed with the new value of 9.

Advantages -

• Flood Fill overs the entire area in an enclosed figure through interconnected pixels with the same RGB value
• Simple Implementation
• Can be used in vectorized images to fill the same colour in any area regardless of its shape and size.

Disadvantages -

• Uses A lot of memory
• Not effective for large polygons as it may hamper with cache memory
• High time complexity.
• Most filled pixels are checked 4 times which decreases their efficiency

Real-World Usage -

• Bucket Fill in Paint
• Maze solving
• Minesweeper game