![Binary Tree book by OpenGenus](/assets/images/binary-tree.png)
Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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
![Flood-Fill](/content/images/2021/08/Flood-Fill.png)
Fig.1 Flood Fill Algorithm
![Boundary-Fill](/content/images/2021/08/boundary-fill-algorithm.gif)
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.