Find the Area of Polygon in Python
This post discusses the implementation of an algorithm to find the area of any convex polygon in Python given its vertices in the form of co-ordinates.
Prerequisites: Basic Input/Output, string and list manipulation and basic functions in Python (refer this)
NOTE: All programs in this post are written in Python 2.7.x but it will work on the latest versions too.
The Algorithm – Area of Polygon
The idea here is to divide the entire polygon into triangles. We then find the areas of each of these triangles and sum up their areas. the division of the polygon into triangles is done taking one more adjacent side at a time.
Given below is a figure demonstrating how we will divide a pentagon into triangles
We start with any random vertex on the pentagon, say A. We now consider the next 2 vertices on either side. In this case, we are going in the clockwise direction, hence B and C. We find the area of triangle ABC (1-Yellow). For the next triangle, we consider the side AC and take the next vertex D, hence triangle ACD (2-Green). Finally, we have a triangle ADE (3-Blue).
Adding the areas of the triangles ABC, ACD and ADE, we get the area of the pentagon.
To find the area of each triangle, we use the co-ordinate geometry formula,
Area = |0.5*(x1(y2-y3)+x2(y3-y1)+x3(y1-y2))|
Where (x1,y1), (x2,y2), (x3,y3) are the vertices of the triangle in the form of co-ordinates
Implementation – Area of Polygon
The implementation in python requires just one condition that the vertices must be supplied to the program. However, it does not matter which vertex the input is starting from or the direction (clockwise or counter-clockwise) in which it is supplied.
Consider the following program,
n = input("Enter Number of Sides: ") x_cords = list() y_cords = list() for k in range(n): x,y = map(int,raw_input("Enter x,y co-ordinate separated by space: ").split(" ")) x_cords.append(x) y_cords.append(y) area = 0 for x in range(n-2): v1,v2,v3 = 0,x+1,x+2 tr_area = abs(0.5*(x_cords[v1]*(y_cords[v2]-y_cords[v3])+ x_cords[v2]*(y_cords[v3]-y_cords[v1])+ x_cords[v3]*(y_cords[v1]-y_cords[v2]))) area += tr_area print "Area of Polygon: ",area
This is how we can find or calculate the area of a polygon in Python.
In this program, we first accept the number of sides and then accept the co-ordinates of each vertex.
To do so, we have used the split() function, which divides the string it is called by, at the argument specified (space in this case). It returns a list containing the elements from each part. Eg: “hello world”.split(” “) will return a list [‘hello’,’world’].
We then use the map function to convert the co-ordinates accepted as strings, that are present in the list into int.
We then unpack this list of two integers into the variables x and y. x and y are added to the end of their respective lists containing co-ordinates.
In the next step, we run a for loop n-2 times. This is because, we first take up 3 sides, followed by 1 additional side every next time. Hence there are n-2 triangles that we will consider.
In each iteration, we assign vertices with indexes. Eg: In iteration 1, the vertices are 0th, 1st and 2nd index in the co-ordinates lists. In iteration 2, its the 0th, 2nd and 3rd and so on. In the (n-2)nd iteration, we will consider 0th, (n-2)th and (n-1)th indexes (NOTE that x=n-3 in last iteration and (n-1)th index represents the last vertex.
We then applied the formula discussed above to find the area of the triangle and keep adding it to the total area. We, however, check if the area obtained is negative and if so, make it positive, before adding it to the total area.
Let us now run the program for the case of a square. The output is as follows:
– This algorithm will not work for some concave polygons cover areas outside the polygon.