0
38kviews
Explain Boundary / Edge fill algorithm (8 connected region). OR Write a boundary fill procedure to fill 8-connected region.
1 Answer
1
1.5kviews

Polygon Filling:-
Filling the polygon means highlighting all the pixels which lie inside the polygon with any colour other than background colour. Polygons are easier to fill since they have linear boundaries.

There are two basic approaches used to fill the polygon.

One way to fill polygon is to start from given “seed”, point known to be inside the polygon and highlight outward from this point i.e. neigh-bouring pixels until we encounter the boundary pixels. This approach is called seed fill , because colour flows from the seed pixel until reaching the polygon boundary like water flooding on the surface of the container.

Another approach to fill the polygon is to apply the inside test i.e. to check whether the pixels is inside the polygon or outside the polygon and then highlight pixels which lie inside the polygon. This approach is known as scan-line algorithm It avoids the need for seed pixel it requires some computation.

Seed Fill :-

The seed fill algorithm is further classified as flood fill algorithm and boundary fill algorithm.

Algorithms that fill interior-defined regions are called flood-fill algorithms; those that fill boundary-defined regions are called boundary-fill algorithms or edge-fill algorithms.

Boundary Fill Algorithm :

In this method, edges of the polygons are drawn. Then starting with some seed, any point inside the Polygon we examine the neighbouring pixels to check whether the boundary pixel is reached. If boundary pixels are not reached, pixels are highlighted and the process is continued until boundary pixels are reached.

enter image description here

Boundary defined regions may be either 4-connected or 8-connected as shown in the figure (a) and (b).

If a region is 4-connected, then every pixel in the region may be reached by a combination of moves in only four directions: left, right, up and down.

For an 8-connected region every pixel in the region may be reached by a combination of moves in the two horizontal, two vertical, and four diagonal directions.

In some cases, an 8-connected algorithm is more accurate than the 4-connected algorithm. This is illustrated in figure (c). Here, a 4-connected algorithm produces the partial fill.

enter image description here

The following procedure illustrates the recursive method for filling a 4-connected region with colour specified in parameter fill colour (f_colour) up to a boundary colour specified with parameter boundary colour (b_colour).

Procedure:-

4-connected boundary / edge fill Algorithm :-

boundary_fill(x, y, f_colour, b_colour) 
{
   if(getpixel(x, y)! = b_colour && getpixel(x, y)! = f_colour) 
   {
       putpixel(x, y, f_colour);
       boundary_fill(x + 1, y, f_colour, b_colour); 
       boundary_fill(x, y + 1, f_colour, b_colour); 
       boundary_fill(x -1, y, f_colour, b_colour); 
       boundary_fill(x, y – 1, f_colour, b_colour); 
    }
}

8-connected boundary / edge fill Algorithm:-

boundary_fill(x, y, f_colour, b_colour) 
{
   if(getpixel(x, y)! = b_colour && getpixel(x, y)! = f_colour) 
   {
       putpixel(x, y, f_colour);
       boundary_fill(x + 1, y, f_colour, b_colour); 
       boundary_fill(x - 1, y, f_colour, b_colour);
       boundary_fill(x, y + 1, f_colour, b_colour); 
       boundary_fill(x, y - 1, f_colour, b_colour); 
       boundary_fill(x + 1, y + 1, f_colour, b_colour);
       boundary_fill (x - 1, y - 1, f_colour, b_colour);
       boundary_fill(x + 1, y - 1, f_colour, b_colour);
       boundary_fill(x - 1, y + 1, f_colour, b_colour);
    }
}

Note: - getpixel function gives the colour of specified pixel and putpixel function draws the pixel with specified colour.

Please log in to add an answer.