Unit - II

What is Polygon ?............

 Polygon is a representation of the surface.

 It is primitive which is closed in nature.
 It is formed using a collection of lines. It is also called as
many-sided figure.
 The lines combined to form polygon are called sides or
edges. The lines are obtained by combining two vertices.
 Unit - II

What is Polygon ?............

• Polygon is the combination of two words, i.e. poly (means

many) and gon (means sides).
• A minimum of three line segments is required to connect
end to end, to make a closed figure.
• Thus a polygon with a minimum of three sides is known as
Triangle and it is also called 3-gon.
• An n-sided polygon is called n-gon.
 Unit - II

 A polygon is a closed two-

dimensional figure composed
of straight-line segments that
meet at their endpoints.
 The line segments of polygons
are called sides, and each
endpoint is called a vertex.

 Polygons have at least three

sides and three angles, and
their sides must be straight.
 Unit - II

Examples of polygons. Notice their straight sides and closed

endpoints.
 Unit - II

A polygon cannot have any curve sides.

Open-sided figures and shapes with curves
are examples of non-polygon figures.
Unit - II
 Polygons and non Polygons Unit - II

Polygons non Polygons

 Unit - II

Examples Polygon ?............

Triangle

Rectangle

Hexagon

Pentagon
 Polygon (Definition) Unit - II

Polygon is a figure having many slides. It may be represented as a number

of line segments end to end to form a closed figure. The line segments
which form the boundary of polygon are called as edges or slides of
polygon. The end of the side are called the polygon vertices.

Triangle is the most simple form of polygon having three side and
three vertices. The polygon may be of any shape.
9
 Unit - II
Types of Polygon

1. Convex

2. Concave

3. Complex

10
 Unit - II
Convex Polygon

Convex polygon is a polygon in which if we take any points which are

surely inside the polygon and if we draw a joining these two points and
if all the points on that line lies into the polygon, then such a polygon is
called as convex polygon.

11
 Unit - II
Concave Polygon

Concave polygon is a polygon in which if we take any two points

which are surely inside the polygon and if we draw a line joining
these two points and if all the points on that line are not lying inside
the polygon, then such a polygon is called as concave polygon.

12
 Unit - II
Complex Polygons
In a computer graphics, a polygon which is neither convex nor concave
is referred as complex polygons.

The complex polygon includes any polygon which intersects itself of

the polygon which overlaps itself. The complex polygon has a
boundary.

13
 Unit - II
Polygon Representation

OP X Y

6 5 5

2 7 5 A(5,5) B(7,5)
2 9 3

2 7 1 F(3,3) C(9,3)

2 5 1

2 3 3 E(5,1) D(7,1)

2 5 5

14
 Unit - II
Inside Test Methods

1. Even-odd Method

2. Winding Number Method

15
 Unit - II
Even - Odd Methods

x4,y4
Outside A
Outside C A
Point ‘B’
Point ‘B’
x3,y3
x1,y1 Count even
Count Odd
Fig. 3.2.3 Fig. 3.2.4

x2,y2 A

Fig. 3.2.2 A
B C

B C D A

Fig. 3.2.5

16
 Unit - II
Winding Number Methods

Newly
drawn line
C A
1 B
-1 1
1
Fig. 3.2.8
Fig. 3.2.7

+1 -1
C D A
B

Fig. 3.2.9
17
 Unit - II
Winding Number Methods
Case I
Case II
-1
-1
C D
D B A
B A
C -1
-1 +1
+1

Fig. 3.2.10 (a) Fig. 3.2.10 (b)

Case III

C D
B A
+1
-1 -1

Fig. 3.2.10 (c)

18
 Unit - II
Polygon Filling

Polygon Filling
Algorithm

Pixel Level Geometric Level

1. Boundary Fill Algorithm 1. Scan Line Algorithm

2. Flood Fill (Seed Fill) Algorithm

3. Edge Fill Algorithm

4. Fence Fill Algorithm

19
 Unit - II
4-connected Method

In this 4 neighboring points of a current test point are tested.

These are pixel positions that are right, left, above and below of current pixels as shown in figure 2.26

8-connected Method
Here 8 neighboring pixels of current test pixel are tested.
These pixel positions are left, right, above and 4 – diagonal positions of current pixel as shown in figure
2.27

