Polygon Filling Algorithm
Presented by
Asst. Prof. Aparna Joshi
Polygon Filling Algorithm
• An ordered list of vertices forms a polygon.
• Polygon Filling :- The pixels that fall on the border of
the polygon are determined and the pixels that fall inside
are determined in order to color the polygon.
• Polygons are easier to fill since they have linear
boundaries.
• Filling the polygon means highlighting all the pixels which
lie inside the polygon with any color other than the
background color.
Polygon Filling
• There are two basic approaches used to fill the polygon.
Point Inside Test – Even-Odd Method
• Once the polygon is entered in the display file, we can draw the outline of the
polygon.
• To show polygon as a solid object we have to set the pixel inside the polygon as
well as pixels on the boundary of it.
• Now the question is how to determine whether or not a point is inside of a polygon.
• One simple method of doing this is to draw a line segment and count how many
intersections of the line segment with the polygon boundary occur.
• If there are an odd number of intersections, then the point is inside, otherwise it is
outside.
• This method is called the even-odd method of determining polygon inside points.
• This inside test or Even-Odd method is used in scan line method of polygon filling.
Scanline Polygon Filling Algorithm
• Scanline filling is basically filling up of polygons using
horizontal lines or scanlines.
• The purpose of the SLPF algorithm is to fill (color) the
interior pixels of a polygon given only the vertices of the
figure.
• This algorithm works by intersecting scanline with
polygon edges and fills the polygon between pairs of
intersections.
• These intersection points are then sorted from left to right,
and the corresponding positions between each
intersection pair are set to the specified fill color.
Scanline Polygon Filling Algorithm
• Step 1 − Find out the Ymin and
Ymax from the given polygon.
• Step 2 − Scanline intersects
with each edge of the polygon
from Ymin to Ymax. Name
each intersection point of the
polygon. As per the figure
shown above, they are named
as p0, p1, p2, p3.
• Step 3 − Sort the intersection
point in the increasing order
of X coordinate i.e. (p0,p1),
(p1,p2) and (p2,p3).
• Step 4 − Fill all those pair of
coordinates that are inside
polygons and ignore the
alternate pairs.
• Special cases of polygon
vertices:
• If both lines intersecting
at the vertex are on the
same side of the scanline,
consider it as two points.
• If lines intersecting at the
vertex are at opposite
sides of the scanline,
consider it as only one
point.
Basic Terms
• Spatial Coherence :-
The adjacent pixels are likely to have the same
characteristics in polygons. This property is called spatial
coherence.
• Scan line Coherence :-
Adjacent pixels on a scan line are likely to have the same
characteristics. This is called scan line coherence.
Seed Filling Approach
• One way to fill a polygon is to start from a given “seed”, point known
to be inside the polygon and highlight outward from this point i.e.
neighboring pixels until we encounter the boundary pixels.
• Seed fill approach is of two types – Boundary Fill ( Edge Fill
algorithm ) and Flood Fill (Seed Fill )
Boundary Fill Algorithm / Edge Fill Algorithm:
• This algorithm picks a point inside an object and starts to fill until it hits the
boundary of the object.
• The color of the boundary and the color that we fill should be different for this
algorithm to work.
• In this algorithm, we assume that color of the boundary is same for the entire
object.
• Then starting with some seed, any point inside the polygon we examine the
neighboring pixels to check whether the boundary pixel is reached.
• If boundary pixels are not reached, pixels are highlighted and the process is
continued until boundary pixels are reached.
• The boundary fill algorithm can be implementd by 4-connected pixels or 8-
connected pixels.
(a) Four Connected Region (b) Eight Connected Region
Boundary Fill / Edge Fill Algorithm
• 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
4-Connected Polygon
• In this technique, 4-connected pixels are used as shown in
figure.
• We are putting the pixels – above, below, to the right and
to the left of the current pixels and this process will
continue until we find a boundary with different color.
4-Connected Polygon Filling
Algorithm
8-Connected Polygon
• 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.
8-Connected Polygon Algorithm
Flood Fill Algorithm or Seed fill
Algorithm
• Sometimes it is required to fill in an area that is not defined within a single
color boundary. In such cases we can fill areas by replacing a specified
interior color instead of searching for a boundary color. This approach is
called a flood-fill algorithm.
• Like boundary fill algorithm, here we start with some seed and examine the
neighboring pixels. However, here pixels are checked for a specified interior
color instead of boundary color and they are replaced by new color. Using
either a 4-connected or 8-connected approach, we can stop through pixel
positions until all interior point have been filled.
• Recursive algorithm for seed fill methods have difficulty as -
The first difficulty is that if some inside pixels are already displayed
in fill color then recursive branch terminates, leaving further
internal pixels unfilled. To avoid this difficulty, we have to first
change the color of any internal pixels that are initially set to the
fill color before applying the seed fill procedures
4-connected pixels Vs 8-connected pixels
• 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
• 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.
Questions on Polygon Filling Algorithm
1. Explain boundary fill algorithm in detail
2. Explain the steps required to fill the polygon using flood fill technique.
3. What are the steps involved in filling a polygon using the scanline method ?
4. Explain the boundary fill method for 4-connected region to fill a polygon.
5. Write a short note on polygon filling.
6. Explain the scanline algorithm for polygon filling.
7. Describe any one method to test whether the point is inside a polygon.
8. Write a boundary fill procedure to fill 4-connected region.
9. When0 eight-way
0
symmetry is used
0
to obtain
0
a full circle from pixel coordinates generated for
the 0 to 45 or the line 90 to 45 octant, certain pixels are set or plotted twice. This
phenomenon is sometimes referred to as overstrike. Identify the locations where overstrike
occurs.
At locations resulted from the initial coordinates (r, 0) or (0, r) since
(0, r) = (-0, r),
(0,-r) = (-0, -r),
(r, 0 ) = (r, -0) and
(-r, 0 ) = ( -r, -0)
10. What is 4-connected and 8-connected method ?
Thank You
