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

Question

我有一组点（x,y），我想用这些点作为顶点画出最大的多边形。我可以在matplotlib中使用patches.Polygon()，但这只是按照我给的顺序在点之间画线。这并不能自动实现我想要的效果。举个例子，如果我想画一个正方形，并且按照x值从小到大排序，再按照y值从小到大排序，我得到的却不是一个正方形，而是两个相连的三角形。（线条“交叉”了）

所以现在的问题是，如何对这组点进行排序，以便在遍历这个列表时能够“绕着多边形的外边”走。

或者，matplotlib中有没有其他功能可以帮我实现这个呢？

Answer 1

那么，自己来排序怎么样呢？

假设你的凸包点集合在Python中存储为一个列表points，而C是你凸包点集合中的某个内部点，你可以准备一个比较器，像下面的伪代码这样：

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

这个想法是利用点积来判断这些点的相对旋转顺序。

Answer 2

从你对其他回答的评论来看，你似乎已经知道了定义凸包的一组点，但这些点的顺序还没整理好。整理这些点最简单的方法是选择一个在凸包内部的点，作为新的坐标系的原点。然后，你可以把这些点的（很可能是）笛卡尔坐标转换成极坐标，基于这个新的坐标系。如果你根据极角的大小来给这些点排序，就可以画出你的凸包了。不过，这种方法只适用于你的点集形成的是一个凸的（而不是凹的）外形。

Answer 3

正如之前提到的，一个简单的解决办法是从某个内部点出发，计算到所有点的角度，然后对这些角度进行排序。

这里有一个 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 才能形成正确的顺序。也就是说，如果顺序缺失，就像提问者的情况一样，是可以恢复的。当然，还有其他情况下 ccworder 也是很有用的。