在 scipy.spatial.Delaunay 中 find_simplex() 方法返回什么？

Question

我需要找出我的一些点是在凸包内部还是外部，我正在使用这个答案：（在此处输入链接描述）。

但是当我测试它时，返回的数组有点混乱。例如，如果我创建两个相同的数组，使用一个数组创建一个船体，然后测试第二个数组的点是否在该船体中，我会得到以下结果：

from scipy.spatial import Delaunay
pts_outer = np.array([[0, 0], [0, 5], [5, 0], [5, 5]])
pts_inner = pts_outer
hull = Delaunay(pts_outer)
hull.find_simplex(pts_inner)

Out[29]: array([0, 0, 1, 1], dtype=int32)

该方法的文档只说它返回：“包含每个点的单纯形的索引。三角剖分之外的点得到值-1”。

我理解

1

是点在船体内部，

-1

是点在船体外部，但是0是什么？该点是否位于船体边界上？但那为什么只得两分呢？应该是全部。

如果我稍微修改一下测试数组：

pts_inner = np.array([[0, 0], [0, 5], [5, -1], [5, 5]])
hull.find_simplex(pts_inner)

Out[31]: array([ 0,  0, -1,  0], dtype=int32)

前两个点的指数相同，第三个点的指数为-1，正如计划的那样，但第四个点由于某种原因变成了 0，尽管船体和点完全相同。

有谁知道如何解释这些结果？

Answer 1

tl;dr：它返回包含该点的a三角形的索引。如果有多个三角形包含它，它并不总是选择相同的索引。

我认为你误解了“它返回：包含每个点的单纯形的索引。三角剖分之外的点得到值-1。”

我的解释是

Delaunay(pts_outer)

用索引分别为0和1的两个三角形对你的矩形进行三角剖分。然后

hull.find_simplex(pts_inner)

重新调整

[0, 0, 1, 1]

意味着前两个点位于三角形 0 中，后两个点位于三角形 1 中。

最后有点奇怪的是，

find_simplex

现在告诉你你的点

[5, 5]

在三角形1中。但这并不是不正确，因为点

[5, 5]

在两个三角形中。

Answer 2

您不应该将 delauny 单纯形的顶点放入 find_simplex 中。

当你这样做时：hull = Delaunay(pts_outer)

Scipy 制作一组单纯形（高维三角形），其中 (pts_outer) 中的每个点都是一些单纯形上的顶点。单纯形集对于数据集是唯一的（Delaunay 单纯形集）。

然后 hull.find_simplex() 告诉你这些点位于哪个单纯形中，如果一个点不在单纯形中，则返回 -1，因此它不在凸包中。

0 只是表示它位于 Delaunay(pts_outer) 返回的第 0 个单纯形中。

当您放入用于制作单纯形的相同点（即所有单纯形顶点）时，它在任何单纯形中都不清楚，因为它正好位于许多单纯形的边界上。所以我不知道它如何决定返回哪个单纯形，也许它会归结为一些浮点精度误差。这就是为什么您在相同的输入下改变了它所在的单纯形的部分原因。

对我来说，我感兴趣的是该点位于哪个单纯形中，这样我就可以获得重心坐标并进行插值。因为我已经知道每个顶点的因变量，所以找到它所在的“哪个顶点”是没有意义的。