获取创建凸包的点的索引

Question

我正在尝试使用scipy.spatial（从scipy.spatial导入ConvexHull）来绘制一系列点的凸包。

import pylab as pl
from scipy.spatial import ConvexHull

pl.figure()  
pl.hold(True)  

points = np.concatenate((x, y), axis=1)

hull = ConvexHull(points)

pl.plot(points[:,0], points[:,1], 'ro')

for simplex in hull.simplices:
    pl.plot(points[simplex,0], points[simplex,1], 'dk--')    

问题是我不正确地理解了什么是hull.simplices，我想找到在凸包面上的点的索引，以便我可以使用这些索引从x和y中获取该点。

- Am1rr3zA

Answer 1

在二维情况下，ConvexHull对象的simplices属性包含构成凸包线段的点对索引。要仅获取这些索引，一种方法是获取展开的simplices数组的唯一元素。但请注意，这些点不会按照凸包在集合周围的顺序排列。（在scipy 0.13.0及更高版本中，可以使用vertices属性获取索引；请参见下文。）

例如，

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt


# Generate some random points for the demo.
np.random.seed(4321)
pts = 0.1 + 0.8*np.random.rand(15, 2)

ch = ConvexHull(pts)

# hull_indices = ch.vertices   # This will work in the scipy 0.13
hull_indices = np.unique(ch.simplices.flat)
hull_pts = pts[hull_indices, :]

plt.plot(pts[:, 0], pts[:, 1], 'ko', markersize=10)
plt.plot(hull_pts[:, 0], hull_pts[:, 1], 'ro', alpha=.25, markersize=20)
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.show()

这将生成：

vertices属性是在scipy 0.13.0中添加的：

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt


# Generate some random points for the demo.
np.random.seed(4321)
pts = 0.1 + 0.8*np.random.rand(15, 2)

ch = ConvexHull(pts)

# Get the indices of the hull points.
hull_indices = ch.vertices

# These are the actual points.
hull_pts = pts[hull_indices, :]

plt.plot(pts[:, 0], pts[:, 1], 'ko', markersize=10)
plt.fill(hull_pts[:,0], hull_pts[:,1], fill=False, edgecolor='b')
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.show()

- Warren Weckesser

---

我之前见过vertices，但我的问题是当我使用Vertices时，出现了这个错误：“AttributeError：'ConvexHull'对象没有属性'vertices'”。 - Am1rr3zA

啊，抱歉。我使用的是来自GitHub的最新版本scipy。vertices属性是几个月前才添加的（https://github.com/scipy/scipy/commit/3ff9d5fb2d2b9de660ee39a62a19ff186fc1618a）。 - Warren Weckesser

谢谢您提供的解决方案，但是我有一个很大的问题。如果您想根据索引绘制凸包（pl.plot(points[hull_indices,0], points[hull_indices,1], 'b--'）），那么绘制出来的形状是不正确的。我认为这是因为您的解决方案没有保存索引的顺序。 - Am1rr3zA

这就是我说“点不会按照凸包围绕集合的顺序排列”的意思（这也是我使用特殊标记而不是绘制线段的原因）。ConvexHull的文档字符串显示了绘制形状的示例：http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html#scipy.spatial.ConvexHull - Warren Weckesser