Computer Graphics: Drawing, Clipping, and Filling Algorithms
|
├── 1. Line Drawing Algorithms
│   ├── DDA Algorithm
│   ├── Bresenham’s Line Algorithm
│   └── Circle and Ellipse Generation Algorithm
│
├── 2. Clipping
│   ├── Point Clipping
│   ├── Line Clipping
│   └── Polygon Clipping
│
└── 3. Filling
    ├── Inside Tests
    ├── Flood Fill Algorithm
    ├── Boundary-Fill Algorithm
    └── Scan-Line Polygon Fill Algorithm
                
            

DDA Line Drawing Algorithm

The DDA (Digital Differential Analyzer) line drawing algorithm is an efficient method for drawing lines in computer graphics. It uses simple calculations to determine the coordinates of each pixel along a line.

Steps to Draw a Line using DDA Algorithm

• Step 1: Given Two Points

  We are given two points, which define the start and end of the line:

  • Point 1 (x1, y1) – Start point of the line.
  • Point 2 (x2, y2) – End point of the line.

  The points (x1, y1) and (x2, y2) will define the start and end of the line.

• Step 2: Calculate Differences

  We calculate the differences in the X and Y coordinates:

  \[ \Delta X = x2 - x1 \]

  
  

  \[ \Delta Y = y2 - y1 \]

  The values of ΔX and ΔY will help in determining the slope and how to increment X or Y.

• Step 3: Calculate the Slope

  The slope (m) of the line is calculated as:

  \[ m = \frac{\Delta Y}{\Delta X} \]

  This gives us the direction of the line, which helps in deciding whether to increment X or Y.

• Step 4: Decide Whether to Increment X or Y

  Now, we decide how to move along the line. There are two cases:

  • Case 1: When ΔX ≥ ΔY (X changes more than Y)

    In this case, we increment X by 1 in each step. To find the corresponding Y, we use the slope:

    \[ \Delta Y = m \times \Delta X \]

    Since we are incrementing X by 1 (i.e., ΔX = 1), we substitute this into the equation:

    \[ y_{i+1} = y_i + m \]

    Now, we increment X by 1:

    \[ x_{i+1} = x_i + 1 \]

  • Case 2: When ΔY > ΔX (Y changes more than X)

    In this case, we increment Y by 1 in each step. To find the corresponding X, we rearrange the slope formula:

    \[ \Delta X = \frac{\Delta Y}{m} \]

    Since we are incrementing Y by 1 (i.e., ΔY = 1), we substitute this into the equation:

    \[ x_{i+1} = x_i + \frac{1}{m} \]

    Now, we increment Y by 1:

    \[ y_{i+1} = y_i + 1 \]

• Step 5: Continue Until the End Point is Reached

  Start at (x1, y1) and keep calculating the next coordinates using the steps above until reaching (x2, y2). Round the values to get the closest integer pixel positions.

---

Example: Line from (2, 3) to (6, 8)

Given:

• Point 1 (x1, y1) = (2, 3)
• Point 2 (x2, y2) = (6, 8)

First, calculate the differences:

\[ \Delta X = 6 - 2 = 4, \quad \Delta Y = 8 - 3 = 5 \]

Next, calculate the slope:

\[ m = \frac{5}{4} = 1.25 \]

Since ΔY > ΔX, we increment Y by 1 and calculate X for each step. Here’s the calculation for the points:

• Start at (2, 3).
• Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 2 + \frac{1}{1.25} = 2.8 \]

• The next point is (2.8, 4).
• Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 2.8 + \frac{1}{1.25} = 3.6 \]

• The next point is (3.6, 5).
• Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 3.6 + \frac{1}{1.25} = 4.4 \]

• The next point is (4.4, 6).
• Next point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 4.4 + \frac{1}{1.25} = 5.2 \]

• The next point is (5.2, 7).
• Final point: Increment Y by 1, calculate X:

