凸包与SciPy

Question

我正在尝试使用scipy（版本0.10.1）来快速制作一个可视化的凸包。

我可以通过以下代码得到凸包：

vecs = [[-0.094218, 51.478927], [-0.09348,  51.479364], [-0.094218, 51.478927],
        ...
        [-0.094218, 51.478927], [-0.094321, 51.479918], [-0.094218, 51.478927],
        [-0.094222, 51.478837], [-0.094241, 51.478388], [-0.094108, 51.478116],
        [-0.09445,  51.480279], [-0.094256, 51.478028], [-0.094326, 51.500511]]
hull = scipy.spatial.Delaunay(vecs).convex_hull

得到的数组看起来是这样的：

[[56,  9], [16,  1], [56,  1], [55,  9], [53, 55], [53, 16]]

这些数字是顶点的索引。我的问题是这些索引没有顺序。我需要它们按照顺时针或逆时针的顺序排列，这样才能更方便地在KML中进行可视化。

有没有简单的方法可以让scipy.spatial计算出正确的顺时针顺序呢？

Answer 1

我发现了一个不错的方法，不过需要用到scipy 0.11.0版本的一个功能（sparse.csgraph）。

下面是一个完整的例子，真正的排序操作在“sort hull ...”这个注释后面的两行代码中。

import numpy as np
import scipy as sp

# random point cloud and hull
X = np.random.randint(0,200,(30,2))
hull = sp.spatial.qhull.Delaunay(X).convex_hull

# sort hull indices using (sparse) adjacency matrix graph stuff
g = sp.sparse.csr_matrix((np.ones(hull.shape[0]),hull.T), shape=(hull.max()+1,)*2)
sorted_hull = sp.sparse.csgraph.depth_first_order(g,hull[0,0],directed=False)[0]

# display with matplotlib
from matplotlib import pyplot as plt
plt.plot(X[:,0],X[:,1],'.')
plt.plot(X[sorted_hull,0],X[sorted_hull,1])

Answer 2

在当前的开发文档（0.13.0.dev）中，关于scipy.spatial.ConvexHull，有一个叫做vertices的属性，它在二维空间中是按逆时针方向排列的。

Answer 3

这段代码看起来能解决问题，但其实可以更简单一些……

基本上，我首先收集了外壳的顶点编号。然后我计算出这些点的平均值，接着把数据重新调整到这个平均值为中心，并根据与平均值的角度进行排序。

ps = set()
for x, y in hull:
    ps.add(x)
    ps.add(y)
ps = numpy.array(list(ps))
center = vecs[ps].mean(axis=0)
A = vecs[ps] - center
h = vecs[ps[numpy.argsort(numpy.arctan2(A[:,1], A[:,0]))]]