algorithm - 查找向量之间角度度量的廉价算法

Question

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

幸运的是，我不需要角度本身，而只需要一些与所述角度成比例的值。

所以我正在寻找一些计算成本低的算法来计算与两个向量之间的角度相关的数量。到目前为止，我还没有找到符合要求的东西，我自己也无法想出一些东西。

score 19 · Accepted Answer

如果您不需要实际的欧几里得角，但可以用作角度比较的基础，那么更改为出租车几何形状可能是一种选择，因为您可以放弃三角学并且在保持准确性（或至少精度损失很小，见下文）。

在主要的现代浏览器引擎中，加速因子在 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。实际上，这不是很重要，例如。弧度 2.3000000000000001 和 2.3000000000000002 都在菱形角 1.4718731421442295 中，但是如果我们通过降低一个零来降低精度，弧度 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）空间中的距离比较快。

score 13 · Accepted Answer

你试过CORDIC算法吗？它是解决极坐标 ↔ 矩形问题的通用框架，仅使用加/减/位移 + 表，本质上是按 tan ^-1 (2 ^-n ) 形式的角度进行旋转。您可以通过更改迭代次数来权衡准确性和执行时间。

在您的情况下，将一个向量作为固定参考，并将另一个向量复制到一个临时向量，您使用心角向第一个向量（大致平分）旋转该临时向量，直到达到所需的角度精度。

（编辑：在每一步使用点积的符号来确定是向前还是向后旋转。虽然如果乘法足够便宜以允许使用点积，那么不要理会 CORDIC，也许使用一张 sin/cos 对表角度 π/2 ⁿ的旋转矩阵来解决二等分问题。）

（编辑：我喜欢 Eric Bainville 在评论中的建议：将两个向量都旋转为零并跟踪角度差。）

score 12 · Accepted Answer

早在只有几 K RAM 和数学能力有限的机器的时代，我就使用了查找表和线性插值。基本思想很简单：根据需要创建一个具有尽可能多的分辨率的数组（更多的元素可以减少插值产生的误差）。然后在查找值之间进行插值。

这是处理中的示例（原始死链接）。

您也可以使用其他三角函数来执行此操作。在 6502 处理器上，这允许以一个数量级的速度增加来计算全 3D 线框图形。

score 4 · Accepted Answer

在这里，我仍然没有发表评论的特权（尽管我在 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 的输出不同。如果你想做的只是钻石（阿尔法）>钻石（贝塔），那么我想钻石没问题。

score 2 · Accepted Answer

叉积与两个向量之间的角度成正比，当向量归一化并且角度很小时，叉积非常接近以弧度表示的实际角度，因为角度近似值很小。

具体来说：

I1Q2-I2Q1 与 I1Q1 和 I2Q2 之间的角度成正比。

score 1 · Accepted Answer

如果使用极坐标而不是笛卡尔坐标（或“以及”使用笛卡尔坐标）定义/存储向量，则该解决方案将是微不足道的。

score 1 · Accepted Answer

两个向量 (x1, y1) 和 (x2, y2) 的点积是

x1 * x2 + y1 * y2

并且等价于两个向量的长度乘以它们之间夹角的余弦的乘积。

因此，如果您首先对两个向量进行归一化（将坐标除以长度）

Where length of V1 L1 = sqrt(x1^2 + y1^2),  
  and length of V2 L2 = sqrt(x2^2 + y2^2),

然后归一化向量是

(x1/L1, y1/L1),  and (x2/L2, y2/L2),

并且归一化向量的点积（与向量之间角度的余弦相同）将是

 (x1*x2 + y1*y2)
 -----------------
     (L1*L2)

当然，这在计算上可能与计算余弦一样困难

score 1 · Accepted Answer

如果您需要计算平方根，请考虑使用invsqrt hack。

acos((x1*x2 + y1*y2) * invsqrt((x1*x1+y1*y1)*(x2*x2+y2*y2)));

score 0 · Accepted Answer

0

点积可能适用于您的情况。它与角度不成正比，而是“相关”。

于 2009-09-15T14:16:31.377 回答

algorithm - 查找向量之间角度度量的廉价算法

9 回答 9

Related

Reference