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

Question

给定两个向量,u=(ux,uy,uz)以及v=(vx,vy,vz),计算最便宜的检查它们是平行还是几乎平行的方法(给定一些近似阈值),假设向量没有标准化？

关于几乎平行:例如,我们假设一个阈值直到第一个小数部分,例如,如果它们的叉积是0.01我们可以安全地假设它们是平行的.我们可以类似地放宽我们可能想要使用的其他方法的条件.

如果首选遵循编程语言来回答,让我们假设我们想在c ++中这样做.

• 计算它们之间的角度是昂贵的,因为它需要使用反三角函数.
• 计算他们的交叉产品可能是一种方式,但不确定它是否是最有效的方式.
• 将它们标准化并验证它们的标量积是否为1.

Answer 1

简短回答: 从理论上讲,它根本不重要.实际上:衡量它

答案很长:

同意逆三角函数是不可能的,让我们比较计算最后两个选项的最有效方法.

计算他们的交叉产品

由于允许矢量几乎平行,因此需要计算

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

其中涉及9次乘法和5次加法.如果矢量(几乎)平行,那么crossNorm 应该(几乎)为零.

然而,如通过正确指出的Baum MIT眼球,就足够了检查crossx,crossy并且crossz是几乎为零,这减少至6次乘法和加法3,在2周以上的比较为代价.哪个更有效,取决于您的语言的细节和"几乎"相等的定义 - 例如,如果几乎等于意味着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次加法.

将它们标准化并验证它们的标量积是否为1.

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

结论

两个选项的双重操作数几乎相同.如果您真的想知道,可以比较程序集https://godbolt.org/z/nJ9CXl,但差异对于所有实际目的来说都是最小的.事实上,如果只算"贵"的指令(mulsd,addsd,subsd)和比较(ucomisd)两种方案各有五他们.但是,如果你必须确切知道,请测量它!