4

I have a list/array of 2D points which form a non-convex non-self-intersecting shape. I want to calculate the area enclosed by that polygon.

First I need to form a polygon with the points that I get provided as a 'curve-walk' (non self intersecting). If I can triangulate that polygon I can calculate the area ( I can tolerate a small relative error).

Using scipy's scipy.spatial.ConvexHull() results in the wrong shape and area , obviously, but I have not found a available algorithm in the big math packages which does this.

Can anyone tell me how to do that ?

zython
  • 1,176
  • 4
  • 22
  • 50
  • 6
    https://stackoverflow.com/questions/24467972/calculate-area-of-polygon-given-x-y-coordinates – SteveJ Dec 05 '17 at 16:13
  • Some arrays of points can be interpreted as more than one non-convex polygon, even with your constraint of non-intersecting. How is the program supposed to calculate a polygon area in this ambiguous situation? – Mr. T Dec 05 '17 at 16:16
  • @Piinthesky well one line of the triangles is always known, it is the line from one point on the curve to the next, I thought someone already had thought of an algorithm which does this – zython Dec 05 '17 at 16:21
  • Maybe your sets will never have this problem, but I think of a rectangle with one point inside of it. This can give rise to four different non-convex pentagons with different areas. – Mr. T Dec 05 '17 at 16:24
  • @Piinthesky maybe you misunderstand the term "curve", curve in this context is more like a path if that makes sense – zython Dec 05 '17 at 16:26
  • OK, if this problem can't occur in your data sets, you don't have to think about it. – Mr. T Dec 05 '17 at 16:31
  • @Piinthesky ok excuse the question, but how do you propose I could calculate the area ? – zython Dec 05 '17 at 17:41
  • Python beginner here, so not really aware of Python libraries. I assume, the strategy depends on your data set. Subtract concave areas from convex hull figure? Find point inside the polygon and add up triangle areas for each pair of two consecutive points? – Mr. T Dec 05 '17 at 18:55

1 Answers1

15

use the shapely module available for both Python 2.7 and 3

In [41]: from shapely.geometry import Polygon

In [48]: coords  = ((-1, 0), (-1, 1), (0, 0.5), (1, 1), (1, 0), (-1, 0))

In [49]: polygon = Polygon(coords)

In [50]: polygon.area
Out[50]: 1.5
ShpielMeister
  • 1,417
  • 10
  • 23