寻找矢量之间角度测量的廉价算法

Question

使用余弦规则找到两个向量之间的角度并不难.但是,因为我正在为资源非常有限的平台编程,所以我想避免计算诸如sqrt和arccos.即使是简单的划分也应该尽可能地受到限制.

幸运的是,我不需要角度本身,但只需要一些与所述角度成比例的值.

所以我正在寻找一些计算上便宜的算法来计算与两个矢量之间的角度相关的量.到目前为止,我还没有找到符合条件的东西,也没有能够自己想出一些东西.

Answer 1

如果你不需要实际的欧几里德角,但你可以用作角度比较的基础,那么改为出租车几何可能是一个选择,因为你可以放弃三角学并且它在保持精度的同时是缓慢的(或者至少精确度略有下降,见下文).

在主要的现代浏览器引擎中,加速因子在1.44-15.2之间,精度几乎与atan2相同.计算钻石角度平均比atan2快5.01倍,并且在Firefox 18中使用内联代码,加速到达15.2倍.速度比较:http://jsperf.com/diamond-angle-vs-atan2/2.

代码很简单:

function DiamondAngle(y, x)
{
    if (y >= 0)
        return (x >= 0 ? y/(x+y) : 1-x/(-x+y)); 
    else
        return (x < 0 ? 2-y/(-x-y) : 3+x/(x-y)); 
}

上面的代码给出了0到4之间的角度,而atan2给出了-PI和PI之间的角度,如下表所示:

请注意,钻石角度始终为正,在0-4范围内,而atan2也给出负弧度.因此,钻石角度更加标准化.另一个注意事项是atan2给出了更精确的结果,因为范围长度是2*pi(即6.283185307179586),而在钻石角度它是4.实际上这不是很重要,例如.rad 2.3000000000000001和2.3000000000000002都是钻石角度1.4718731421442295,但是如果我们通过降低一个零来降低精度,则rad 2.300000000000001和2.300000000000002给出两个不同的钻石角度.钻石角度的这种"精确松动"非常小,只有在距离很大的情况下才会产生一些重要的影响.您可以在http://jsbin.com/bewodonase/1/edit?output(旧版本:http://jsbin.com/idoyon/1)中进行转换:

上面的代码足以进行快速角度比较,但在许多情况下需要将钻石角度转换为弧度和副角度.如果你,例如.有一些公差作为弧度角,然后你有一个100,000次循环,其中这个公差与其他角度进行比较,使用atan2进行比较是不明智的.相反,在循环之前,您将弧度公差更改为出租车(钻石角度)公差,并使用金刚石公差进行环路比较,这样您就不必在代码的速度关键部分使用慢三角函数(= in循环).

进行此转换的代码是:

function RadiansToDiamondAngle(rad)
{
  var P = {"x": Math.cos(rad), "y": Math.sin(rad) };
  return DiamondAngle(P.y, P.x);
}  

当你发现有cos和sin.如您所知,它们很慢,但您不必在循环中进行转换,但在循环之前并且加速很大.

如果由于某种原因,你必须将钻石角度转换为弧度,例如.在循环并进行角度比较后返回例如.最小比较角度或任何弧度,代码如下:

function DiamondAngleToRadians(dia)
{
  var P = DiamondAngleToPoint(dia);
  return Math.atan2(P.y,P.x);
}

function DiamondAngleToPoint(dia)
{
  return {"x": (dia < 2 ? 1-dia : dia-3), 
  "y": (dia < 3 ? ((dia > 1) ? 2-dia : dia) : dia-4)};
}

在这里你使用atan2,这很慢,但想法是在任何循环之外使用它.您不能通过简单地乘以某个因子将钻石角度转换为弧度,而是在出租车几何中找到该点,该点与正X轴之间的钻石角度是有问题的钻石角度,并使用atan2将此点转换为弧度.

这应该足以进行快速角度比较.

当然还有其他atan2加速技术(例如CORDIC和查找表),但是AFAIK它们都是松散的准确度,但仍然可能比atan2慢.

背景:我已经测试了几种技术:点积,内积,余弦定律,单位圆,查找表等,但在速度和精度都很重要的情况下,没有什么是足够的.最后,我在http://www.freesteel.co.uk/wpblog/2009/06/encoding-2d-angles-without-trigonometry/找到了一个具有所需功能和原理的页面.

我首先假设也可以使用出租车距离进行准确和快速的距离比较,因为在出​​租车中,欧几里得的距离越大.我意识到与欧氏距离相反,起点和终点之间的角度对出租车距离有影响.在欧几里得和出租车之间只能轻松快速地转换垂直和水平矢量的长度,但在其他情况下,你必须考虑角度,然后过程太慢(？).

因此,作为结论,我认为在速度关键应用中,角度和/或距离的几个比较的循环或递归,在出租车空间和欧氏距离(平方,不使用sqrt)空间中比较角度更快.

Answer 2

在几K的RAM和具有有限数学能力的机器的那天,我使用了查找表和线性插值.基本思路很简单:创建一个具有所需分辨率的数组(更多元素可减少插值产生的错误).然后在查找值之间进行插值.

这是处理中的一个例子(原始死链接).

您也可以使用其他触发功能执行此操作.在6502处理器上,这允许以一个数量级的速度增加来计算全3D线框图形.

Answer 3

你尝试过CORDIC算法吗？这是一个解决极性↔矩形问题的通用框架,只有加/减/ bitshift + table,基本上是通过形式为tan ^-1(2 ^-n)的角度进行旋转.您可以通过更改迭代次数来折衷准确性和执行时间.

在您的情况下,将一个矢量作为固定参考,并将另一个矢量复制到临时矢量,使用朝向第一个矢量(大致二等分)的cordic角度旋转,直到达到所需的角度精度.

(编辑:使用点积的符号来确定每一步是向前还是向后旋转.虽然如果乘法足够便宜以允许使用点积,那么不要打扰CORDIC,也许使用sin/cos对表角度π/ 2 ^n的旋转矩阵解决了二分问题.)

(编辑:我喜欢Eric Bainville在评论中的建议:将两个向量旋转到零并跟踪角度差异.)

Answer 4

在此，我仍然没有发表评论的特权（尽管我在 math.se 上有评论），所以这实际上是对 Timo 关于钻石角度的帖子的回复。

基于 L1 范数的菱形角的整个概念是最有趣的，如果它只是比较哪个向量相对于正 X 轴具有更大/更小，那就足够了。然而，OP确实提到了两个通用向量之间的角度，我猜想OP想要将它与一些公差进行比较，以找到平滑度/角状态或类似的东西，但不幸的是，似乎只有jsperf.com上提供的公式或者 freesteel.co.uk （上面的链接）似乎不可能使用菱形角来做到这一点。

观察我的公式 Asymptote 实现的以下输出：

Vectors : 50,20 and -40,40
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.21429
Convert that to degrees       : 105.255
Rotate same vectors by 30 deg.
Vectors : 33.3013,42.3205 and -54.641,14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.22904
Convert that to degrees       : 106.546
Rotate same vectors by 30 deg.
Vectors : 7.67949,53.3013 and -54.641,-14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.33726
Convert that to degrees       : 116.971

所以关键是你不能做 Diamond(alpha)-diamond(beta) 并将其与某个公差进行比较，这与你可以对 atan2 的输出所做的不同。如果您想做的只是钻石（alpha）>钻石（beta）那么我认为钻石就可以了。