\[ X_{\text{next}} = X + \frac{1}{m} = 5.2 + \frac{1}{1.25} = 6 \]

• The next point is (6, 8), which is the end point.

Here’s the table of values:

This table shows the calculated points from the start to the end point using the DDA algorithm.

---

Example: Line from (1, 1) to (4, 3)

Given:

• Point 1 (x1, y1) = (1, 1)
• Point 2 (x2, y2) = (4, 3)

First, calculate the differences:

\[ \Delta X = 4 - 1 = 3, \quad \Delta Y = 3 - 1 = 2 \]

Next, calculate the slope:

\[ m = \frac{2}{3} \approx 0.6667 \]

Since ΔX > ΔY, we increment X and calculate Y for each step. Here’s the calculation for the points:

• Start at (1, 1).
• Next point: Increment X by 1, calculate Y:

\[ Y_{\text{next}} = Y + m = 1 + 0.6667 = 1.6667 \]

• The next point is (2, 1.6667).
• Next point: Increment X by 1, calculate Y:

\[ Y_{\text{next}} = Y + m = 1.6667 + 0.6667 = 2.3333 \]

• The next point is (3, 2.3333).
• Final point: Increment X by 1, calculate Y:

\[ Y_{\text{next}} = Y + m = 2.3333 + 0.6667 = 3 \]

• The next point is (4, 3), which is the end point.

Here’s the table of values:

This table shows the calculated points from the start to the end point using the DDA algorithm.

Bresenham's Line Drawing Algorithm

• We are familiar with the DDA (Digital Differential Analyzer) algorithm for line drawing, right? It works by calculating the slope of the line and incrementing the coordinates in steps, using floating-point arithmetic. While DDA provides a simple and straightforward way to draw lines, the main drawback is that it uses floating-point calculations, which can lead to rounding errors and less efficient performance.
• This is where Bresenham's Line Drawing Algorithm comes in. Unlike DDA, which uses floating-point calculations, Bresenham's algorithm works entirely with integer arithmetic. This means it avoids the use of floating-point numbers, leading to more accurate and efficient calculations. The result is a much faster and more precise way to draw lines on digital screens, without the risk of rounding errors.

Definition: The Bresenham's Line Drawing Algorithm is an efficient way to draw a straight line between two points in computer graphics. The algorithm uses integer calculations to avoid the use of floating-point operations, making it faster and suitable for raster display systems.

• Step 1: Given Two Points

  We are given two points (x1, y1) and (x2, y2), which define the start and end of the line.

• Step 2: Calculate Differences

  First, we calculate the differences in X and Y:

  \[ \Delta X = x2 - x1, \quad \Delta Y = y2 - y1 \]

  Important: These values of ΔX and ΔY are calculated once at the beginning and remain the same throughout the algorithm. When updating the decision parameter p, we always use these initial values and do not recalculate them based on the updated x and y.

• Step 3: Calculate the Slope

  The slope m is calculated as:

  \[ m = \frac{\Delta Y}{\Delta X} \]

  We use this to determine whether the line is shallow or steep.

• Step 4: Initialize the Decision Parameter

  The decision parameter p is initialized using the fixed values of ΔX and ΔY:

  \[ p = 2\Delta Y - \Delta X \]

  Important: When updating p in later steps, we always use the original ΔX and ΔY that were calculated at the beginning.

