In C language , Image editing programs often use the “flood fill” algorithm to f
ID: 3905165 • Letter: I
Question
In C language , Image editing programs often use the “flood fill” algorithm to fill similarly colored connected areas with a new color. Suppose that the two-dimensional 8×8 array of Figure 11.4a represents the pixels of an image, where 0 represents the black color, 1: white, 2: red, 3: green, and 4: blue, while a pixel is similarly colored connected with another, if they have the same color and it is adjacent to it. The similarly colored areas are depicted in Figure 11.4b.
To implement the “flood fill” algorithm, write a recursive floodfill() function which change the color (i.e., c) of a pixel at a location (i.e., i, j) to a new color (i.e., nc) and then it changes the color of its neighbouring pixels (i.e., the pixels to the left, right, above, and below the pixel at (i, j)) whose color is also c. This process continues recursively on the neighbours of the changed pixels until there are no more pixel locations to consider.
For example, if we choose to change the color of the pixel in the position 0, 0 from black (i.e., 0) to green (i.e., 3), the color of the top-left area of four pixels changes to green, as shown in Figure 11.4c.
Write a program that creates a two-dimensional 8×8 array of integers and assigns to its elements random values in [0, 4]. Then, the program should read the location of a pixel and a new color and use floodfill() to change the existing color of its similarly colored area with the new one.
Explanation / Answer
Hello Student!
I am happy to help you.
Here goes the solution :
#include<stdio.h>
// Array size as per question
#define N 8
// Flood fill algo - A recursive function to replace
// previous color 'prevC' at '(x, y)' and surrounding with
// new colour
void floodFillRecr(int arr[][N], int x, int y, int prevColor, int newColor) {
// Base cases
if (x < 0 || x >= N || y < 0 || y >= N)
return;
if (arr[x][y] != prevColor)
return;
// Replace the color at (x, y)
// and after that call recursively
arr[x][y] = newColor;
// Now call recursively and replace the color of
// the side position with the newcolor
floodFillRecr(arr, x+1, y, prevColor, newColor);
floodFillRecr(arr, x-1, y, prevColor, newColor);
floodFillRecr(arr, x, y+1, prevColor, newColor);
floodFillRecr(arr, x, y-1, prevColor, newColor);
}
// It mainly finds the previous color on (x, y) and
// calls floodFillUtil()
void floodFill(int arr[][N], int x, int y, int newColor) {
int prevColor = arr[x][y];
floodFillRecr(arr, x, y, prevColor, newColor);
}
int main() {
int arr[N][N] = {{1, 1, 4, 1, 1, 1, 4, 4},
{1, 1, 1, 1, 2, 2, 0, 0},
{1, 0, 0, 1, 1, 0, 2, 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, 4, 1, 1, 2, 1, 1},
{1, 4, 1, 1, 1, 2, 2, 4},
};
int x , y, newColor ;
printf("Enter the pixel location : %d %d ", x, y);
printf("Enter the new color : %d ", newColor);
floodFill(arr, x, y, newColor);
printf ("Updated arr after call to floodFill: ");
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
printf("%d ", arr[i][j] );
}
printf(" ");
}
}
Test case output :
Thank you. Feel free to ask anything. If, you like the answer please upvote. Thank you again