Today I came across the following problem:
“If you know the coordinates of the vertices of a polygon with square edges, find the surrounded area. Or more formally given an array of the X and Y coordinates enumerated in a clockwise direction as well as the number numPoints of points. Return the area of the polygon!”
Sometimes simple problems have a simple solution. And this one is such problem. Here is the algorithm:
function polygonArea(X, Y, numPoints) {
area = 0;
j = numPoints-1;
for (i=0; i<numPoints; i++)
{ area = area + X[i] * (Y[j]-Y[i]);
j = i; //j is previous vertex to i
}
return area;
}
The algorithm assumes the usual mathematical convention that positive y points upwards. In computer systems where positive y is downwards (most of them) the easiest thing to do is list the vertices counter-clockwise using the “positive y down” coordinates. The two effects then cancel out to produce a positive area.
How it works?
Consider one side of the polygon. The formula is based on taking the area to the left of the chosen side, all the way to the Y-axis.
Going down one side of the polygon adds all the area.
Then going up the other side of the polygon subtracts all the area, because when a side is going up, Y0-Y1 is a negative number.
You don’t have to start at the top of the polygon. You can start anywhere, go all the way around, and the numbers will still add up to the same value.
Also, it doesn’t matter whether some or all of the polygon’s corners are in the negative-X space, negative-Y space, or both, the result is still the same.
