为什么在计算凸包时，Qhull会出现错误？

Question

我正在尝试计算10维空间中9个点的凸包。通过scipy接口，我调用scipy.spatial.ConvexHull(points)，得到QH6214 qhull input error: not enough points(9) to construct initial simplex (need 12)的错误提示。

我认为无论是哪个维度，凸包的定义都是明确的。这里发生了什么？是否有其他函数可以解决这个问题？

- Mark

---

在n维空间中，一个非退化的凸包由至少n+1个点定义，例如1D空间中的线段，2D空间中的三角形或3D空间中的四面体。您在10维空间中的9个点定义了一个8维子空间。如果您将这些点引用到该子空间中，则计算这个新的8维子空间中9个点的凸包时不应该有问题。然后，您可以将结果凸包转换回10维空间。 - Jaime

或者，如果您只想知道退化凸包的顶点：如果点数少于“ndim + 1”，则所有点都在凸包中。 - pv.

@pv。假设我正在R ^ 100中工作，并且我有3个共线点。在这种情况下，我的凸包应该只由两个极端点指定，而不是所有3个点。 - Mark

Answer 1

也许在计算凸包之前将点投影到超平面上会起作用。

例如，使用scikit-learn工具包中的主成分分析类sklearn.decomposition.PCA来降低维度。

vertices = np.random.randn(9, 10)
from sklearn.decomposition import PCA
model = PCA(n_components=8).fit(vertices)

现在你可以使用 model.transform 和 model.inverse_transform 在顶点和投影之间进行转换。

proj_vertices = model.transform(vertices)
hull_kinda = ConvexHull(proj_vertices)
hull_kinda.simplices

这将输出类似于这样的内容。

array([[6, 4, 3, 8, 0, 7, 5, 1],
       [2, 4, 3, 8, 0, 7, 5, 1],
       [2, 6, 3, 8, 0, 7, 5, 1],
       [2, 6, 4, 8, 0, 7, 5, 1],
       [2, 6, 4, 3, 0, 7, 5, 1],
       [2, 6, 4, 3, 8, 7, 5, 1],
       [2, 6, 4, 3, 8, 0, 5, 1],
       [2, 6, 4, 3, 8, 0, 7, 1],
       [2, 6, 4, 3, 8, 0, 7, 5]], dtype=int32)

现在使用 model.inverse_transform 将简单形式重新转化为您的10维数据。

- Francisco Javier Blanco-Silva