python - 坐标簇与沿单位向量 i 的点之间的最小距离

Question

我有一组 3D 坐标 Q，围绕原点 O、单位向量 i 和长度 d 聚集成一个粗糙的球体。设 p = c * i，其中 c 是正实数。令 M 表示 p 与 Q 中每个 q 之间的距离集合。我需要一种稳健的方法来计算 c 的最小值，但约束条件是 M 的最小值大于 d。有没有一种优雅的方法可以在 python 中使用 scipy/numpy 来做到这一点？我怀疑 scipy.spatial.KDTree 会有用，但目前还不清楚如何有效地找到约束最小值。

Answer 1

你可以这样解决问题:

对于 Q 中的点 q，定义:

C(q) = set of values of c >= 0 s.t. |q - c*i| >= d

然后定义

C = intersection { q in Q } C(q)

则所需的c值为:

c = inf C = minimum element of C

集合 C(q) 只是二次不等式的解，因此 有以下形式之一:

1) C(q) = [0, +infinity)
2) C(q) = [0, b] union [ e, +infinity )  (for some e > b)
3) C(q) = [e, +infinity )

您可以安全地丢弃第一种形式的集合。

如果所有剩余的 C(q) 集合都具有形式 #2，则 c = 0。

如果它们都具有形式 #3，则 c 是:

c = maximum { q in Q } e(q)

否则事情会变得更加复杂。

对于给定的 q，要计算 C(q)，请注意:

|q - c*i| >= d
  <=> (q - c*i)^2 >= d*d
  <=> (q - c*i).(q - c*i) >= d*d
  <=> q.q + c*c - 2*c*(q.i) >= d*d
  <=> c*c - c*2*(q.i) + q.q - d*d >= 0

如果该二次方程的判别式< 0，则 C(q) = [0, +无穷大)。

否则令 b 和 e 为根，b <= e，并检查这些情况:

e < 0    -->  C(q) = [0, +infinity)
b < 0    -->  C(q) = [e, +infinity)
b >= 0   -->  C(q) = [0, b]  union [e, +infinity)

演示更复杂情况的二维示例:

Q = { q1, q2, q3, q4 }
  = { (1,0), (0,1), (4,4), (0,10) }
i = (1/sqrt 5, 2/sqrt 5)
d = 2

C(q1) = [ 2.236, +infinity )
C(q2) = [ 2.843, +infinity )
C(q3) = [ 0, 4.472 ] union [ 6.261, +infinity )
C(q4) = [ 0, +infinity )

C(q1)、C(q2) 和 C(q3) 的交集的最小元素为 2.843。