9

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?

7 Answers 7

4

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.

1
  • 1
    For simple cases, this is definitely the way to go (+1). If the points he has always form a convex hull, this will always work. However, you might want to point out that it won't work for more complex polygons (i.e. anything where the "correct" ordering of the points isn't simply a steadily increasing angle about the center). Feb 18, 2011 at 14:07
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

2
  • Thanks. But as far as i understand it, "finding the convex hull" normally means finding the subset of points which are a part of the convex hull of the total set.
    – Eskil
    Feb 18, 2011 at 11:18
  • Thanks. But as far as i understand it, "finding the convex hull" normally means finding the subset of points which are a part of the convex hull of the total set. I on the other hand already have the convex hull in some sense, i just need to ORDER them such that i get a drawing of the convex hull when i draw lines between them in order.
    – Eskil
    Feb 18, 2011 at 11:24
2

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.

2
  • But since i already have the convex hull point set, it might be overkill. I just need to sort them so they come in a clockwise or counterclockwise order. And the algorithm in your link won't take less than 6 points.
    – Eskil
    Feb 18, 2011 at 11:53
  • 1
    Delauney is rather overkill for triangulating a convex polygon. Instead just use a triangle fan. However, if you want to triangulate including the interior points, use Delauney. Feb 18, 2011 at 12:10
2

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.

2

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.

1

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

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

1
  • Problem is that this algorithm requires that i have more than five points. I need something that works for the simple cases. It is also kind of overkill, since i already have the set which is the convex hull, i just need to sort it correctly to be able to draw it.
    – Eskil
    Feb 18, 2011 at 11:37
0

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.

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.