python - nD线与Python中凸包的交点

Question

我使用 scipy.spatial.ConvexHull 创建了一个凸包。我需要计算凸包和射线之间的交点，从 0 开始并沿其他定义点的方向。已知凸包包含 0，因此应保证相交。问题的维度可能在 2 到 5 之间变化。我尝试了一些谷歌搜索但没有找到答案。我希望这是计算几何中已知解决方案的常见问题。谢谢。

Answer 1

根据 qhull.org ，凸包的一个面的点x验证V.x+b=0，其中V和b 由 hull.equations 给出。 (. 代表这里的点积。V 是一个长度为 1 的法向量。)

If V is a normal, b is an offset, and x is a point inside the convex hull, then Vx+b <0.

如果 U 是从 O 开始的射线向量，则射线方程为 x=αU, α>0。所以射线与小平面的交点是 x = αU = -b/(V.U) U。与船体的唯一交点对应于 α 正值的最小值:

下一个代码给它:

import numpy as np
from scipy.spatial import ConvexHull

def hit(U,hull):
    eq=hull.equations.T
    V,b=eq[:-1],eq[-1]
    alpha=-b/np.dot(V,U)
    return np.min(alpha[alpha>0])*U

这是一个纯粹的 numpy 解决方案，所以速度很快。 [-1,1]^3 立方体中 100 万个点的示例:

In [13]: points=2*np.random.rand(1e6,3)-1;hull=ConvexHull(points)

In [14]: %timeit x=hit(np.ones(3),hull) 
#array([ 0.98388702,  0.98388702,  0.98388702])
10000 loops, best of 3: 30 µs per loop