COMPUTER GRAPHICS - Implement Area Filling Algorithm: Boundary Fill, Flood Fill.

 Experiment No.03

Aim: Implement Area Filling Algorithm: Boundary Fill, Flood Fill.

Prerequisite:C Language

Outcome: After successful completion of this experiment students will be able to Implement various output and filled area primitive algorithms

Theory:

• Boundary Fill Algorithm

The boundary fill algorithm works as its name. This algorithm picks a point inside an object and starts to fill until it hits the boundary of the object. The color of the boundary and the color that we fill should be different for this algorithm to work.

In this algorithm, we assume that color of the boundary is same for the entire object. The boundary fill algorithm can be implemented by 4-connected pixels or 8-connected pixels.

• Flood Fill Algorithm

Sometimes we want to fill in (or recolor) an area that is not defined within a single color boundary.

Figure below shows an area bordered by several different color regions.

We can paint such areas by replacing a specified interior color instead of searching for a boundary color value.

This approach is called a flood-fill algorithm.

We start from a specified interior point (x, y) and reassign all pixel values that are currently set to a given interior color with the desired fill color.

If the area we want to paint has more than one interior color, we can first reassign pixel values so that all interior points have the same color.

Using either a 4-connected or 8-connected approach, we then step through pixel positions until all interior points have been repainted.

Procedure:

• Boundary Fill Algorithm

Algorithm

Step 1 − Initialize the value of seed point (seedx, seedy), fcolor and dcol.

Step 2 − Define the boundary values of the polygon.

Step 3 − Check if the current seed point is of default color, which is boundary color, then repeat the steps 4 and 5 till the boundary pixels reached.

If getpixel(x, y) = dcol then repeat step 4 and 5

Step 4 − Change the default color with the fill color at the seed point.

setPixel(seedx, seedy, fcol)

Step 5 − Recursively follow the procedure with four neighborhood points.

FloodFill (seedx – 1, seedy, fcol, dcol)

FloodFill (seedx + 1, seedy, fcol, dcol)

FloodFill (seedx, seedy - 1, fcol, dcol)

FloodFill (seedx – 1, seedy + 1, fcol, dcol)

Step 6 − Exit

Procedure for filling a 4- connected region:

 Color is specified by parameter fill color (f-color) and boundary color is specified by boundary color (b-color). getpixel() function gives the color of specified pixel and putpixel() fills the pixel with particular color.

boundary_ fill (x,y, f_color, b_color)

{

If ( getpixel (x,y) != b_color && getpixel (x,y) != f_color)

putpixel(x,y,f_color)

boundary_fill( x+1, y, f_color, b_color);

boundary_fill( x, y+1, f_color, b_color);

boundary_fill( x-1, y, f_color, b_color);

boundary_fill( x, y-1, f_color, b_color);

}

}

• Flood Fill Algorithm

Step 1 − Initialize the value of seed point (seedx, seedy), fcolor and dcol.

Step 2 − Define the boundary values of the polygon.

Step 3 − Check if the current seed point is of default color, which is interior color, then repeat the steps 4 and 5 till the boundary pixels reached

If getpixel(x,y) = dcol then repeat step 4 and 5

Step 4 − Change the default color with the fill color at the seed point.

setPixel(seedx, seedy, fcol)

Step 5 − Recursively follow the procedure with four neighbourhood points

FloodFill (seedx – 1, seedy, fcol, dcol)

FloodFill (seedx + 1, seedy, fcol, dcol)

FloodFill (seedx, seedy - 1, fcol, dcol)

FloodFill (seedx, seedy + 1, fcol, dcol)

FloodFill (seedx – 1, seedy + 1, fcol, dcol)

FloodFill (seedx + 1, seedy + 1, fcol, dcol)

FloodFill (seedx + 1, seedy - 1, fcol, dcol)

FloodFill (seedx – 1, seedy - 1, fcol, dcol)

Step 6 − Exit

Flood Fill Function using 4 Connected Method:

void floodFill4 ( int x, int y, intfillColor , intoldColor)

{

i f (getpixel (x, y) == oldcolor)

{

setcolor ( fillColor ) ;

setpixel (x, y ) :

floodFill4 (x + l, y, fillColor, oldColor):

floodfill4 (x-1, y, fillcolor, oldcolor);

floodPill4 (x, y + l, fillcolor, oldcolor);

floodFill4 (x, y-1, fillColor, oldcolor);

}

}

Procedure for filling a 8- connected region:

flood_ fill (x,y, old_color, new_color)

{

putpixel(x,y,new_color)

flood_ fill (x+1, y, old_color, new_color)

flood_ fill (x-1, y, old_color, new_color)

flood_ fill (x, y+1, old_color, new_color)

flood_ fill (x, y-1, old_color, new_color)

flood_ fill (x+1, y+1, old_color, new_color)

flood_ fill (x-1, y-1, old_color, new_color)

flood_ fill (x+1, y-1, old_color, new_color)

flood_ fill (x-1, y+1, old_color, new_color)

}}

Code : 

CODE FOR BOUNDARY FILL ALGORITHM

#include<stdio.h>

#include<conio.h>

#include<graphics.h>

void boundaryfill(int x,int y,int f_color,int b_color)

{

if(getpixel(x,y)!=b_color && getpixel(x,y)!=f_color)

{

putpixel(x,y,f_color);

boundaryfill(x+1,y,f_color,b_color);

boundaryfill(x-1,y,f_color,b_color);

boundaryfill(x,y+1,f_color,b_color);

boundaryfill(x,y-1,f_color,b_color);

}

}

