Boundary Fill Algorithm: A Detailed Guide

The Boundary Fill Algorithm is a foundational computer graphics technique. To know the fundamentals of the Boundary Fill Algorithm, read the blog, where we will cover the definition, steps, types, and implementation, along with the pros and cons of it.

Learn data structures and algorithms from this comprehensive video course:

What is the Boundary Fill Algorithm?

The Boundary Fill Algorithm is a fundamental technique used in computer graphics for coloring enclosed areas within a specified color. Its primary objective is to fill a closed boundary or area with a distinct color, navigating through pixel coordinates.

The algorithm starts by selecting an initial point within the region to be filled and checking neighboring pixels, recursively filling the area until it encounters a boundary color or condition. This process continues until the entire enclosed region is colored. 

The algorithm is particularly useful in applications involving drawing, painting, and picking regions within graphic software because of its ability to efficiently and accurately color bounded areas. 

Points to Consider Before Implementing the Boundary Fill Algorithm

Various points need to be considered before implementing the Boundary Fill Algorithm:

1. Pixel Connectivity: Choose between 4-connectivity or 8-connectivity to define neighboring pixels.
2. Color Representation: Ensure that proper color representation is there.
3. Handling Complex Shapes: Consider how the algorithm handles irregular or complex shapes, including concave areas or regions with holes, to ensure accurate filling of colors. 
4. Boundary Condition Handling: Determine how the algorithm will handle boundary conditions, such as whether to include or exclude boundary pixels. 

Join the Full Stack Developer Course to enhance your expertise. 

Steps in the Boundary Fill Algorithm

The Boundary Fill Algorithm includes the following steps:

Step 1: Select Starting Point: Choose the starting point within the region to be filled with a specified color.

Step 2: Check Current Pixel: If the current pixel is not the same as the boundary color or is not filled, move to the next step. If it is the boundary color and already filled, skip the pixel. 

Step 3: Color Current Pixel: Change the color of the current pixel to fill the color.

Step 4: Recursively Check Neighboring Pixels: Check and apply the following steps:

• Check the pixel to the left
• Check the pixel to the right
• Check the pixel above
• Check the pixel below

Step 5: Repeat Until Filling is Complete: Repeat this process for each checked pixel until the entire area is filled with the desired color. 

Types of Boundary Fill Algorithm

The Boundary Fill Algorithm has two primary types based on pixel connectivity: 4-connected and 8-connected. These types determine which neighboring pixels are considered during the fill process. 

4-Connected Boundary Fill

In 4 connected systems, pixels are considered connected if they share a common edge. In this configuration, a pixel is connected to its immediate neighbors located to the north, south, east, and west.

Pixel Connectivity: Consider only up, down, left, and right to the current pixel

Example: Imagine a square with its sides formed by pixels. When filling using 4 connectivity, only the directly adjacent pixels are checked for filling. 

The algorithm for 4 connected is as follows:

fill_boundary(x, y, colour_f, colour_b) 
{
   if(pixel_get(x, y)! = colour_b && getpixel(x, y)! = colour_f) 
   {
       pixel_put(x, y, f_colour);
       fill_boundary(x + 1, y, colour_f, colour_b); 
       fill_boundary(x, y + 1, colour_f, colour_b); 
       fill_boundary(x -1, y, colour_f, colour_b); 
       fill_boundaryl(x, y – 1, colour_f, colour_b); 
    }
}

Seeking knowledge about various types of polymorphism? Explore our detailed blog explaining the types of polymorphism in C++

8-Connected Boundary Fill

An 8-connected system considers pixels connected if they share a common edge or a corner. In this configuration, a pixel is connected to its immediate neighbor located to the north, south, east, and west, as well as the diagonals: northwest, northeast, southwest, and southeast.

Pixel Connectivity: Consider all eight neighbor pixels, including diagonals.

Example: Expanding on the square example, the 8-connectivity approach checks the diagonally adjacent pixels in addition to the ones checked in the 4-connectivity method. 

The algorithm for 8 connected is as follows:

