Scribd
Upload
41 views6 pages

Boundary Fill Algorithm Explained

The boundary fill algorithm starts by filling a pixel inside a polygon and proceeds outwards, filling neighboring pixels of a different color until it reaches the boundary. It is recursive and calls itself on neighboring pixels to fill the area. It can fill areas with 4-connected or 8-connected neighboring pixels. 4-connected uses up, down, left, right pixels while 8-connected additionally uses diagonal pixels, allowing it to fill more complex shapes completely. Boundary fill differs from flood fill in that it only fills until reaching a boundary color rather than replacing all similarly colored pixels.

Uploaded by

pratapmukherjee
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
41 views6 pages

Boundary Fill Algorithm Explained

The boundary fill algorithm starts by filling a pixel inside a polygon and proceeds outwards, filling neighboring pixels of a different color until it reaches the boundary. It is recursive and calls itself on neighboring pixels to fill the area. It can fill areas with 4-connected or 8-connected neighboring pixels. 4-connected uses up, down, left, right pixels while 8-connected additionally uses diagonal pixels, allowing it to fill more complex shapes completely. Boundary fill differs from flood fill in that it only fills until reaching a boundary color rather than replacing all similarly colored pixels.

Uploaded by

pratapmukherjee
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Introduction : 

Boundary Fill Algorithm starts at a pixel inside the polygon to be


filled and paints the interior proceeding outwards towards the boundary. This
algorithm works only if the color with which the region has to be filled and the
color of the boundary of the region are different. If the boundary is of one single
color, this approach proceeds outwards pixel by pixel until it hits the boundary
of the region.
Boundary Fill Algorithm is recursive in nature. It takes an interior point(x, y),
a fill color, and a boundary color as the input. The algorithm starts by checking
the color of (x, y). If it’s color is not equal to the fill color and the boundary color,
then it is painted with the fill color and the function is called for all the
neighbours of (x, y). If a point is found to be of fill color or of boundary color, the
function does not call its neighbours and returns. This process continues until
all points up to the boundary color for the region have been tested.
The boundary fill algorithm can be implemented by 4-connected pixels or 8-
connected pixels.
4-connected pixels : After painting a pixel, the function is called for four
neighboring points. These are the pixel positions that are right, left, above and
below the current pixel. Areas filled by this method are called 4-connected.
Below given is the algorithm :
Algorithm :

void boundaryFill4(int x, int y, int fill_color,int boundary_color)


{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill4(x + 1, y, fill_color, boundary_color);
boundaryFill4(x, y + 1, fill_color, boundary_color);
boundaryFill4(x - 1, y, fill_color, boundary_color);
boundaryFill4(x, y - 1, fill_color, boundary_color);
}
}
Below is the implementation of above algorithm :

// C Implementation for Boundary Filling Algorithm


#include <graphics.h>
  
// Function for 4 connected Pixels
void boundaryFill4(int x, int y, int fill_color,int
boundary_color)
{
    if(getpixel(x, y) != boundary_color &&
       getpixel(x, y) != fill_color)
    {
        putpixel(x, y, fill_color);
        boundaryFill4(x + 1, y, fill_color, boundary_color);
        boundaryFill4(x, y + 1, fill_color, boundary_color);
        boundaryFill4(x - 1, y, fill_color, boundary_color);
        boundaryFill4(x, y - 1, fill_color, boundary_color);
    }
}
  
//driver code
int main()
{
    // gm is Graphics mode which is
    // a computer display mode that
    // generates image using pixels.
    // DETECT is a macro defined in
    // "graphics.h" header file
    int gd = DETECT, gm;
  
    // initgraph initializes the
    // graphics system by loading a
    // graphics driver from disk
    initgraph(&gd, &gm, "");
  
    int x = 250, y = 200, radius = 50;
  
    // circle function
    circle(x, y, radius);
  
    // Function calling
    boundaryFill4(x, y, 6, 15);
  
    delay(10000);
  
    getch();
  
    // closegraph function closes the
    // graphics mode and deallocates
    // all memory allocated by
    // graphics system .
    closegraph();
  
    return 0;
}

Output :

8-connected pixels : More complex figures are filled using this approach. The
pixels to be tested are the 8 neighboring pixels, the pixel on the right, left,
above, below and the 4 diagonal pixels. Areas filled by this method are called 8-
connected. Below given is the algorithm :
Algorithm :
void boundaryFill8(int x, int y, int fill_color,int boundary_color)
{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill8(x + 1, y, fill_color, boundary_color);
boundaryFill8(x, y + 1, fill_color, boundary_color);
boundaryFill8(x - 1, y, fill_color, boundary_color);
boundaryFill8(x, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y + 1, fill_color, boundary_color);
boundaryFill8(x + 1, y - 1, fill_color, boundary_color);
boundaryFill8(x + 1, y + 1, fill_color, boundary_color);
}
}

Below is the implementation of above algorithm :

// C Implementation for Boundary Filling Algorithm


#include <graphics.h>
  
