How to draw the largest polygon from a set of points

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?

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.

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

If you already know the hull points, then drawing the polygon by connecting those points is actually quite easy to do in Matplotlib because polygons are implemented in Matplotlib as paths. I would begin with the matplotlib.path class.

If you do not know the hull points then I agree with Elmar--convex hull is the algorithm you want. I have coded this algorithm in NumPy and plotted it in Matplotlib. My code was borrowed from an excellent recipe in the SciPy Cookbook, here. This recipe includes a NumPy implementation plus the complete code required to plot in Matplotlib the convex hull around a given set of points.

In addition, Matplotlib includes a package called delauney, which as you might have guessed is for tesselating a surface using delaunay triangulation. And as you might know, this is related to convex hull through voronoi tesselation--i.e., the boundaries of each voronoi cell are created from a convex hull calculation.

From your comments to other answers, you seem to already get the set of points defining the convex hull, but they're not ordered. The easiest way to order them would be to take a point inside the convex hull as the origin of a new coordinate frame. You then transform the (most probably) Cartesian coordinates of your points into polar coordinates, with respect to this new frame. If you order your points with respect to their polar angle coordinate, you can draw your convex hull. This is only valid if the set of your points defined a convex (non-concave) hull.

Then, how about do the sorting yourself?

Say, the convex hull point set is stored as a list points in python, and C is the some sort of inner point in your convex hull point set, you can just prepare a comparer like the following pseudo-code:

def cmpAngle(p1, p2):
    vector1 = p1 - C
    vector2 = p2 - C
    return dotProduct(vector1, vector2)
points.sort(cmp=cmpAngle)

The idea is to make use of dot product to figure out the ordering by their relative rotation.

Here you have a python implementation of convex hull (this is what you are looking for):

http://www.scipy.org/Cookbook/Finding_Convex_Hull

I've used scipy.spatial for this kind of problem. It has specific functions for plotting convex-hulls. See here. Maybe that's more firepower than you wanted.

Using shapely I found this to work quite nicely:

 lats = [<list of lats>]
 longs = [<list of longs>]
 # Returns the coordinates for the polygon (i.e. the convex hull) containing all coordinates in lats-longs"
 return MultiPoint(list(zip(longs, lats))).convex_hull.exterior.coords

3rd party library then takes care of the convex hull math for you.