Trying to recursively find the area of a polygon

Question

Trying to calculate the area of a polygon recursively using the shoelace theorem and splitting it into triangles.

public static double calculatePolygonArea(ArrayList<Point> points) {
    if (points.size() < 3) {
        return 0;
    }
    if (points.size() == 3) {
        return calculateTriangleArea(points.get(0), points.get(1), points.get(2));
    }
       
    return calculateTriangleArea(points.get(0), points.get(1), points.get(2)) +
           calculatePolygonArea(new ArrayList<>(points.subList(1, points.size())));
}

private static double calculateTriangleArea(Point p1, Point p2, Point p3) {
    return Math.abs((p1.getX() * p2.getY() + p2.getX() * p3.getY() + p3.getX() * p1.getY()
            - p1.getY() * p2.getX() - p2.getY() * p3.getX() - p3.getY() * p1.getX()) / 2.0);
}

The code does not return the correct area and its always less than the actual area.

Answer 1

I think the problem stems from how you're reducing the polygon's points. (You're forming a triangle with the first three points and then removing the second point from the list for the next recursion.) While this should theoretically work for convex polygons, ensuring that all triangles are valid, it doesn't handle the geometrical relationships properly, leading you to get a low-balled area.

here's a possible fix:

public static double calculatePolygonArea(ArrayList<Point> points) {
  if (points.size() < 3) {
    return 0;
  }
  if (points.size() == 3) {
    return calculateTriangleArea(points.get(0), points.get(1), points.get(2));
  }

  ArrayList<Point> newPoints = new ArrayList<>(points);

  newPoints.remove(1); // remove the point that was just used

  return calculateTriangleArea(points.get(0), points.get(1), points.get(2))
      + calculatePolygonArea(newPoints); // recurse with the updated list of points
}

this ensures the first point is always used as a vertex in the triangles being formed

this does assume you're using convex polygons, for non-convex polygons this approach probably won't accurately calculate the area due to assuming that a direct line between points does not intersect the polygon itself

---

edit: unneeded, but fun optimization
a further optimization would be to avoid creating new lists, you could do this by using indices to track the current "view" of the polygon, which would decrease memory usage significantly.

public static double calculatePolygonArea(ArrayList<Point> points) {
  return calculateAreaRecursive(points, 0, points.size());
}

// overloaded recursive function using indices
private static double calculateAreaRecursive(
    ArrayList<Point> points, int start, int end) {
  int n = end - start;
  if (n < 3) {
    return 0;
  }
  if (n == 3) {
    return calculateTriangleArea(
        points.get(start), points.get(start + 1), points.get(start + 2));
  }

  double triangleArea = calculateTriangleArea(
      points.get(start), points.get(start + 1), points.get(end - 1));

  return triangleArea + calculateAreaRecursive(points, start + 1, end);
}