• Step 5: Check the Slope

  Now, we check whether the slope m is less than 1 or greater than or equal to 1. The algorithm behaves differently based on this value:

  • Case 1: When m < 1 (Shallow Line - More Horizontal)

    If m < 1, we always increment x by 1 and decide whether to increment y.

    Using the fixed values of ΔX and ΔY, the steps are:

    • Start: Let x0 = x1 and y0 = y1. We continue until we reach x2.
    • If p < 0:

      \[ x_{i+1} = x_i + 1, \quad y_{i+1} = y_i \]

      Update p using the fixed ΔX and ΔY:

      \[ p = p + 2 \Delta Y \]

    • If p ≥ 0:

      \[ x_{i+1} = x_i + 1, \quad y_{i+1} = y_i + 1 \]

      Update p using the fixed ΔX and ΔY:

      \[ p = p + 2 \Delta Y - 2 \Delta X \]

  • Case 2: When m ≥ 1 (Steep Line - More Vertical)

    If m ≥ 1, we always increment y by 1 and decide whether to increment x.

    Using the fixed values of ΔX and ΔY, the steps are:

    • Start: Let x0 = x1 and y0 = y1. We continue until we reach y2.
    • If p < 0:

      \[ x_{i+1} = x_i, \quad y_{i+1} = y_i + 1 \]

      Update p using the fixed ΔX and ΔY:

      \[ p = p + 2 \Delta X \]

    • If p ≥ 0:

      \[ x_{i+1} = x_i + 1, \quad y_{i+1} = y_i + 1 \]

      Update p using the fixed ΔX and ΔY:

      \[ p = p + 2 \Delta X - 2 \Delta Y \]

• Step 6: Continue Until the End Point is Reached

  We continue applying the rules above, updating p and plotting the points step by step from (x1, y1) to (x2, y2).

  Important: The values of ΔX and ΔY never change during this process. When updating p, we do not recalculate them using the new x and y. Instead, we always use the original values calculated at the beginning.

---

Bresenham's Line Drawing Algorithm: Example

We will use Bresenham's Line Drawing Algorithm to draw a line between the points (1, 1) and (5, 3).

Given Two Points:

Let the starting point be:

\[ x_0 = 1, \quad y_0 = 1 \]

We continue until we reach:

\[ x = 5, \quad y = 3 \]

Step 1: Calculate Differences

First, we calculate the differences in the x and y coordinates:

\[ \Delta X = x_2 - x_1 = 5 - 1 = 4, \quad \Delta Y = y_2 - y_1 = 3 - 1 = 2 \]

Step 2: Compute Initial Decision Parameter

The decision parameter \( p \) is calculated as:

\[ p_0 = 2 \Delta Y - \Delta X = 2 \times 2 - 4 = 0 \]

Step 3: Iterating Through Points

Since \( m < 1 \), we increment \( x \) by 1 at each step and decide whether to increment \( y \) based on \( p \).

• Initially: \( x_0 = 1, y_0 = 1, p_0 = 0 \).
• Step 1: Since \( p_0 \geq 0 \), we increment both \( x \) and \( y \):

\[ x_1 = x_0 + 1 = 2, \quad y_1 = y_0 + 1 = 2 \]

Update \( p \):

\[ p_1 = p_0 + 2 \Delta Y - 2 \Delta X = 0 + 2(2) - 2(4) = -4 \]

• Step 2: Since \( p_1 < 0 \), we only increment \( x \):

\[ x_2 = x_1 + 1 = 3, \quad y_2 = y_1 = 2 \]

Update \( p \):

\[ p_2 = p_1 + 2 \Delta Y = -4 + 2(2) = 0 \]

• Step 3: Since \( p_2 \geq 0 \), we increment both \( x \) and \( y \):

\[ x_3 = x_2 + 1 = 4, \quad y_3 = y_2 + 1 = 3 \]

Update \( p \):

\[ p_3 = p_2 + 2 \Delta Y - 2 \Delta X = 0 + 2(2) - 2(4) = -4 \]

• Step 4: Since \( p_3 < 0 \), we only increment \( x \):

\[ x_4 = x_3 + 1 = 5, \quad y_4 = y_3 = 3 \]

Since we have reached \( x = 5, y = 3 \), we stop.

Table of Calculated Points:

The points (1,1), (2,2), (3,2), (4,3), and (5,3) are plotted following Bresenham's algorithm. The decision parameter is used to determine whether to increment Y in each step while always incrementing X by 1.

