Python中nD线与凸包的相交 [英] Intersection of nD line with convex hull in Python

问题描述

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

I have created a convex hull using scipy.spatial.ConvexHull. I need to compute the intersection point between the convex hull and a ray, starting at 0 and in the direction of some other defined point. The convex hull is known to contain 0 so the intersection should be guaranteed. The dimension of the problem can vary between 2 and 5. I have tried some google searching but haven't found an answer. I am hoping this is a common problem with known solutions in computational geometry. Thank you.

推荐答案

根据 qhull.org ，凸包的小平面上的点 x 验证 V.x + b = 0 ，其中 V 和 b 由 hull.equations 给出。 （。在这里代表点积。 V 是长度为1的法线向量。）

According to qhull.org, the points x of a facet of the convex hull verify V.x+b=0, where V and b are given by hull.equations. (. stands for the dot product here. V is a normal vector of length one.)

如果V是法线，b是一个偏移量，x是凸形
外壳内的一个点，则Vx + b <0。

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 。与船体的唯一交点对应于α的正值的最小值：

If U is a vector of the ray starting in O, the equation of the ray is x=αU, α>0. so the intersection of ray an facet is x = αU = -b/(V.U) U. The unique intersection point with the hull corresponds to the min of the positive values of α:

下一个代码给出它：

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 多维数据集中的一百万个示例：

It is a pure numpy solution so it is fast. An example for 1 million points in the [-1,1]^3 cube :

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

这篇关于Python中nD线与凸包的相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！