Get this book -> Problems on Array: For Interviews and Competitive Programming

In the days of MS-Paint, we all drew something and filled it with a color. Such task falls under Region Filling (Seed-Fill) Algorithms.

**Region Filling** is the process of filling a region or an image. Further depending upon filling, it can be categorized as:

__Boundary Filling Algorithm__- region inside the boundary of same pixel value__Flood Filling Algorithm__- region having same pixel value

Fig.1 Flood Fill Algorithm

Fig.2 Boundary Fill Algorithm

In this article, we are going to discuss about Boundary Algorithm.

## Introduction to Boundary Fill Algorithm

In computer graphics, Boundary Fill algorithm is used to fill a inside of closed polygon having boundary of same color with a desired color. It is mainly used with interactive-painting packages where an inside point can be easily chosen as its approach requires a starting pixel also called seed, to start with.

## Details on Implementation and Problem statement

It is mainly implemented using stack-based recursion. Functioning of the boundary-fill requires an interior point (x,y) , fill color and boundary color to start with. The algorithm starts by checking whether a pixel value equals to boundary color or fill color . If not, pixel is filled with desired color and advances to check for neighboring pixels. Else, not. The process continues until it hits all sides of the boundary region.

Further, Boundary-fill algorithm can be implemented using 4-connected pixels and 8-connected pixels.

**4-connected pixels** : Neighboring pixels are pixels on left,right,above and below of current pixel.

**8-connected pixels** : Neighboring pixels are left,right ,above ,below and 4 diagonal pixels as shown below.

Fig.3 Neighboring Pixels

**4-connected vs 8-connected**

In case of sharp boundaries, 4-connected method fails, while 8-connected method filled the region efficiently. Following figure represents the situation.

## Boundary Fill Algorithm

Steps in Boundary Fill Algorithm:

- There are two defined colors: color of boundary (color_boundary) and color that needs to be filled (color_fill)
- Get color (say color1) of the current pixel
- If color1 is equal to color_boundary or color_fill, nothing needs to be done as correct color is already assigned.
- If color1 is not equal to the two values:

4.1. Add color_fill to the current pixel.

4.2. Do the same process for 4 adjacent pixel points: (x, y-1), (x+1, y), (x, y+1), (x-1, y)

4.3. If 8-connected fill is being done, do the same process for 4 diagonal pixel points additionally: (x+1, y-1), (x+1, y+1), (x-1, y+1), (x-1, y-1). - Do the process for every pixel point.

```
void boundary_fill(int x,int y,int fill_color,int boundary_color){
int cur_color = getpixel(x,y);
if(cur_color == boundary_color or cur_color == fill_color)
return;
fillpixel(x,y,fill_color);
boundary_fill(x,y-1,fill_color,boundary_color);
boundary_fill(x+1,y,fill_color,boundary_color);
boundary_fill(x,y+1,fill_color,boundary_color);
boundary_fill(x-1,y,fill_color,boundary_color);
/*For 8-connected pixels,additional calls
boundary_fill(x+1,y-1,fill_color,boundary_color);
boundary_fill(x+1,y+1,fill_color,boundary_color);
boundary_fill(x-1,y+1,fill_color,boundary_color);
boundary_fill(x-1,y-1,fill_color,boundary_color);
*/
}
```

The time complexity of Boundary Fill Algorithm is **O(N)** where N is the number of pixels.

The space complexity is O(N) from the recursive calls. In an iterative implementation, space complexity will be O(1).

## Restrictions

- Starting point should be inside closed polygon.
- For all edges of a polygon, boundary color should be same.
- It may fail to fill in case some interior pixels are already filled with color.

With this article at OpenGenus, you must have the complete idea of Boundary Fill Algorithm.