python - 检查一个点是否在 ConvexHull 中？

Question

我无法理解如何计算 n 维点是否在 n 维 ConvexHull 内。

这里提出了一个非常相似的问题（相同）： 找到一个点是否位于点云的凸包中的有效方法是什么？

但是，答案让我感到困惑或似乎对我不起作用，我不知道为什么。

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

这个函数给了我很多错误或不需要的真实数据结果，我正在使用它。但是，在调试时，我编写了一个简单的脚本来测试一些明显的期望：

如果我从一组点构造一个 ConvexHull，当我检查那组点的“成员资格”时，它们都应该是“成员”。

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 个）上失败，实际数据的问题更大。我所说的失败是指我实际上遇到了一些情况，并非所有积分都被视为成员。

有什么我做错了吗？或者也许完全是误解？在这一点上我很困惑，所以很想解释发生了什么。

最后，我想要；给定一个在前一阶段计算的 ConvexHull；能够确定点是否位于船体内。

标签： pythonnumpyscipy

Answer 1

对于几乎平坦的单纯形（三角形），对象的find_simplex方法似乎是一个边缘情况问题。Delaunay

这是一个代码，用于查找和绘制只有 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]