Example: Draw a Circle with Center (0,0) and Radius 5

Step 1: Given Information

• Center of the Circle: \( (0,0) \)
• Radius: \( r = 5 \)

Step 2: Initial Setup

We start from the topmost point of the circle at \( (0,5) \). The decision parameter helps us determine the next point.

Step 3: Compute Initial Decision Parameter

The initial decision parameter is given by:

\[ p_0 = 1 - r \]

Substituting \( r = 5 \):

\[ p_0 = 1 - 5 = -4 \]

Step 4: Compute Points Step by Step

We use the decision rule:

• If \( p_k < 0 \): Next point is \( (x+1, y) \), update \( p \) using:

  \[ p_{\text{new}} = p + 2x + 3 \]

• If \( p_k \geq 0 \): Next point is \( (x+1, y-1) \), update \( p \) using:

  \[ p_{\text{new}} = p + 2x - 2y + 5 \]

Step-by-Step Calculations

Starting from \( (0,5) \):

• Step 1: We start with \( p_0 = -4 \), which is calculated using the formula \( p_0 = 1 - r \) where \( r = 5 \).

  At this point, the current values of \( x = 0 \) and \( y = 5 \). Since \( p_0 < 0 \), we move horizontally to the right, meaning the next point will be \( (x+1, y)=(1, 5) \), and we update the decision parameter:

  \( p_1 = p_0 + 2x + 3 = -4 + 2(0) + 3 = -1 \)

• Step 2: Now we have \( p_1 = -1 \), and the current values of \( x = 1 \) and \( y = 5 \). Since \( p_1 < 0 \), we again move horizontally to the right, meaning the next point will be \( (x+1, y)=(2, 5) \). We update the decision parameter:

  \( p_2 = p_1 + 2x + 3 = -1 + 2(1) + 3 = 4 \)

• Step 3: Now we have \( p_2 = 4 \), and the current values of \( x = 2 \) and \( y = 5 \). Since \( p_2 \geq 0 \), we move diagonally, meaning the next point will be \( (x+1, y-1) = (3, 4) \). We then update the decision parameter:

  \( p_3 = p_2 + 2x - 2y + 5 = 4 + 2(2) - 2(5) + 5 = 3 \)

• Step 4: Now we have \( p_3 = 3 \), and the current values of \( x = 3 \) and \( y = 4 \). Since \( p_3 \geq 0 \), we again move diagonally, meaning the next point will be \( (x+1, y-1) = (4, 3) \). However, since \( x = 4 \) and \( y = 3 \), we stop the algorithm here as the condition \( x \geq y \) is satisfied (we have completed one-eighth of the circle).

Final Points

These points are calculated for one-eighth of the circle.

Point Clipping

• In point clipping, we work specifically with individual points rather than lines or shapes.
• We determine whether a given point lies inside or outside the clipping window.
• For example, consider two points: P1 (x₁, y₁) and P2 (x₂, y₂). If P1 is outside the clipping window and P2 is inside, we need a method to confirm this based on their coordinates.

• To determine if a point lies inside the rectangular window, we use the boundary values: x_min, x_max, y_min, and y_max.

• If a point satisfies all four boundary conditions, it is considered inside the window. Otherwise, it is outside. Let the point be P(x, y). The conditions are:
  1. x ≥ x_min
  2. x ≤ x_max
  3. y ≥ y_min
  4. y ≤ y_max

Numerical: Consider two points: P1 (5, 1) and P2 (6, 9), and a clipping window with the following boundaries:

• x_min = 2
• x_max = 9
• y_min = 3
• y_max = 11

Solution: Evaluate point P1 (5, 1):

• 5 ≥ 2 → True
• 5 ≤ 9 → True
• 1 ≥ 3 → False

Since one condition is false, P1 is outside the clipping window.

Now evaluate point P2 (6, 9):

• 6 ≥ 2 → True
• 6 ≤ 9 → True
• 9 ≥ 3 → True
• 9 ≤ 11 → True

