[FIXED] How to draw the largest polygon from a set of points

Issue

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?

Solution

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.

Answered By - eat