How to draw the largest polygon from a set of points

Question

So, i have a set of points (x,y), and i want to be able to draw the largest polygon with these points as vertices. I can use patches.Polygon() in matplotlib, but this simply draws lines between the points in the order i give them. This doesn't automatically do what i want. As an example, if a want to draw a square, and sort the points by increasing x, and then by increasing y, i won't get a square, but two connecting triangles. (the line "crosses over")

So the problem now is to find a way to sort the list of points such that i "go around the outside" of the polygon when iterating over this list.

Or is there maybe some other functionality in Matplotlib which can do this for me?

Answer 1

As suggested all ready a simple solution is to calculate the angles from some inner point to all points and sort them.

So here is for you a numpy function to calculate ccworder:

In []: def ccworder(A):
   ..:     A= A- mean(A, 1)[:, None]
   ..:     return argsort(arctan2(A[1, :], A[0, :]))
   ..:

And simple demonstration:

In []: A
Out[]:
array([[0, 0, 1, 1],
       [0, 1, 1, 0]])
In []: ccworder(A)
Out[]: array([0, 3, 2, 1])

Update:
It may seem that this kind ordering could be somehow tedious to calculate, but numpycan provide nice abstraction to make them pretty straightforward.

Caveat: As Joe and others have pointed out, this ccworder will form proper order on convex hull only if all points are all ready on the convex hull. I.e. somehow the order is missing, as it seems to be the OP's case, it can be recovered. Of'course there are other situations were ccworder is use full.

Answer 2

I don't know Matplotlib, but what you need/want is to draw the convex hull of the point set. Think of the convex hull as an elastic rope that you place around the point set. The shape that the elastic rope takes on is the convex hull. There are different algorithms for calculating a convex hull, so check if Matplotlib supports any. If not, check these links for a starting point on how to implement one.

http://en.wikipedia.org/wiki/Convex_hull

http://en.wikipedia.org/wiki/Convex_hull_algorithms