寻找两点间角度的最快方法

Question

寻找两点间角度的最快方法

javascriptmath

11

为了提高计算角度正弦/余弦的速度，我建立了一个参考表代替了实时计算。同样地，我还有一个找到两点间角度的想法。

我创建了一个 3600 个归一化向量的表格（3600 / 10 = 十分之一度的精度）。每当我需要知道两点之间的角度时，我会搜索表格以找到最佳匹配。然而，我担心这可能比使用 math.atan2() 更慢。

这是我使用的代码：

创建向量表：

// vector to angle table
var vectorToAngleTable = new Array();
for (i = 0; i < 3600; i += 1) {
    vectorToAngleTable[i] = new Vector2();
    vectorToAngleTable[i] = RotatePoint(forwardVector, i / 10);
}

从两个点中找到角度：

function NormalizeVector(vector) {
    var toReturn = vector;
    var dist = Math.sqrt(vector.x * vector.x + vector.y * vector.y);
    toReturn.x /= dist.x;
    toReturn.y /= dist.y;
    return toReturn;
}

function PointDirection(position, target) {
    var vector = target;
    var toReturn = 0;
    var smallest = 1.0;
    vector.x -= position.x;
    vector.y -= position.y;
    vector = NormalizeVector(vector);
    for (i = 0; i < 3600; i += 1) {
        if (PointDistance(vectorToAngleTable[i], vector) < smallest) {
            smalllest = PointDistance(vectorToAngleTable[i], vector);
            toReturn = i;
        }
    }
    return toReturn;
}

function PointDistance(point1, point2) {
    return Math.sqrt(((point2.x - point1.x) * (point2.x - point1.x)) + ((point2.y - point1.y) * (point2.y - point1.y)));
}

你可以看到，我所关心的是代码要经过多少行，以及它查找的表中有多少条目。我想知道如何以最快的方式找到角度，不管使用什么方法。

- Timothy Eckstein

2

适用于：http://codereview.stackexchange.com/ - Diodeus - James MacFarlane

3

使用内置函数几乎肯定更快（这是 JavaScript 的特点）。特别是因为你目前的方法涉及到取平方根，这在效率上可能与使用反正切函数完全相同，因为平方根可能是通过牛顿逼近法的约 5 次迭代计算得出，而反正切可能是通过一个无穷级数的前几项来计算的。 - Wug

2

toReturn.x /= dist.x; toReturn.y /= dist.y; 看起来不对。dist 是一个标量，而不是另一个向量。 - japreiss

非常相似的算法可以用来找到向量之间角度的度量。 - hatchet - done with SOverflow

@shhac，我刚刚查了一下jsperf。这是一个很棒的概念，但我足够信任有经验的同行们，相信他们的话。如果你想要我的代码来自己玩耍，我可以把它放到网上并提供链接。 - Timothy Eckstein

显示剩余5条评论

2个回答

1

这肯定比调用atan2要小，因为它只是一个平方根，然后是在3600个可能性中进行线性搜索。相反，许多处理器直接实现了atan2 - 在英特尔领域中是FPATAN。

- Tommy

谢谢Tommy。我知道atan是一个非常常见的计算，我觉得奇怪的是没有任何三角函数直接通过处理器计算。如果这是真的，那么我认为正弦和余弦也是如此？也就是说，直接使用它们比制作参考表更好。 - Timothy Eckstein

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul S. · Accepted Answer

由于 angle(v1, v2) = acos((v1x*v2x+v1y*v2y)/(sqrt(v1x^2+v1y^2)*sqrt(v2x^2+v2y^2)))，且我们知道 v2 = [1, 0]。

var v = {x: 0, y: 1},
    angleRad = Math.acos( v.x / Math.sqrt(v.x*v.x + v.y*v.y) ),
    angleDeg = angleRad * 180 / Math.PI;

其中v是向量[point2.x - point1.x , point2.y - point1.y]

编辑 - 我刚刚意识到您可能是要将每个点视为向量，那么它将是

var v1 = {x: 0, y: 1}, v2 = {x: 1, y: 0},
    angleRad = Math.acos( (v1.x * v2.x + v1.y * v2.y) / ( Math.sqrt(v1.x*v1.x + v1.y*v1.y) * Math.sqrt(v2.x*v2.x + v2.y*v2.y) ) ),
    angleDeg = angleRad * 180 / Math.PI;

v1是向量[point1.x，point1.y]，v2是[point2.x，point2.y]

编辑2
如果您多次使用向量的长度，请保存它，例如v.length = ...，这样您就可以在不重新计算的情况下获得它。如果您知道每个向量都需要多次计算其角度，请使用我写的第一种方法进行缓存，即v.angle = ...。然后，您可以执行v2.angle - v1.angle等操作来查找两者之间的角度等。
即拥有

function Vector(x, y){
    this.x = x;
    this.y = y;
    this.length = Math.sqrt(x*x + y*y);
    this.angle = Math.acos( x / this.length );
}

jsperf 给出了一个包含 3601 个项目的数组进行预计算和查找，与直接使用 acos 的性能对比。