MVPS’s KBT College of Engineering

Name of Faculty: Dr. V. S. Tidake

Department: Computer Engineering

Maratha Vidya Prasarak Samaj’s

Karmaveer Adv. Baburao Ganpatrao
Thakare College of Engineering
Nashik Maharashtra, India Enging
Polygons - V. S. Tidake 1
Introduction to Polygons,
types and Inside test
UNIT II

Polygons - V. S. Tidake 2
Objective
• Remembering:
• To acquaint the learner with the basic concepts of Computer Graphics
(polygons).
• Understanding:
• To learn the various algorithms for generating and rendering graphical figures.

Polygons - V. S. Tidake 3
Course Outcomes
On completion of the course, learner will be able to–
• CO2: Apply mathematics to develop Computer programs for
elementary graphic operations.
• CO3: Illustrate the concepts of windowing and clipping and apply
various algorithms to fill and clip polygons.

Polygons - V. S. Tidake 4
Polygons
• A polygon is a plane figure that is described by a finite number of
straight line segments connected to form a closed polygonal chain or
polygonal circuit.
• The segments of a polygonal circuit are called its edges or sides.
• The points where two edges meet are the polygon's vertices.
• The interior of a solid polygon is sometimes called its body.
• An n-gon is a polygon with n sides; for example, a triangle is a 3-gon.

Polygons - V. S. Tidake 5
Types of Polygons
• Concave
• Convex
• Complex

Polygons - V. S. Tidake 6
Types of Polygons
•A convex polygon has all interior angles less than 180° (it has no
inward-pointing sides).

•A concave polygon has at least one interior angle greater than 180°.

•A simple polygon encloses a single interior space (boundary) and

does not have self-intersecting sides.

•Complex polygons (also called self-intersecting polygons)

•have self-intersecting sides.
•have sides that cross over each other.
•The classic star is a complex polygon

Polygons - V. S. Tidake 7
Convex polygons

Polygons - V. S. Tidake 8
Concave polygons

Polygons - V. S. Tidake 9
Simple polygon Complex polygon
- Has no intersecting edges. - Has self intersecting edges.

Polygons - V. S. Tidake 10
 Representation of polygon
OP X Y
No. of sides 5 6 5
A(6,5) 2 3 3 Start and
2 5 1 end
2 7 1 point is
B(3,3) C(9,3) Commands same
2 9 3
2 6 5

Commands:
1: MOVE
E(5,1) F(7,1) 2: LINE

Polygons - V. S. Tidake 11
Algorithm to draw polygon
DrawPolygon(arrayX, arrayY, N)
Input: arrayX and arrayY contain vertices of polygon
N: No. of vertices of polygon
Begin
If N < 3, print “polygon size error”, return
Move_ABS(arrayX[1], arrayY[1])
For i=2 to N+1
Line_REL(arrayX[i], arrayY[i])
End for
return
end

Polygons - V. S. Tidake 12
Inside test of polygons
• This method is also known as counting number method.
• While filling an object, we often need to identify whether particular
point is inside the object or outside it.

• 2 methods to identify whether particular point is inside an object or

outside:
1. Even-odd method
2. Winding number method

Polygons - V. S. Tidake 13
Even-Odd Method
• In this technique, we will count the edge crossing along the line from
any point (x,y) to infinity.
• If the number of intersections is odd, then the point (x,y) is an interior
point.
• If the number of intersections is even, then the point (x,y) is an
exterior point.

Polygons - V. S. Tidake 14
Even-Odd Method (contd.)
• Draw a line segment between a test point and a point outside
polygon.

• How to find a point outside polygon?

• Point with x coordinate less than the smallest x coordinate of polygon
vertices.
• Y coordinate can be same or any value of test point.

Polygons - V. S. Tidake 15
 Even-Odd Method (contd.)
• Point P – test point
A(6,5) • Point Q – outside
• No. of intersections with
B(3,3) C(9,3) polygon boundary = 1 ( odd)
• Hence P is inside polygon.
Q P