void main()

{

int gd=DETECT,gm;

initgraph(&gd,&gm,"C:\\TURBOC3\\BGI");

rectangle(250,200,310,260);

boundaryfill(280,250,4,15);

getch();

closegraph();

}

CODE FOR FLOOD FILL ALGORITHM

#include<stdio.h>

#include<conio.h>

#include<graphics.h>

void flood(int x,int y,int f_color,int oldcolor)

{

if(getpixel(x,y)==oldcolor)

{

putpixel(x,y,f_color);

flood(x+1,y,f_color,oldcolor);

flood(x-1,y,f_color,oldcolor);

flood(x,y+1,f_color,oldcolor);

flood(x,y-1,f_color,oldcolor);

}

}

void main()

{

int gd=DETECT,gm;

initgraph(&gd,&gm,"C:\\TURBOC3\\BGI");

rectangle(100,100,160,160);

flood(105,105,4,0);

getch();

closegraph();

}

Output : 

OUTPUT OF FLOOD FILL ALGORITHM

OUTPUT OF FLOOD FILL ALGORITHM

Conclusion:

 In this experiment we learnt to draw a colour filled square with required dimensions using Boundary fill algorithm and also with Flood fill algorithm. We can also draw other shapes using these algorithms.

Question of Curiosity

Q.1] Compare Boundary fill and flood fill algorithm for a polygon?

Ans : 

BOUNDARY-FILL ALGORITHM	FLOOD-FILL ALGORITHM
It defines the area with a single colour. Interior points are coloured by continuously searching for the boundary colour. Memory consumption is Low. It is faster than Flood-fill algorithm.	It can have an area containing several colours. A random colour can be used to colour the interior portion then the old one is replaced with a new one. Memory consumption is High. It is comparatively slower.

Q.2] Write Advantages and Disadvantages of Both algorithms?

Ans : 

Advantages of Flood Fill:

Flood fill colours an entire area in an enclosed figure through interconnected pixels using a single colour.It is an easy way to fill colour in the graphics. One just takes the shape and starts flood fill. The algorithm works in a manner so as to give all the pixels inside the boundary the same colour leaving the boundary and the pixels outside. Flood Fill is also sometimes referred to as Seed Fill as you plant a seed and more and more seeds are planted by the algorithm.

Disadvantages of Flood Fill:

Flood fill algorithm is not advisable for filling larger polygons as quite larger stack is required for them.Also it is slow since it requires a recursive function call to be given to the getpixel() command time and time again.

Advantages of Boundary Fill:

Boundary Fill is another algorithm used for the purpose of colouring figures in computer graphics. It is so similar to Flood Fill that many are confused as to whether it is another variation of it. Here area gets coloured with pixels of a chosen colour as boundary this giving the technique its name.

Disadvantages of Boundary-Fill:

The limitations of boundary fill algorithm like if the polygon is having boundaries with different colours then boundary fill algorithm fails.This limitation of boundary fill algorithm is overcome in flood fill algorithm

Q.3] Explain 4-connected and 8-connected Method ?

Ans :

1) 4-Connected Polygon

In this technique 4-connected pixels are used as shown in the figure. We are 

putting the pixels above, below, to the right, and to the left side of the 

current pixels and this process will continue until we find a boundary with 

different color.

Algorithm:

• Initialize the value of seed point (seedx, seedy), fcolor and dcol.
• Define the boundary values of the polygon.
• Check if the current seed point is of default colour, then repeat the steps 4 and 5 till the boundary pixels reached.If getpixel(x,y) = dcol then repeat step 4 and 5
• Change the default colour with the fill colour at the seed point.

setPixel (seedx, seedy, fcol)

• Recursively follow the procedure with four neighbourhood points.

Floodfill (seedx-1, seedy, fcol, dcol)

Floodfill (seedx+1, seedy, fcol, dcol)

Floodfill (seedx, seedy-1, fcol, dcol)

Floodfill (seedx, seedy+1, fcol, dcol)

• Exit 

There is a problem with this technique. Consider the case as shown below where we tried to fill the entire region. Here, the image is filled only partially. In such cases, 4-connected pixels technique cannot be used.

2) 8-Connected Polygon

In this technique 8-connected pixels are used as shown in the figure. We are putting pixels above, below, right and left side of the current pixels as we were doing in 4-connected technique.

 In addition to this, we are also putting pixels in diagonals so that entire area of the current pixel is covered. This process will continue until we find a boundary with different colour.

Algorithm : 

• Initialize the value of seed point (seedx, seedy), fcolor and dcol.
• Define the boundary values of the polygon.
• Check if the current seed point is of default color then repeat the steps 4 and 5 till the boundary pixels reached

If getpixel(x,y) = dcol then repeat step 4 and 5

• Change the default color with the fill color at the seed point. setPixel( seedx, seedy, fcol)
• Recursively follow the procedure with four neighbourhood points

Floodfill (seedx-1, seedy, fcol, dcol)

Floodfill (seedx+1, seedy, fcol, dcol)

Floodfill (seedx, seedy-1, fcol, dcol)

Floodfill (seedx, seedy+1, fcol, dcol)

Floodfill (seedx-1, seedy+1, fcol, dcol)

Floodfill (seedx+1, seedy+1, fcol, dcol)

Floodfill (seedx+1, seedy-1, fcol, dcol)

Floodfill (seedx-1, seedy-1, fcol, dcol)

• Exit

The 4-connected pixel technique failed to fill the area as marked in the following figure which won’t happen with the 8-connected technique.