查找点是否位于点云的凸包中的有效方法是什么？

Question

我在numpy中有一个点云坐标。对于大量点，我想找出这些点是否位于点云的凸包中。我尝试了pyhull，但是我不知道如何检查点是否在ConvexHull：hull = ConvexHull(np.array([(1, 2), (3, 4), (3, 6)]))for s in hull.simplices:    s.in_simplex(np.array([2, 3]))引发LinAlgError：数组必须为正方形。

Answer 1

我不确定如何使用您的程序库来实现这一目标。但是有一种简单的算法可以用语言来实现：

1. 创建一个绝对不在您的船体之外的点。叫Y

2. 产生将您的问题点（X）连接到新点Y的线段。

3. 环绕凸包的所有边缘线段。检查每个线段是否与XY相交。

4. 如果您计算的相交数为偶数（包括0），则X在船体之外。否则，X在船体内部。

5. 如果发生这种情况，则XY穿过您在船体上的一个顶点，或直接与您船体的一个边缘重叠，将Y稍微移动一点。

6. 以上也适用于凹面船体。您可以在下图中看到（绿色点是您要确定的X点。黄色标记相交点。