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

Question

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

所以现在的问题是找到一种方法来对点列表进行排序,这样当迭代这个列表时我就会"绕过多边形".

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

Answer 1

正如建议的那样，一个简单的解决方案是计算从某个内部点到所有点的角度并对它们进行排序。

所以这里有一个numpy函数供您计算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可以提供很好的抽象，使它们变得非常简单。

警告：正如 Joe 和其他人指出的那样，ccworder只有当凸包上的所有点都准备好​​时，这才会在凸包上形成正确的顺序。即不知何故订单丢失了，因为它似乎是OP的情况，它可以被恢复。当然还有其他情况就是ccworder用满了。