检查两个向量是否平行的最有效方法

Question

给定两个向量u=(ux,uy,uz)和v=(vx,vy,vz),检查它们是否平行或接近平行的计算成本最低的方法是什么（给定一些阈值来近似), 假设向量未归一化？

关于接近并行：例如，我们假设一个阈值达到第一个小数部分，例如，如果它们的叉积是0.01，我们可以安全地假设它们是平行线。我们可以类似地放宽我们可能想要使用的其他方法的条件。

如果首选坚持编程语言来回答，让我们假设我们想用 c++ 来做这个。

计算它们之间的角度是昂贵的，因为它需要使用反三角函数。
计算它们的叉积可能是一种方法，但不确定它是否是最有效的方法。
对它们进行归一化并验证它们的标量积是否为一。

Answer 1

简答： 理论上来说，完全没有关系。实用：测一下

长答案：

同意反三角函数是不可能的，让我们比较一下计算最后两个选项的最有效方法。

计算他们的叉积

由于您允许向量几乎平行，因此您需要计算

crossx := uy * vz + uz * vy;
crossy := ...;
crossz := ...;
crossNorm = crossx * crossx + crossy * crossy + crossz * crossz;

其中涉及9次乘法和5次加法。如果向量（几乎）平行，则 crossNorm 应该（几乎）为零。

然而，正如正确指出的那样，检查 crossx、crossy 和 crossz 几乎为零就足够了，将其减少到 6 次乘法和3 次加法，最多增加两次比较。哪个更有效，取决于您的语言细节和“几乎”相等的定义——例如如果几乎等于意味着 fabs(...) < 1E-6 它可能只值得做一次。

计算标量积

标量积是

scalar = ux * vx + uy * vy + uz * vz;

如果向量（几乎）平行，则

scalar * scalar

应该（几乎）等于

(ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz).

这归结为 10 次乘法和 6 次加法。

对它们进行归一化并验证它们的标量积是否为一。

这只是上面的计算，但有两个额外的 double 划分。这不会增加任何值，实际上它可能只会引入舍入问题。

结论

两个选项的双重操作次数几乎相同。如果你真的想知道，你可以比较程序集 https://godbolt.org/z/nJ9CXl 但对于所有实际目的来说，差异将是最小的。事实上，如果你只计算“昂贵”的指令（mulsd、addsd、subsd）和比较（ucomisd），这两个选项都有五个。但是，再次重申，如果您必须准确，请测量它！

Answer 2

我认为这是错误的

标量=l1*l2*cos(r)=ux * vx + uy * vy + uz * vz 标量^2=(l1*l2*cos(r))^2=(ux * vx + uy * vy + uz * vz)^2

(l1*l2)^2= (ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz) 所以 cos(x)^2 =标量^2/(ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz)= (ux * vx + uy * vy + uz * vz)^2 /(ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz)

当 cos 为 1 或 -1 时，

x 接近 0 或 180，因此 cos(x)^2 -> 1

当这个

福米拉接近 1

(ux * vx + uy * vy + uz * vz)^2 /(ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz) 这意味着向量是平行的

检查两个向量是否平行的最有效方法

Most efficient way to check if two vectors are parallel

c++

geometry

vector

computation-theory

计算他们的叉积

计算标量积

对它们进行归一化并验证它们的标量积是否为一。

结论