Get this book > Problems on Array: For Interviews and Competitive Programming
Reading time: 30 minutes  Coding time: 10 minutes
Given Coordinates of vertices of polygon, Area of Polygon can be calculated using Shoelace formula described by Mathematician and Physicist Carl Friedrich Gauss where polygon vertices are described by their Cartesian coordinates in the Cartesian plane. This takes O(N) multiplications to calculate the area where N is the number of vertices.
Different Approaches
There are various methods to calculate Area of Polygon, Following are some of the ways :

Finding Area of Regular Polygon using their Apothems
1.1 Area = 1/2 * Perimeter * Apothem
Perimeter = sum of length of all sides.
Apothem = a segment that joins the polygon's center to the midpoint of any side that is perpendicular to that side 
Finding Area of known Basic Regular Polygon :
Formula
where x is the xth coordinate of vertice, similarly y is the yth coordinate of vertice. Indexing of vertices starts from 1,2,3.....n. det is the determinant of successive crossmultiplication of coordinate vertices of polygon.
From above algorithmformula the computer have to calculate two different sums that could potentially lead to very high numbers, and these numbers could generate an overflow error if they reach the maximum capacity of an doublevalue. Hence,
The Shoelace formula can be rewritten as follows:
Algorithm
This algorithm consists of rigorous crossmultiplication between corresponding coordinate pairs of the different vertices of a polygon to find the magnitude of area enclosed.
step 1 : List down all the coordinates of vertices of Polygon and note the x and y coordinates in two separate columns in the table having same entry of coordinates in first and last row of table.
step 2 : Calculate the sum of multiplying each x coordinate with the y coordinate in the row below (wrapping back to the first line when you reach the bottom of the table).
step 3 : Calculate the sum of multiplying each y coordinate with the x coordinate in the row below (wrapping back to the first line when you reach the bottom of the table).
step 4 : Subtract the second sum from the first sum, get the Absolute value Difference.
step 5 : Divide the resulting Absolute Difference value by 2 to get the magnitude of Area of the Polygon.
step 6 : Exit.
Example
Let the vertices of polygon be (1, 2), (3, 4), and (5, 7).
step 1 : According to Shoelace Algorithm arrange the given coordinates in tabular form.
Vertices in Tabular Form as follows :
1 2
3 4
5 7
1 2 [written twice]
step 2: Calculating the sum of multiplying each x coordinate with the y coordinate in the row below,
1 \ 2
3 \ 4
5 \ 7
1 2
i.e : 1*4 + 3*7 + 5*7 = 60
i.e : sum1 = 60
step 3: Calculating the sum of multiplying each y coordinate with the x coordinate in the row below,
1 / 2
3 / 4
5 / 7
1 2
i.e : 2*3 + 4*5 + 7*1 = 33
i.e : sum2 = 33
step 4 :
absolute(sum1  sum2) = 60  33
= 27
step 5 :
Area of Polygon = 1/2 * (absolute(sum1  sum2))
= 1/2 * (27)
= 13.5
Area of Polygon is 13.5 square units.
Implementation
#include <iostream>
class AreaOfPolygon
{
public:
AreaOfPolygon(int numberOfVertices, double *x, double *y) : numberOfVertices_(numberOfVertices), X(x), Y(y) {}
double calculateArea();
private:
int numberOfVertices_;
double* X;
double* Y;
};
double AreaOfPolygon::calculateArea()
{
//dynamic allocating array to store coordinates of vertices of polygon.
X = new double[numberOfVertices_];
Y = new double[numberOfVertices_];
std::cout << "\nEnter the Coordinates of Vertices of Polygon. ";
for (int i = 0; i < numberOfVertices_; i++)
{
std::cout << "\nEnter X[" << i + 1 << "]Coordinate : ";
std::cin >> X[i];
std::cout << "\nEnter Y[" << i + 1 << "]Coordinate : ";
std::cin >> Y[i];
}
// Initialze area
double areaOfPolygon = 0.0;
// Implementing shoelace formula
int j = numberOfVertices_  1;
for (int i = 0; i < numberOfVertices_; i++)
{
areaOfPolygon += (X[j] + X[i]) * (Y[j]  Y[i]);
j = i; // j is referring to previous vertex to i
}
return abs(areaOfPolygon / 2.0);
}
int main()
{
int tnumberOfVertices;
std::cout << "\nEnter the Number of Vertices of Polygon : ";
std::cin >> tnumberOfVertices;
AreaOfPolygon aArea(tnumberOfVertices, NULL, NULL);
std::cout << "\nArea of Polygon : " << aArea.calculateArea() << " square units.";
}
Complexity
The time and space complexity of Shoelace Algorithm is :
 Worst case time complexity:
Î˜(n)
 Average case time complexity:
Î˜(n)
 Best case time complexity:
Î˜(n)
 Space complexity:
Î˜(1)
where n is the Number of Vertices present in Polygon. The value of Complexity depends on the number of crossmultiplication of corresponding coordinates done of vertices of Polygon, which inturn depends on number of vertices polygon is containing, hence time complexity of algorithm is directly proportional to n.