How do I calculate the area of a non-convex polygon?

Question

Assuming that the polygon does not self-intersect, what would be the most efficient way to do this? The polygon has N vertices. I know that it can be calculated with the coordinates but is there another general way?

Answer 1

The signed area, A(T), of the triangle T = ((x1, y1), (x2, y2), (x3, y3)) is defined to be 1/2 times the determinant of the following matrix:

|x1 y1 1|
|x2 y2 1|
|x3 y3 1|

The determinant is -y1*x2 + x1*y2 + y1*x3 - y2*x3 - x1*y3 + x2*y3.

Given a polygon (convex or concave) defined by the vertices p[0], p[1], ..., p[N - 1], you can compute the area of the polygon as follows.

area = 0
for i in [0, N - 2]:
    area += A((0, 0), p[i], p[i + 1])
area += A((0, 0), p[N - 1], p[0])
area = abs(area)

Using the expression for the determinant above, you can compute A((0, 0), p, q) efficiently as 0.5 * (-p.y*q.x + p.x*q.y). A further improvement is to do the multiplication by 0.5 only once:

area = 0
for i in [0, N - 2]:
    area += -p[i].y * p[i+1].x + p[i].x * p[i+1].y
area += -p[N-1].y * p[0].x + p[N-1].x * p[0].y
area = 0.5 * abs(area)

This is a linear time algorithm, and it is trivial to parallelize. Note also that it is an exact algorithm when the coordinates of your vertices are all integer-valued.

Link to Wikipedia article on this algorithm

Answer 2

The best way to approach this problem that I can think of is to consider the polygon as several triangles, find their areas separately, and sum them for the total area. All polygons, regular, or irregular, are essentially just a bunch of triangle (cut a quadrilateral diagonally to make two triangles, a pentagon in two cuts from one corner to the two most opposite ones, and the pattern continues on). This is quite simple to put to code.

A general algorithm for this can be coded as follows:

function polygonArea(Xcoords, Ycoords) { 
  numPoints = len(Xcoords)
  area = 0;         // Accumulates area in the loop
  j = numPoints-1;  // The last vertex is the 'previous' one to the first

  for (i=0; i<numPoints; i++)
    { area = area +  (Xcoords[j]+Xcoords[i]) * (Ycoords[j]-Ycoords[i]); 
      j = i;  //j is previous vertex to i
    }
  return area/2;
}

Xcoords and Ycoords are arrays, where Xcoords stores the X coordinates, and Ycoords the Y coordinates.

The algorithm iteratively constructs the triangles from previous vertices.

I modified this from the algorithm provided Here by Math Open Ref

It should be relatively painless to adapt this to whatever form you are storing your coordinates in, and whatever language you are using for your project.