问题描述
我使用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.
推荐答案
根据,凸包的小平面上的点 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
如果 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线与凸包的相交的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!