Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 304
Rella Avatar asked Mar 12 '10 11:03

Rella


3 Answers

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);
}
like image 117
Dead account Avatar answered Nov 13 '22 10:11

Dead account


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.

like image 36
Nathan Avatar answered Nov 13 '22 11:11

Nathan


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.

like image 24
Boolean Avatar answered Nov 13 '22 09:11

Boolean