• Articles
  • Tutorials
  • Interview Questions

Boundary Fill Algorithm: A Detailed Guide

Boundary Fill Algorithm: A Detailed Guide

Table of content

Show More

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:

Video Thumbnail

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. 

Boundary Filled Region
Flood Filled Region

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. 

Steps in the Boundary Fill Algorithm

The Boundary Fill Algorithm includes the following steps:

Steps in Boundary Fill Algorithm

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. 

Get 100% Hike!

Master Most in Demand Skills Now!

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. 

4-Connected Boundary Fill

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); 
    }
}

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. 

8-Connected Boundary Fill

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);
    }
}

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:

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.

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.

FAQs

What are the key considerations before implementing the Boundary Fill Algorithm?

Before implementing the Boundary Fill Algorithm, ensure you define boundary conditions accurately, choose an appropriate seed point, and handle boundary cases efficiently to prevent potential issues like overflow or underflow.

What are the steps involved in the Boundary Fill Algorithm?

The steps typically involve selecting a seed point, checking and setting boundary conditions, and recursively or iteratively filling adjacent pixels until the boundary is reached, while avoiding overflow or infinite loops.

What are the types of Boundary Fill Algorithms?

There are mainly two types: the 4-connected and 8-connected Boundary Fill Algorithms. The former considers pixels that are horizontally and vertically adjacent, while the latter includes diagonal pixels.

How does the 4-connected Boundary Fill Algorithm differ from the 8-connected one?

The 4-connected algorithm fills pixels that are horizontally and vertically adjacent, whereas the 8-connected algorithm also considers diagonal pixels, providing smoother and more comprehensive filling in some cases.

What are the advantages of the Boundary Fill Algorithm?

The algorithm is relatively simple to implement, efficient for filling closed areas, and applicable in various graphic applications such as paint programs, flood fill tools, and CAD software.

Are there any drawbacks or limitations to the Boundary Fill Algorithm?

Yes, one limitation is its inefficiency in handling complex boundaries or irregular shapes, as it might lead to inefficient memory usage or difficulty in defining boundaries precisely.

Can the Boundary Fill Algorithm be optimized for performance?

Yes, optimization can be achieved by employing efficient data structures, handling boundary conditions intelligently, and implementing the algorithm iteratively to avoid excessive function calls in recursive implementations.

What are the applications of the Boundary Fill Algorithm?

It finds applications in various graphic software for tasks like filling closed shapes, flood fill tools in paint programs, boundary marking, and even in areas like CAD (Computer-Aided Design) software for region filling.

Course Schedule

Name Date Details
Python Course 30 Nov 2024(Sat-Sun) Weekend Batch View Details
07 Dec 2024(Sat-Sun) Weekend Batch
14 Dec 2024(Sat-Sun) Weekend Batch

About the Author

Senior Consultant Analytics & Data Science

Sahil Mattoo, a Senior Software Engineer at Eli Lilly and Company, is an accomplished professional with 14 years of experience in languages such as Java, Python, and JavaScript. Sahil has a strong foundation in system architecture, database management, and API integration.