8

I have a series of points on a plot of the sky. I want to find the area that these points occupy.

To do this I need to find the vertices of a polygon that encloses these points - convert the points to an equal-area projection and then work out the area.

I have all the code written apart from how to calculate the vertices of a polygon that enclose the points on the graph. What is the best way to do this?

enter image description here

Samuel
  • 157
  • 6
  • 22
  • 1
    There is no python in this question – Peter Wood Aug 28 '15 at 08:58
  • One way to find a convex-polygon that contains these points is to compute the convex-hull. Look up the convex hull algorithm. – John Doe Aug 28 '15 at 09:00
  • 1
    You could look into the convex hull algorithms. They can be used for determining the smallest polygon that encloses all of them. Look at this: http://geomalgorithms.com/a10-_hull-1.html – Slimu Aug 28 '15 at 09:01
  • 1
    If the image in the question is correct, there are multiple solutions. How do you know which you want? – Holloway Aug 28 '15 at 09:04
  • 1
    Why are the green spheres not connected? – Peter Wood Aug 28 '15 at 09:21
  • The dashed polygonal boundary represents a concave hull which is not the same as a convex hull. I would begin your search for that term, whether you wish to generate the container for the centroid of the circles or their actual bounds. Convex hull searches will be fruitless unless the desired outcome is modified. –  Aug 28 '15 at 10:01

2 Answers2

3

The polygon you chose is not convex, so the popular convex hull algorithm wouldn't work for you.

https://pypi.org/project/alphashape/ seems what you want

Chen Xing
  • 1,665
  • 2
  • 13
  • 13
-2

I think what you're looking for is finding a convex hull for a given set of points. That doc desrcibes it pretty well:

http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.ConvexHull.html

Michał Szydłowski
  • 3,261
  • 5
  • 33
  • 55
  • 1
    The reference is for a convex hull, unfortunately the polygonal area delineated is for a concave hull, which is different and not as easy to calculate. –  Aug 28 '15 at 09:59
  • 1
    This question and the algorithms mentioned seem relevant: http://stackoverflow.com/questions/41268547/estimating-an-area-of-an-image-generated-by-a-set-of-points-alpha-shapes – user1834164 Apr 06 '17 at 09:03