如何从一组点绘制最大的多边形

本文介绍了如何从一组点绘制最大的多边形的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

因此，我有一组点(x，y)，并且我希望能够绘制以这些点为顶点的最大多边形.我可以在matplotlib中使用patch.Polygon()，但这只是按照我给它们的顺序在两点之间画线.这不会自动执行我想要的操作.举个例子，如果a想画一个正方形，通过增加x然后增加y对点进行排序，我不会得到一个正方形，而是两个连接的三角形.(线越过")

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.

或者 Matplotlib 中是否有其他一些功能可以为我做到这一点?

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.

所以这里有一个 numpy 函数来计算 ccworder:

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, :])) ..:

简单演示:

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

更新:看起来这种排序可能有点繁琐，但是 numpy 可以提供很好的抽象方法，使它们变得非常简单.

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

注意事项:如Joe和其他人所指出的那样，只有在凸包上所有点都准备就绪时，此 ccworder 才会在凸包上形成适当的顺序.IE.不知何故，订单丢失了，因为它似乎是 OP 的情况，它可以恢复.当然，还有其他情况是 ccworder 已用完.

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.