Area of a irregular shape

Question

I have set of points which lies on the image. These set of points form a irregular closed shape. I need to find the area of this shape. Does any body which is the normal algorithm used for calculating the area ? Or is there any support available in libraries such as boost? I am using C++.

Answer 1

There's a summation formula for that.

Answer 2

If you polygon is simple (it doesn't have any point in common except for the pairs of consecutive segments) then wikipedia comes to help you:

The formula for the area is

(it assumes that the last point is the same of the first one)

You can easily implement it as

float area = 0.0f;

for (int i = 0; i < numVertices - 1; ++i)
  area += point[i].x * point[i+1].y - point[i+1].x * point[i].y;

area += point[numVertices-1].x * point[0].y - point[0] * point[numVertices-1].y;

area /= 2.0f;

Of course vertices must be ordered according to their natural following in the polygon..

Answer 3

You might want to be more precise, possibly even providing a graphical example.

For instance, if the points you have are merely pixels, then the number of pixels equals the area. But if the points are the corners of a polygon, then the area of the polygon isn't that easily determined. You'd use polygon triangulation, and sum the areas of the triangles obtained.

Answer 4

Note: If you don't know the order of the points and cannot guarantee that your polygon is convex, it is not possible to determine the ordering of the shape, since there may be more than one possible order the points which produces a polygon. If you do know that the polygon is convex, determining the ordering of the points is easy. Merely sort the points by angle from one particular point., with the first point being the one that forms a line between itself and the initial point such that all the other points are on the same side of the line. The triangles formed by this process can also be used to calculate the area.

Answer 5

There is support for area calculation of polygons in Boost.Geometry (which isn't yet accepted into boost and which is very confusing to use). Otherwise you would have to determine the polygon that is defined by your points first. From the looks of it all of your points are vertices of the polygon so this is a simply a matter of ordering your point sets correctly. Another possibility is that you are looking for the convex hull of your point set (see http://en.wikipedia.org/wiki/Convex_hull_algorithms).

Answer 6

Without modesty, I refer you to my answer to another question http://stackoverflow.com/questions/1667310/combined-area-of-overlapping-circles/1667368#1667368. Monte Carlo is robust, easy-to-parallelise and will, eventually, give you an answer to the accuracy you require.

Answer 7

The simplest way to do this is probably to triangulate your shape and calculate the area of the triangles. Dave Eberly has a library called (Boost license) that may help with the triangulation; there is more information here. Look for TriangulateEC, for example.

Answer 8

i think integration works i remember doing that a long time ago

Answer 9

I have a similar (GIS) issue with small PNG files .. i'll probably end up just counting pixels raster-style (the shapes have AFAIK been entered by overtracing with a graphic tablet, or onscreen with a mouse, or somesuch) ..