area contained in a piecewise straight simply closed curve

Question

I have the plane points pi i=1,...,n and they form a simply closed but not necessarily convex curve. The curve from pi to p(i+1) and from pn to p1 is the straight line. I need an algorithm to compute the area contained.

Answer 1

Let us break down the problem into much smaller, manageable ones.

The idea:
Break it down into triangles and sum their area. In every iteration get a point that is convex (in relation to the one before and after), get the area of that triangle (area(p(i), p(i-1), p(i+1))) and remove that point from the list of relevant point still to be handled.

On the topic of checking if a point is inside a convex polygon, I'll assume the points are going clockwise (if not, reverse them of swap the condition on the angle). Basically, given p(i), p(j), p(k) where i + 1 = j and j + 1 = k (consecutive), the angle between the ledges edge(i, j) and edge(j, k) will tell us if p(j) is concave or convex. This solution can be seen here

totlaArea = 0
listOfPoints = inputtedPoints

getThreeAdjacentPoints(listOfPoints, index) {
  n = listOfPoints.length
  point1 = listOfPoints[pointIndex]
  point2 = listOfPoints[(pointIndex + 1) % n]
  point3 = listOfPoints[(pointIndex - 1) % n]
  return { point1, point2, point3 }
}

getTriangleArea(listOfPoints, index) {
  { point1, point2, point3 } = getThreeAdjacentPoints(listOfPoints, index)
  return calculateTriangleArea(point1, point2, point3)
}

getNextConvexPointIndex(listOfPoints) {
  for index in listOfPoints.length - 1:
    { point1, point2, point3 } = getThreeAdjacentPoints(listOfPoints, index)
    angleBetweenEdges = getAngle(edge(point3, point1), edge(point1, point2))
    if angleBetweenEdges < 180:
      return index

  // Will never actually reach here unless code error:
  return -1
}

while listOfPoints.length > 2:
  pointIndex = getNextConvexPointIndex(listOfPoints)
  triangleAreaOfPoint = getTriangleArea(listOfPoints, pointIndex)
  totalArea += triangleAreaOfPoint
  listOfPoints.remove(pointIndex)

I don't have a mathematical proof at hand, but I'm pretty sure that taking any polygon, it's made up of convex triangles that can be found in the method I describe.

Hope this was helpful.