20
 Unit - II
Boundary Fill Algorithm

The following procedure illustrate a recursive method for boundary fill by using 4-connected method.

bfill (x, y, newcolor)

{
current = getpixel (x, y);
if (current != newcolor)) && (current != boundarycolor)

{
putpixel (x, y, newcolor);
bfill (x+1, y, newcolor);
bfill (x-1, y, newcolor);
bfill (x, y+1, newcolor);
bfill (x, y-1, newcolor);
}

21
 Unit - II
Flood Fill (Seed fill) Algorithm

The following procedure illustrate a recursive method for flood fill by using 4-connected method.

F-fill (x, y, newcolor)

{ current = getpixel (x, y);
if (current != newcolor)
{ putpixel (x, y, newcolor);
f-fill (x-1, y, newcolor);
f-fill (x+1, y, newcolor);
f-fill (x, y-1, newcolor);
f-fill (x, y+1, newcolor);
}
}

22
 Unit - II
Scan line Algorithm

(0,0)
Edge y x y x Slope
A(x1, y1)
max max min min
y min D(x4, y4) AB y2 x2 y1 x1 m1

AD y4 x4 y1 x1 m2

C(x3, y3) CD y3 x4 Y4 x4 m3
y max
B(x2,y2)
BC y2 x2 y3 x3 m4
Fig. 3.4.1
Fig. 3.4.1

23
 Unit - II
Scan line Algorithm

A(x1,y1)
y min Edge y x y x Slope
max max min min
AB y2 x2 y1 x1 m1

BC y2 x2 y3 x3 m4

y2-2 CD y3 x3 Y4 x4 m3
y2-2
AD y4 x4 y1 x1 m2
y max =y2
B(x2, y2)
Fig. 3.4.2

24
 Unit - II
Scan line Algorithm
A(x1,y1)
min
D(x4,y4) Edge y x y x Slope
D(x4,y4) Y min
max max min min
AB y1 x1 y2 x2 m1
B BC y1 x1 y5 x3 m2
E
(x2,y2)
C(x3,y3) (x5,y5)
C CD y3 x3 Y2 x2 m3
(x3,y3)
Y max AD y x y x m4
A
max (x1,y1)
B(x2,y2)

Fig. 3.4.3 Fig. 3.4.4

25
 Unit - II
Scan line Algorithm

B
P1 P2
P3 E
yp P2 P4
P1 P3
C

Fig. 3.4.5
Fig. 3.4.6

26
 Unit - II
Flood fill Vs Boundary fill Vs Edge fill Vs Fence fill Vs Scan line fill
Flood fill Boundary Fill Edge fill Fence Fill Scan line fill

Need Seed point to Need Seed point to Based on Based on Based on line
start. start. complimenting the complimenting the drawing, polygon is
pixels. pixels. filled.
Current pixels color Current pixels color Pixels which are on Pixels which are on Intersection of
is compared with is compared with right side of an edge right side of an edge polygon edges are
new pixel color. new pixel color and are getting and to the left of found with the scan
boundary color. complemented. fence as well as left line and then the
side of edge and solid lines are drawn
right side of fence between two such
are getting intersection points.
complemented.
Useful for polygons Useful for polygons More number of Less number of Need separate
having single color having multi color pixels are pixels are accessed attention to handle
boundary. boundary. unnecessarily as compared to concave polygons.
accessed. edge fill.

27
 Unit - II
Connected boundary fill Algorithm
To enhance speed of filling colour one may look for alternative of 4-connected.
In this algorithm all adjacent pixels will be consider for filling till the match is true. Algorithm is as follows :

boundary_fill (x, y, f_colour, b_colour)

{
if (getpixel (x, y) != b_colour && getpixel (x, y) != f_colour)
{
putpixel (x, y, f_colour);
boundary_fill (x+1, y, f_colour, b_colour);
boundary_fill (x-1, y, f_colour, b_colour);
boundary_fill (x, y+1, f_colour, b_colour);
boundary_fill (x, y-1, f_colour, b_colour);
boundary_fill (x+1, y+1, f_colour, b_colour);
boundary_fill (x-1, y-1, f_colour, b_colour);
boundary_fill (x+1, y-1, f_colour, b_colour);
boundary_fill (x-1, y+1, f_colour, b_colour);
}
}
28