All conditions are satisfied, so P2 lies inside the clipping window.

Line Clipping (Cohen–Sutherland Algorithm)

• The Cohen–Sutherland algorithm is used to clip lines to a rectangular clipping window. The goal is to identify which portion of a line lies within the window and discard the portion that lies outside.

• To determine which part of the line is inside the clipping window, we use a 4-bit region code, also known as the TBRL code — representing Top, Bottom, Right, and Left. Each bit indicates whether the point lies outside the respective boundary.
• In the diagram below, the entire 2D plane is divided into 9 regions. The central region (region 5) represents the clipping window.

• Each region is assigned a unique 4-bit code based on its position relative to the clipping window. The code for the center region (inside the window) is 0000, meaning the point lies within all four boundaries.

• There are three possible cases for any line segment:
  1. Completely Inside: A line with both endpoints having the region code 0000 lies entirely within the clipping window. No clipping is needed.
     
  2. Completely Outside: If both endpoints of the line lie in the same region outside the window and share a common set bit in their region codes, the result of the bitwise AND operation is non-zero. This means the line is completely outside and can be rejected.

                                         
       0001
     & 0001
     -------
       0001
                                     
                                 

     
     
  3. Partially Inside (Intersecting): One endpoint lies inside the clipping window (region code 0000), and the other lies outside (non-zero region code). In this case, the line intersects the boundary of the window, and clipping must be performed.
     
• While the completely inside and completely outside cases are straightforward, the partially inside case requires more work. You must calculate the intersection point of the line with the clipping window boundary. This intersection point is used to trim the portion of the line that lies outside the window.
  Based on the diagram below, we retain the line from the intersection point (x′, y′) to the endpoint inside the window and discard the portion from the external point to (x′, y′).
  

Numerical Example: Line Clipping Through Three Regions (Left → Inside → Top)

• Clipping Window Boundaries:
• \( x_{\min} = 2 \)
• \( x_{\max} = 8 \)
• \( y_{\min} = 2 \)
• \( y_{\max} = 6 \)
• Given Line Endpoints:
• Point A: \( (0, 3) \) → Region code: 0001 (Left)
• Point B: \( (7, 7) \) → Region code: 1000 (Top)

Step 1: Calculate the slope of the line (m)

\[ m = \frac{y_2 - y_1}{x_2 - x_1} = \frac{7 - 3}{7 - 0} = \frac{4}{7} \]

Step 2: Clip Point A (Left Region: 0001) against Left Boundary \( x = 2 \)

We use the vertical clipping formula to find the new y-coordinate:

\[ y' = y_1 + m \cdot (x_{\text{clip}} - x_1) \] \[ y' = 3 + \frac{4}{7} \cdot (2 - 0) = 3 + \frac{8}{7} = \frac{29}{7} \approx 4.14 \]

New intersection point A′ is: \( (2, 4.14) \)

Step 3: Clip Point B (Top Region: 1000) against Top Boundary \( y = 6 \)

Now use the horizontal clipping formula to find the new x-coordinate:

\[ x' = x_2 + \frac{1}{m} \cdot (y_{\text{clip}} - y_2) \] \[ x' = 7 + \frac{1}{\frac{4}{7}} \cdot (6 - 7) = 7 - \frac{7}{4} = \frac{21}{4} = 5.25 \]

New intersection point B′ is: \( (5.25, 6) \)

Final Clipped Line Segment

• Start: \( A′ = (2, 4.14) \)
• End: \( B′ = (5.25, 6) \)

This visible segment lies entirely within the clipping window. The original segment went through:

1. Left — point A was outside on the left
2. Inside — clipped segment \( A′ \to B′ \)
3. Top — point B was outside the top boundary

Polygon Clipping

• Polygon clipping refers to the process of removing (or "clipping") the parts of a polygon that lie outside a defined clipping window, typically a rectangular region.

