检查一个点是否在凸包内？

Question

我不太理解如何计算一个n维点是否在n维凸包内。这里有一个非常相似的问题（相同），链接如下：What's an efficient way to find if a point lies in the convex hull of a point cloud?。然而，答案让我感到困惑，或者似乎对我无效，我不知道为什么。请注意保留HTML标签。

def in_hull(p, hull):
    """ Copied and from the Top Original answer """
    from scipy.spatial import Delaunay
    if not isinstance(hull,Delaunay):
        hull = Delaunay(hull)

    return hull.find_simplex(p)>=0

这个函数在我使用真实数据时给我带来了很多错误或不必要的结果。然而，当我调试时，我编写了一个简单的脚本来测试一些显而易见的期望：

如果我从一组点中构造一个凸包，当我检查该组点的“成员资格”时，它们应该全部是“成员”。

results_all = []
for _ in range(5000):
    cloud = np.random.rand(5000, 2)
    result = in_hull(cloud, cloud)
    results_all.append(np.all(result))

arr = np.array(results_all)
print(np.sum(np.logical_not(arr)))

虽然罕见，但在随机生成的数据上似乎会出现失败情况（5000个数据中有3个），而在真实数据上问题更大。所谓的失败是指，我确实遇到了一些情况，其中并非所有点都被视为成员。

我做错了什么吗？或者完全误解了吗？此时我相当困惑，希望能够解释一下发生了什么。

最终，我希望在给定先前某个阶段计算的凸包的情况下，能够确定点是否在凸包内。

- SirSteel

Answer 1

看起来是针对非常平坦的单形（三角形）的Delaunay对象的find_simplex方法的边缘情况问题。

以下是一段代码，用于查找和绘制仅具有3个点的错误案例：

import matplotlib.pylab as plt
from scipy.spatial import Delaunay
from scipy.spatial import delaunay_plot_2d

for _ in range(5000):
    cloud = np.random.rand(3, 2)

    tri = Delaunay(cloud)

    if np.any( tri.find_simplex(cloud)<0 ):
        print('break at', _)

        delaunay_plot_2d(tri);
        id_break = np.where(tri.find_simplex(cloud)<0)
        plt.plot( *cloud[id_break].ravel(), 'or' );
        break

这里提出的另一种方法似乎很有效：

hull = ConvexHull(cloud)

def point_in_hull(point, hull, tolerance=1e-12):
    return all(
        (np.dot(eq[:-1], point) + eq[-1] <= tolerance)
        for eq in hull.equations)

[ point_in_hull(point, hull) for point in cloud ]
# [True, True, True]

- xdze2

---

非常感谢！这解决了我的问题，而且是那些边界情况。 - undefined