Area of a polygon
Abstract—This work discusses finding out the are of a given polygon with n number of edges or sides. The time complexity and scalability of the algorithm are analyzed. The results indicate that the algorithm is scalable and efficient.
Keywords: polygon, triangles, polygon.
I. Introduction
Area of a given polygon with n number of edges can be found by different methods like finding the centroid of a given polygon then apply area formula to get the area of that polygon. Using the divide and conquer technique to find the area of a given polygon, this technique is used when the given problem is larger or more complex then divide the problem until we get smaller subproblems than find solutions for that smaller subproblems then combine the results of smaller subproblems. Now we obtain the result for a complex problem. To find the area for a triangle (a simple polygon) we know the formula to find the area.
Area = ½ * base* height. (1)
Polygon: A plane shape (two-dimensional) with straight sides.
Examples: triangles, rectangles, and pentagons.
Triangles of a Polygon: The triangles of a polygon are the triangles created by drawing line segments from one vertex of a polygon to all the others.
According to divide and conquer method to find the area of a polygon with n number of edges we will form a polygon with that edges then apply the method to divide the polygons into smaller triangles then compute the area of smaller triangles next take the areas of smaller triangles to combine the results it will give you the area of a given polygon and the below table describes the name of regular polygon and number edges that polygon consists of.
Number of edges
n
|
Polygon name
|
Total triangles
t
|
4
|
Tetragon
|
2
|
5
|
Pentagon
|
3
|
6
|
Hexagon
|
4
|
7
|
Heptagon
|
5
|
8
|
Octagon
|
6
|
9
|
Nonagon/Enneagon
|
7
|
10
|
Decagon
|
8
|
11
|
Undecagon
|
9
|
12
|
Dodecagon
|
10
|
Figure 1 type of polygons with the number of triangles.
For a given polygon of n edges draw as many possible diagonals condition here is diagonals should not overlap or intersect each other, below figures show that how to divide the polygon with n number of edges and how many triangles can be formed. To find the area of given polygon divide tetragon as shown below.
To find the area of a tetragon divide tetragon as shown below in fig2.
Figure 2 tetragon divisionTo find the area of a pentagon divide tetragon as shown below in fig3.
Figure 3 pentagon division
Figure 4 hexagon division
Figure 5 heptagon division
Figure 6 nonagon division
Like that divide, all other polygons, for the polygon of n number of edges n-2 triangles can be formed. Compute area of triangles then combine the areas of triangles to the area of a polygon.
II. Algorithm development
The area of a polygon algorithm is developed under the method divide and conquers strategy. For a given number of edges, we are forming a polygon. Than to divide the polygon into triangles by using the above formula
ie., t = n -2. (2)
Where t is total triangles and n is the number of edges of a triangle. Once we divide our polygon into triangles it is easier to compute the area of individual triangles using formula (1). Then combine the areas we obtained that will give you the total area of a polygon using the formula
ie., TArea = (t) * (Area). (3)
Algorithm development steps
Step 1:
Start
Step 2:
Enter the total number of vertex and edges of the polygon.
Step 3:
Divide the polygon into number triangles as shown in figure 2,3,4,5,6.
Step 4:
Find the area of each individual triangle.
Step 5:
Combine the result or area of the individual triangle to get the area of a given polygon.
Step 6:
End or terminate.
III. algorithm and analysis of the algorithm
Algorithm area of the polygon
Input: v, e, t, base, height
Output: polygon_area
{
if( v = = 2 || e = = 2 )
{ can not form a polygon, exit}
else
{can form a polygon}
{ the polygon is triangle}
else
if( v = = 4 || e = = 4 )
{ the polygon is tetragon}
else
if( v = = 5 || e = = 5 )
{ the polygon is pentagon}
/* according to v and e value name/type of polygon will display*/
/*to find number of triangles, this will divide the polygon into several triangles */
For i ß 1 to e-2
Tn (i) ß e – 2
/* to compute the area of individual triangle */
For i ß 1 to tn(i)
Tarea (i)ß (tn (i)) * (1/5 * base * height)
/*to combine the areas of individual triangles*/
For i ß 1 to tarea (i)
Tarea ß Tarea + t area(i)
{ display polygon area, exit}
}
The algorithm analysis is as shown in the below table.
Algorithm steps
|
cost
|
Frequency
|
Input: n, t, base, height
Output: area;
|
||
Read number(n)
|
1
|
1
|
If (n==2)
|
1
|
1
|
then print polygon is not fixed, exit
|
||
else print polygon formed
|
1
|
n
|
read base, height;
|
2
|
1
|
if(n==3) print polygon is triangle
|
1
|
1
|
if(n==4) print polygon is rectangle
|
1
|
1
|
if(n==5) print polygon is pentagon
|
1
|
1
|
if(n==6) print polygon is hexagon
|
1
|
1
|
if(n==7) print polygon is heptagon
|
1
|
1
|
/* to divide and calculate polygon area*/
|
||
tßn-2
|
2
|
n
|
areaß0.5*base*height*t
|
5
|
n
|
print area
|
Figure 3.1 analysis of algorithm steps.
IV. Experimentation and profiling
A priori Analysis:
A Priori Analysis is analyzing the algorithm and calculating the computation time for the algorithm is termed as A Priori Analysis. After having made an analytical review of the algorithm, the calculated time complexity for it is of the O(nlogn).
A Posteriori Analysis:
A Posteriori Analysis is Analysis is done after the execution of the algorithm in the Computer. This Analysis is also called as Profiling.
The below figure shows the execution steps for different polygons.
Polygon
|
Number of sides
|
Execution time
|
Triangle
|
3
|
3.4352ms
|
Tetrahedron
|
4
|
5.397ms
|
Pentagon
|
5
|
5.785ms
|
Hexagon
|
6
|
6.257ms
|
Heptagon
|
7
|
6.853ms
|
Octagon
|
8
|
7.209ms
|
nonagon
|
9
|
7.432ms
|
Decagon
|
10
|
7.923ms
|
Figure 4.1 Different execution times for n-sided polygons
Computing the time complexity:
tworst = O(nlogn).
Tbest = Ω(K) where K is some constant.
Below figure 4.1 shows the time complexity graph for finding out the area of a given polygon with n number of edges.
Figure 4.1 computing time complexity for polygon area algorithm
V. Summary / conclusion
The time complexity for finding the area of a given polygon tΩ α k and tO α nlogn. The worst time complexity of the algorithm tends to nlogn because computational or execution steps vary for a different type of polygons. After all, it depends mainly on the number of edges and how many numbers of triangles can be formed on that polygon?
References
[1] R. Hammons, Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P.Sol´e, The Z4- the linearity of Kerdock, Preparata, Goethals, and related codes.
[2] J. O'Rourke and K. J. Supowit. Some NP-hard polygon decomposition problems. IEEE Trans. Inform. Theory, IT-30:181{190, 1983.
[3] Computer Algorithms by Horowitz E., Sahni S., Rajasekaran S., Galgotia Publications,2001.
[4] R.G. Dromey, How to solve by computer, Prentice Hall of India, New Delhi, 2004.
[5] S. B. Tor and A. E. Middleditch. Convex decomposition of simple polygons. ACM Trans. Graph., 3:244{265, 1984.
