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.
- Flood-fill Algorithm
- Boundary-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.
Algorithm of Flood-fill
Procedure flood_fill (p, q, fill_color, Old_color: Integer)
Current = getpixel (p, q)
(Current = Old_color)
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);
Note- Getpixel () defines the color of specified pixel.
Setpixel () set the pixel with the specified color.
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.
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.
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.
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)
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.
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.
Special Cases of Polygon Vertices
There are two special cases of polygon vertices which are given below:
- If both lines intersecting at the vertex lies on the same side of the scan line, then we will consider it as two points.
- 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.