• In the above diagram, polygon clipping is performed sequentially — we apply clipping against one boundary at a time: Left, Right, Top, and Bottom.
• Let's begin with left clipping. We conceptually draw a vertical boundary line at \( x = x_{\min} \). Everything to the left of this boundary is considered outside the window and is discarded. Everything to the right is inside and is retained.
• We repeat this process for the remaining boundaries:
  • Right Clipping: Remove parts of the polygon where \( x > x_{\max} \)
  • Top Clipping: Remove parts where \( y > y_{\max} \)
  • Bottom Clipping: Remove parts where \( y < y_{\min} \)
• After clipping against all four sides, the final result is the portion of the polygon that lies entirely within the rectangular window.

• During the clipping process, whenever a polygon edge crosses a window boundary, an intersection point is calculated. These intersection points become new vertices of the clipped polygon.
• The algorithm most commonly used for polygon clipping is the Sutherland–Hodgman polygon clipping algorithm, which works by processing one window edge at a time and outputting the resulting polygon step-by-step.

In the process of polygon clipping, we evaluate each edge (line segment) of the polygon based on how its two endpoints — vertex \( v_1 \) and vertex \( v_2 \) — relate to the current clipping boundary. Each edge can fall into one of four possible cases:

1. Case 1: Outside to Inside (v₁ is outside, v₂ is inside)
   The line segment enters the clipping window. In this case, we calculate the intersection point \( v_1' \) with the clipping boundary and also include \( v_2 \) (since it's inside).
   Output: \( v_1', v_2 \)
2. Case 2: Inside to Outside (v₁ is inside, v₂ is outside)
   The line segment exits the clipping window. We compute the intersection point \( v_2' \), but we do not include \( v_2 \) (since it’s outside).
   Output: \( v_2' \)
3. Case 3: Inside to Inside (both v₁ and v₂ are inside)
   The entire edge is within the clipping window, so we keep the second vertex \( v_2 \) as part of the output polygon.
   Output: \( v_2 \)
4. Case 4: Outside to Outside (both v₁ and v₂ are outside)
   The edge lies completely outside the clipping boundary, so it does not contribute to the output polygon.
   Output: Nothing

This case-by-case approach is applied repeatedly for each edge of the polygon as it is clipped against each boundary (Left, Right, Top, Bottom). The output polygon at each stage becomes the input for the next boundary.

The Core Idea of the Odd-Even Rule

• It’s kind of like a game:
  • Pick the pixel (point) you want to test.
  • From that point, draw an imaginary horizontal line to the right.
  • Count how many times that line crosses the edges of the polygon.
  • Now check the number:
    • If it’s odd → the point is inside the shape.
    • If it’s even → the point is outside the shape.
• That’s it! Simple logic.

Point Example (Inside)

• Let’s say we have a triangle like this:
  
• We’re testing the point ●.
• We draw a ray from ● to the right → it crosses 1 edge of the triangle.
• = That’s an odd number → so ● is inside the triangle!

Another Point Example (Outside)

• Now look at this:
  
• Here, the point ● is clearly outside.
• You draw a ray to the right → it crosses 0 edges.
• = That’s even → so the point is outside.

Flood Fill Algorithm

• The Flood Fill algorithm is used in computer graphics to fill a connected region with a specific color. Starting from a seed point, it recursively (or iteratively) fills all neighboring pixels of the same initial color with a new color, until it reaches the boundary of the region.
• It is commonly implemented in paint applications (e.g., the "bucket" tool in MS Paint) and is an essential part of region filling in raster graphics.

Key Idea

• Given:
  • A starting point (x, y)
  • A target color (the color to be replaced)
  • A fill color (the new color to apply)
• The algorithm replaces the target color with the fill color at the seed point and continues this process for all connected pixels that have the same target color.

Variants

• Flood fill can be implemented in two ways, based on how many neighboring pixels are considered:

4-Connected Pixels

8-Connected Pixels

Recursive Algorithm (4-Connected)

Pseudocode

                    
void floodFill(int x, int y, int targetColor, int fillColor) {
    // 1. If the current pixel is not the target color, stop (nothing to replace)
    if (getPixel(x, y) != targetColor)
        return;

    // 2. If the current pixel is already filled with the fill color, stop (already done)
    if (getPixel(x, y) == fillColor)
        return;

    // 3. Change the pixel color from targetColor to fillColor
    setPixel(x, y, fillColor);

    // 4. Repeat the same process for the 4 neighboring pixels
    floodFill(x + 1, y, targetColor, fillColor); // move right
    floodFill(x - 1, y, targetColor, fillColor); // move left
    floodFill(x, y + 1, targetColor, fillColor); // move down
    floodFill(x, y - 1, targetColor, fillColor); // move up
}
                    
                

Working Mechanism

• Check Base Case: If the current pixel’s color is not the target color or is already filled, return.
• Change Color: Set the pixel’s color to the new fill color.
• Recursively Call: Apply the algorithm to each of the neighboring pixels.
• This continues until all connected pixels with the target color are replaced.

Limitations

Boundary-Fill Algorithm – Technical Notes

• The Boundary-Fill Algorithm is a region-filling technique in raster graphics. It is used to fill closed figures by starting from a seed point inside the boundary and spreading outwards until a boundary color is encountered.
• Unlike Flood Fill (which fills all areas of a target color), Boundary Fill works based on a boundary color, and fills everything inside that boundary regardless of the initial color.

Use Case Example

• Think of coloring a circle drawn on a canvas. You don’t want the color to leak outside the circle, so you define the circle outline as the boundary, and begin filling from a point inside the circle. The algorithm fills all connected pixels until it hits the edge of the circle (boundary color).

Types of Boundary Fill

4-Connected Pixels

8-Connected Pixels

Algorithm Steps

• Inputs:
  • x, y → Starting seed point (inside region)
  • boundaryColor → Color of the edge/boundary
  • fillColor → Color to fill inside the region

Recursive Pseudocode (4-connected)

                    
void BoundaryFill4(int x, int y, int fillColor, int boundaryColor) {
    // 1. Get the color of the current pixel
    int currentColor = getPixel(x, y);

    // 2. If the current pixel is not the boundary AND not already filled
    if (currentColor != boundaryColor && currentColor != fillColor) {
        // 3. Fill the current pixel with the fill color
        setPixel(x, y, fillColor);

        // 4. Recursively fill the 4 neighboring pixels (4-directional)
        BoundaryFill4(x + 1, y, fillColor, boundaryColor); // right
        BoundaryFill4(x - 1, y, fillColor, boundaryColor); // left
        BoundaryFill4(x, y + 1, fillColor, boundaryColor); // down
        BoundaryFill4(x, y - 1, fillColor, boundaryColor); // up
    }
}
                    
                

• Note: For 8-connected version, add diagonal calls too.

Important Conditions

• The fill stops when a boundary color pixel is encountered.
• Filling does not overwrite pixels already filled (to prevent infinite recursion).
• The algorithm assumes that the boundary forms a closed loop.

Working Mechanism (Step-by-Step)

• Read the color at the current pixel.
• If it's neither the boundaryColor nor the fillColor, fill it with fillColor.
• Recursively apply the fill operation to neighboring pixels.

Iterative Approach (Optional)

• Just like in Flood Fill, the recursive version may lead to stack overflow on large regions. An iterative method using a stack (manual DFS) is safer in practice.

Boundary Fill vs Flood Fill – Comparison

Example (Conceptual)

• Assume we have a black-bordered rectangle on screen (black is boundary color). The inner area is white.
  • Seed Point: (100, 100)
  • boundaryColor: black
  • fillColor: red
• The algorithm starts at (100, 100) and colors every pixel red until it touches the black boundary.