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.

Answer 3

1. Take 3 consecutive points from the polygon.
2. Calculate the area of the resulting triangle.
3. Remove the middle of the 3 points from the polygon.
4. Do a test to see if the removed point is inside the remaining polygon or not. If it's inside subtract the triangle area from the total, otherwise add it.
5. Repeat until the polygon consists of a single triangle, and add that triangle's area to the total.

Edit: to solve the problem given by @NicolasMiari simply make two passes, on the first pass only process the vertices that are inside the remainder polygon, on the second pass process the remainder.

Answer 4

The "Tear one ear at a time" algorithm works, provided the triangle you remove does not contain "holes" (other vertices of the polygon).

That is, you need to choose the green triangle below, not the red one:

However, it is always possible to do so (Can't prove it mathematically right now, but you'l have to trust me). You just need to walk the polygon's vertices and perform some inclusion tests until you find a suitable triple.

Source: I once implemented a triangulation of arbitrary, non-intersecting polygons based on what I read in Computational Geometry in C by Joseph O'Rourke.