Is there any algorithm for calculating area of a shape given co-ordinates that define the shape ?

Question

So I have some function that receives N random 2D points.

Is there any algorithm to calculate area of the shape defined by the input points?

Answer 1

You want to calculate the area of a polygon?

(Taken from link, converted to C#)

class Point { double x, y; } 

double PolygonArea(Point[] polygon)
{
   int i,j;
   double area = 0; 

   for (i=0; i < polygon.Length; i++) {
      j = (i + 1) % polygon.Length;

      area += polygon[i].x * polygon[j].y;
      area -= polygon[i].y * polygon[j].x;
   }

   area /= 2;
   return (area < 0 ? -area : area);
}

Answer 2

Defining the "area" of your collection of points may be hard, e.g. if you want to get the smallest region with straight line boundaries which enclose your set then I'm not sure how to proceed. Probably what you want to do is calculate the area of the convex hull of your set of points; this is a standard problem, a description of the problem with links to implementations of solutions is given by Steven Skiena at the Stony Brook Algorithms repository. From there one way to calculate the area (it seems to me to be the obvious way) would be to triangulate the region and calculate the area of each individual triangle.

Answer 3

You can use Timothy Chan's algorithm for finding convex hull in nlogh, where n is the number of points, h is the number of convex hull vertices. If you want an easy algorithm, go for Graham scan.

Also, if you know that your data is ordered like a simple chain, where the points don't cross each other, you can use Melkman's algorithm to compute convex hull in O(N).

Also, one more interesting property of convex hull is that, it has the minium perimeter.

Answer 4

Your problem does not directly imply that there's a ready-made polygon (which is assumed by this answer). I would recommend a triangulation such as a Delaunay Triangulation and then trivially compute the area of each triangle. OpenCV (I've used it with a large number of 2D points and it's very effective) and CGAL provide excellent implementations for determining the triangulation.