fill_boundary(x, y, colour_f, colour_b) 
{
   if(getpixel(x, y)! = colour_b && getpixel(x, y)! = colour_f) 
   {
       putpixel(x, y, colour_f);
       fill_boundary(x + 1, y, colour_f, colour_b); 
       fill_boundary(x - 1, y, colour_f, colour_b);
       fill_boundary(x, y + 1, colour_f, colour_b); 
       fill_boundary(x, y - 1, colour_f, colour_b); 
       fill_boundary(x + 1, y + 1, colour_f, colour_b);
       fill_boundary(x - 1, y - 1, colour_f, colour_b);
       fill_boundary(x + 1, y - 1, colour_f, colour_b);
       fill_boundary(x - 1, y + 1, colour_f, colour_b);
    }
}

Do you want a comprehensive list of interview questions? Here are the Full Stack Developer Interview Questions!

Implementation of the Boundary Fill Algorithm

Below is the code for the practical implementation of the Boundary Fill Algorithm in Python:

import matplotlib.pyplot as plt
import numpy as np
def boundary_fill(x, y, fill_color, boundary_color, screen):
    if (x < 0 or x >= len(screen[0]) or y < 0 or y >= len(screen) or
        screen[y][x] == fill_color or screen[y][x] == boundary_color):
        return
    screen[y][x] = fill_color
    boundary_fill(x + 1, y, fill_color, boundary_color, screen)
    boundary_fill(x - 1, y, fill_color, boundary_color, screen)
    boundary_fill(x, y + 1, fill_color, boundary_color, screen)
    boundary_fill(x, y - 1, fill_color, boundary_color, screen)
def create_plot(screen, colors):
    height = len(screen)
    width = len(screen[0])
    data = np.zeros((height, width, 3), dtype=np.uint8)
    for y in range(height):
        for x in range(width):
            data[y, x] = colors[screen[y][x]]
    plt.imshow(data)
    plt.axis('off')
    plt.show()
# Initialize the screen
width, height = 10, 8
screen = [['white' for  in range(width)] for  in range(height)]
# Define colors
colors = {
    'black': [0, 0, 0],
    'blue': [0, 0, 255],
    'white': [255, 255, 255]
}
# Draw a rectangle
for i in range(width):
    screen[0][i] = 'black'
    screen[height-1][i] = 'black'
for i in range(height):
    screen[i][0] = 'black'
    screen[i][width-1] = 'black'
# Apply the boundary fill algorithm
boundary_fill(5, 4, 'blue', 'black', screen)
# Create and show the plot
create_plot(screen, colors)

Output:

Pros and Cons of the Boundary Fill Algorithm

Understanding the benefits and drawbacks of the Boundary Fill Algorithm is necessary, as it helps fill a closed boundary or area with a specific color while navigating through pixel coordinates.

• Pros
  • It is easy to comprehend and put into practice.
  • It can be customized to fill bounded areas with various forms.
  • It fills small to medium-sized spaces effectively.
  • It is ideal for interactive applications in which the user can choose the fill color and starting point.
  • To create more complex effects, it can be coupled with other algorithms like edge detection and smoothing.
• Cons
  • It is unable to manage regions that overlap.
  • Because it is recursive, it may be slow for large regions.
  • Unwanted outcomes could include holes or gaps in the filled area.
  • It is not recommended for filling non-convex shapes or areas with holes.
  • Because of its propensity for excessive recursion, it may not function properly in large or complex regions.

Also, read our blog on flood fill algorithms, and master computer graphics.

Wrap-Up

The Boundary Fill Algorithm proves to be a useful tool in computer graphics. Visual rendering has been revolutionized by its ability to color regions within boundaries efficiently. We’ve learned how important it is to comprehend its details, produce visually compelling content, and maximize its functionality through this investigation. This algorithm emphasizes accuracy and creativity in graphic rendering, from minimizing boundary errors to maximizing speed. As it continues to shape immersive experiences and make pixels come alive with vibrant, simple colors in the always-changing conditions of digital artistry, embrace its potential in a variety of applications, from gaming to design.

Do you still have queries? You can post your doubts on our Community Page.

FAQs