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

因此，我有一组点（x，y），我希望能够用这些点绘制最大的多边形作为顶点。我可以在matplotlib中使用patches.Polygon（），但是这只是按照我给他们的顺序在点之间画线。这不会自动做我想要的。作为一个例子，如果想绘制一个正方形，并通过增加x来排序点，然后通过增加y，我不会得到一个正方形，而是两个连接的三角形。（线“交叉”）如何从一组点中绘制最大的多边形

所以现在的问题是要找到一种方法来排序点的列表，使得我遍历该列表时多边形的“外面”。

或者在Matplotlib中可能还有其他一些功能可以为我做到这一点？

来源

2011-02-18 Eskil

建议所有准备好一个简单的解决方案是计算从一些内点到所有点的角度并对它们进行排序。

所以这里是为你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可以提供很好的抽象，使他们相当简单。

警告：乔和其他人指出，这ccworder将形成上凸包只有当所有点都准备上凸包正确的顺序。即不知何故订单不见了，因为它似乎是OP的情况下，它可以恢复。 of'course有其他情况下ccworder是使用全。

来源

2011-02-18 14:00:29 eat

我不知道Matplotlib，但你需要/想要的是绘制凸包的点集。将凸包想象成一个弹性绳索，将其放置在点集上。弹性绳的形状是凸包。计算凸包有不同的算法，所以检查Matplotlib是否支持任何算法。如果没有，请检查这些链接以了解如何实施它的起点。

http://en.wikipedia.org/wiki/Convex_hull

http://en.wikipedia.org/wiki/Convex_hull_algorithms

来源

2011-02-18 11:01:36

谢谢。但据我了解，“找到凸包”通常意味着找到属于全套凸包的一部分点的子集。 – Eskil 2011-02-18 11:18:43

谢谢。但据我了解，“找到凸包”通常意味着找到属于全套凸包的一部分点的子集。另一方面，我在某种意义上已经具有凸包，我只需要对它们进行排序，这样当我按顺序在它们之间画线时，就可以绘制出凸包。 – Eskil 2011-02-18 11:24:39

这里有凸包的Python实现（这是你在找什么）：

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

来源

2011-02-18 11:17:55 karolx

问题是这个算法要求我有五个以上的点数。我需要一些适用于简单情况的东西。这也是一种矫枉过正，因为我已经有了这个凸包，我只是需要正确分类以便能够绘制它。 – Eskil 2011-02-18 11:37:23

如果你已经知道船体点，然后通过连接这些点来绘制多边形在Matplotlib中实际上很容易，因为多边形正在实施在Matplotlib中作为路径。我会从matplotlib.path class开始。

如果你不知道船体点，那么我同意埃尔玛 - 凸包就是你想要的算法。我在NumPy中编写了这个算法，并将其绘制在Matplotlib中。我的代码是从SciPy食谱的优秀配方中借用的，here。这个配方包含一个NumPy实现，以及在Matplotlib中绘制给定点集上的凸包所需的完整代码。

此外，Matplotlib包含了一个叫做delauney，正如你可能已经猜到是使用德劳内三角tesselating的表面。正如你可能知道的那样，这与凸包通过voronoi tesselation有关 - 也就是说，每个voronoi单元的边界都是由凸包计算创建的。

来源

2011-02-18 11:48:37 doug

但是因为我已经有了凸包设置点，所以它可能会过度杀伤。我只需要对它们进行排序，让它们按顺时针或逆时针顺序进入。并且链接中的算法不会少于6分。 – Eskil 2011-02-18 11:53:23

从你的评论到其他答案，你似乎已经得到了定义凸包的点集，但它们没有排序。订购它们的最简单方法是将凸包内的点作为新坐标框架的原点。然后，将这些新点的坐标转换为极坐标（最可能）。如果您就您的极坐标角度对点进行排序，则可以绘制凸包。这只有在你的点集合定义了一个凸形（非凹形）船体时才有效。

来源

2011-02-18 11:54:46 Chaos

那么，你自己排序怎么样？

说，凸包点集合存储为列表点在Python和ç是某种在你的凸包点集内点的，你可以准备像下面的伪一个比较器-code：

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

的想法是利用积由他们的相对旋转找出排序。

来源

2011-02-18 12:09:51 Drake

我对这类问题使用了scipy.spatial。它具有绘制凸壳的特定功能。请参阅here。也许这比你想要的火力更强。

来源

2013-10-23 02:15:32 benten

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

回答

相关问题