// Function for 8 connected Pixels
void boundaryFill8(int x, int y, int fill_color,int
boundary_color)
{
    if(getpixel(x, y) != boundary_color &&
       getpixel(x, y) != fill_color)
    {
        putpixel(x, y, fill_color);
        boundaryFill8(x + 1, y, fill_color, boundary_color);
        boundaryFill8(x, y + 1, fill_color, boundary_color);
        boundaryFill8(x - 1, y, fill_color, boundary_color);
        boundaryFill8(x, y - 1, fill_color, boundary_color);
        boundaryFill8(x - 1, y - 1, fill_color, boundary_color);
        boundaryFill8(x - 1, y + 1, fill_color, boundary_color);
        boundaryFill8(x + 1, y - 1, fill_color, boundary_color);
        boundaryFill8(x + 1, y + 1, fill_color, boundary_color);
    }
}
  
//driver code
int main()
{
    // gm is Graphics mode which is
    // a computer display mode that
    // generates image using pixels.
    // DETECT is a macro defined in
    // "graphics.h" header file
    int gd = DETECT, gm;
  
    // initgraph initializes the
    // graphics system by loading a
    // graphics driver from disk
    initgraph(&gd, &gm, "");
  
    // Rectangle function
    rectangle(50, 50, 100, 100);
  
    // Function calling
    boundaryFill8(55, 55, 4, 15);
  
    delay(10000);
  
    getch();
  
    // closegraph function closes the
    // graphics mode and deallocates
    // all memory allocated by
    // graphics system .
    closegraph();
  
    return 0;
}

Output :

4-connected pixels Vs 8-connected pixels :


Let us take a figure with the boundary color as GREEN and the fill color as
RED. The 4-connected method fails to fill this figure completely. This figure will
be efficiently filled using the 8-connected technique.

Flood fill Vs Boundary fill :


Though both Flood fill and Boundary fill algorithms color a given figure with a
chosen color, they differ in one aspect. In Flood fill, all the connected pixels of a
selected color get replaced by a fill color. On the other hand, in Boundary fill,
the program stops when a given color boundary is found.

Common questions

Powered by AI

The 4-connected Boundary Fill approach tests four neighboring pixels (right, left, above, and below the current pixel) while filling, making it suitable for simpler or more grid-like shapes. The 8-connected method, however, checks all eight neighbors including diagonal ones, making it more adequate for complex figures or boundaries with ambiguous areas, as it provides more directional checks and thus a higher likelihood of completing the fill without gaps .

The 4-connected Boundary Fill method might fail to completely fill a region if the boundary or the figure has small gaps or complex edges, as it only checks pixels in four main compass directions. For example, if filling a star shape with a narrow arm, the 4-connected method may leave parts unfilled where diagonal pixels should be connected but aren't directly adjacent in those four directions. The 8-connected method fills such gaps by also considering diagonal connections, ensuring all regions within the boundary are filled .

A graphics developer might prefer using the Boundary Fill Algorithm over the Flood Fill Algorithm when clear and distinct boundaries are defined, as the Boundary Fill specifically stops at predefined boundaries, making it ideal for regions that must not spill over certain visual limits. This is particularly useful in graphical user interfaces where areas are distinctly marked and should remain isolated in appearance .

The Boundary Fill Algorithm starts at a pixel inside the region to be filled and proceeds outward toward the boundary of that region until the boundary color is encountered. It specifically requires a boundary to prevent filling beyond the desired area. In contrast, the Flood Fill Algorithm replaces all pixels connected to a start pixel of a specific color with the fill color regardless of boundaries, continuing until all such pixels within the connected area are transformed .

The Boundary Fill Algorithm presents limitations such as its dependency on boundary and fill color differentiation to stop recursion, which can lead to inefficiencies or errors if the colors are not correctly set or if color bleeding occurs. Additionally, recursive calls can lead to stack overflow with large or complex fill areas. Its performance issues are also highlighted where recursion depth increases fill time significantly .

Boundary and fill color mismatches can significantly disrupt the Boundary Fill operation, as the algorithm relies on these colors for its termination conditions. Incorrect colors can lead to over-filling or premature termination, compromising the fill integrity. For instance, if the boundary is not uniformly colored, the algorithm might stop incorrectly, leaving gaps near the boundary edges .

Using 8-connected pixels in the Boundary Fill Algorithm is significant for complex figures because it provides a more comprehensive fill strategy that can handle intricate patterns or jagged edges. By assessing all eight possible surrounding pixels, the algorithm reduces the likelihood of leaving unfilled spaces, ensuring more continuous and complete coverage. This comprehensiveness is particularly necessary in scenarios where boundary definitions are not uniform or where intricate shapes require thorough coverage .

The recursive nature of the Boundary Fill Algorithm influences its implementation by necessitating a base case to prevent infinite recursion—namely, encountering a pixel that matches either the boundary color or the fill color. Performance-wise, recursion can lead to significant function call overhead and potential stack overflow if the fill area is large, since each pixel requires a new function call to fill adjacent pixels. This recursive depth is particularly visible in large fill operations, where an iterative approach might manage memory use more effectively .

The Boundary Fill Algorithm respects edges during the filling process by stopping the fill operation when it encounters the boundary color. It checks each pixel and only proceeds if the pixel value does not match the boundary color. This way, it contains the fill within the designated boundary area, ensuring that no colors spill over to unintended areas .

The key prerequisites for efficiently applying the Boundary Fill Algorithm include ensuring that the fill color and the boundary color are distinct. Furthermore, the starting pixel must be inside the boundary and the boundary itself should be a single color; otherwise, the algorithm might not behave as expected due to encountering multiple boundaries .

You might also like