E(5,1) F(7,1)

Polygons - V. S. Tidake 16
 Even-Odd Method (contd.)
• Test fails when intersection point is
A(6,5) a vertex.
• For P, no. of intersections = 2 (even)
B(3,3) C(9,3)

Q P

Polygons - V. S. Tidake 17
 Even-Odd Method (contd.)
• Modification to rule
A(6,5) • Look at the other end points of 2
edges that meet at this vertex.
1. If both points lie on the same
B(3,3) C(9,3) side of constructed line segment
PQ, intersection point counts as
an even no. of intersections.
• Ex. E and F are on same side of PQ,
hence intersection at D is counted
as 2. thus PQ intersects at 3 points,
D P hence P is inside polygon
Q

E F Polygons - V. S. Tidake 18
Even-Odd Method (contd.)
• Modification to rule
A 2. If both points lie on the
opposite side of constructed line
segment PQ, intersection point
Q B C counts as a single intersection.
P
• Ex. E and A are on opposite side
of PQ, hence intersection at B is
counted as 1. thus PQ intersects
at 1 point, hence P is inside
E F polygon.

Polygons - V. S. Tidake 19
Winding Number method
• Stretch a piece of elastic between the test point and point on the
polygon boundary.
• The end attached to the polygon is moved along the boundary until it
has made one complete circuit.
• When all the edges of the polygon are covered by the elastic, examine
the test point
• If test point has wound at least once, then the point is inside the
polygon.
• If there is no net winding, then the point is outside the polygon.

Polygons - V. S. Tidake 20
 • Give directions to all the edges of the
Contd.. polygon.
• Draw a scan line from the test point towards
the left most of X direction.
• Give the value 1 to all the edges which are
going to upward direction and all other -1.
• Check the edge direction values from which
the scan line is passing and sum up them.
• If the total sum of this direction value is
non-zero, then test point is an interior
point, otherwise it is an exterior point.
• Ex. In figure, sum up the direction values
from which the scan line is passing then the
total is 1 – 1 + 1 = 1 which is non-zero. So
the point is said to be an interior point.

Polygons - V. S. Tidake 21
Winding Number method (contd.)
• count = -1
A • P is inside polygon

Q B P C

E F

Polygons - V. S. Tidake 22
Winding Number method (contd.)
• count = 1 - 1 = 0
A • P is outside polygon

Q B C P

E F

Polygons - V. S. Tidake 23
Winding Number method (contd.)
• Special case 1:
A • Intersection point is a vertex.
• Look at the other end points of 2
edges that meet at this vertex.
Q B C P • If both points lie on the opposite
side of constructed line segment
PQ, consider count of any one
edge.
• count = 1 - 1 = 0
• P is outside polygon
E F

Polygons - V. S. Tidake 24
Winding Number method (contd.)
• Special case 1:
A • Intersection point is a vertex.
• count = 1 -1 = 0
• P is outside polygon.
Q B C P

E F

Polygons - V. S. Tidake 25
Winding Number method (contd.)
• Special case 2:
A • Intersection point is a vertex.
• If both points lie on the same side
of constructed line segment PQ,
Q B P C consider count as 0.
• count = -1 + 0 = -1
• P is inside polygon.

E F

Polygons - V. S. Tidake 26
References
• S. Harrington-Computer Graphics, 2nd Edition, McGraw-Hill
Publications, 1987, ISBN 0 – 07 – 100472 – 6.
• [Link]
[Link]

Polygons - V. S. Tidake 27
 THANK YOU

Maratha Vidya Prasarak Samaj’s Phone Number: 0253-2571439/ 0253-2582891 Email id: principal@[Link]
KBT College of Engineering Nashik College website: [Link]
Fax number: 0253-2317016
Udoji Maratha Boarding Campus, Gangapur Road, Nashik-422013. Maharashtra
India