Filled Area Primitives: Area filling is a method or process that helps us to fill an object, area, or image. We can easily fill the polygon. The polygon filling is defined as filling or highlighting all the pixels. The pixels appear inside the polygon shape with any color other than the background color.

There are two algorithms or methods used to fill the polygon.

  • Seed Fill Algorithm
  • Scan Line Algorithm

Seed Fill Algorithm

In this method, we will select a seed or starting point inside the boundary. We can further divide the seed fill into two parts.

Filled Area Primitives
  1. Flood-fill Algorithm
  2. Boundary-fill Algorithm

Flood-fill Algorithm   

Flood-fill algorithm helps to define a region in the boundary, attached to a point in the multi-dimensional array. It is similar to the bucket tool used in the paint program. The stack-based recursive function is used to implement the algorithm. In flood -fill algorithm, we replace all the associated pixels of the selected color with a fill color. We also check the pixels for a particular interior color, not for boundary color.

Filled Area Primitives

Algorithm of Flood-fill

Procedure flood_fill (p, q, fill_color, Old_color: Integer)

Var

      Current: Integer

      Current = getpixel (p, q)

 If

        (Current = Old_color)

Then

       Start

setpixel (p, q, fill_color);

          flood_fill (p, q+1, fill_color, Old_color);

          flood_fill (p, q-1, fill_color, Old_color);

          flood_fill (p+1, q, fill_color, Old_color);

          flood_fill (p-1, q, fill_color, Old_color);

     End;

Note- Getpixel () defines the color of specified pixel.

          Setpixel () set the pixel with the specified color.

Filled Area Primitives

Advantages of Flood-fill algorithm

  • It provides an easy way to fill color in graphics.
  • The Flood-fill algorithm colors the whole area through interconnected pixels by a single color.
  • The algorithm fills the same color inside the boundary.

Disadvantages of Flood-fill Algorithm

  • It is a more time-consuming algorithm.
  • Sometimes it does not work on large polygons.

Boundary-fill Algorithm

It is also known as the “Edge-fill algorithm.” The boundary fill algorithm is used for area filling. We can perform boundary fill where we want to create an attractive painting. In this, we can easily select the interior points. If the object has a particular boundary in a single color, then the algorithm travels each pixel until it reaches the boundary.

Filled Area Primitives

In the Boundary-fill algorithm, we use the 4-connected and 8-connected methods. By the use of a 4-connected or 8-connected method, we can set the new position of the pixels until all the interior points have been filled.

Filled Area Primitives
Filled Area Primitives

Algorithm of Boundary-fill

Procedure boundary fill (p, q, fill color, boundary)

Step 1: Initialize the boundary of the region.

Step 2: Get the interior pixel (p, q). Now, define an Integer called current pixel and assign it to (p, q).

Current = getpixel (p, q)

Step 3: If

                   (current pixel != boundary) and (current pixel != fill)

            Then

                    Setpixel(p, q, fill);

Boundary fill (p+1, q, fill, boundary);

Boundary fill (p-1, q, fill, boundary);

Boundary fill (p, q+1, fill, boundary);

Boundary fill (p, q-1, fill, boundary);

Step 4: End;

Problems with Boundary-fill algorithm

  • Sometimes it may not fill all the regions.
  • In the 4-connected method, it does not fill corner pixels. Because it only checks the adjacent position of the pixel.

Scan-Line Algorithm

The Scan-Line Algorithm is an area filling algorithm. In this algorithm, we can fill the polygons through horizontal lines or scan lines. The scan-line intersects the edges of the polygon, and the polygon is filled between pairs of the intersection. The main purpose of this algorithm is to fill color in the interior pixels of the polygon.

Filled Area Primitives

Special Cases of Polygon Vertices

There are two special cases of polygon vertices which are given below:

  1. If both lines intersecting at the vertex lies on the same side of the scan line, then we will consider it as two points.
  2. If both lines intersecting at the vertex lies on the other side of the scan line, then we will consider it as a single point only.    

Algorithm of Scan line polygon-fill

Step 1: Find the intersection points of the scan line that have edges.

Step 2: Now sort the intersection points by increasing the x coordinate from left to right.

Step 3: Now, we perform the pairing of the intersection points and fill the color inside the pixel pairs.  

Pin It on Pinterest

Share This