问题 找到两点之间角度的最快方法


为了提高我找到角度的正弦/余弦的速度,我建立了一个参考表,而不是动态计算它们。我有同样的想法,从一个点到另一个点找到角度。

我创建了一个包含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)));
}

正如您所看到的,我关注的是它正在经历的所有代码行,以及它所查看的表中有多少条目。无论方法是什么,我都想知道找到角度的最快方法。


7723
2017-10-15 20:32


起源

属于: codereview.stackexchange.com - Diodeus - James MacFarlane
使用内置函数几乎肯定更快(这是javascript)。特别是因为你现在的方法涉及采用平方根,这在效率方面可能与使用反正切函数完全相同,因为sqrt可能用大约5次迭代的牛顿近似完成,而arctan可能是用无限系列的前几个术语。 - Wug
toReturn.x /= dist.x; toReturn.y /= dist.y; 看起来不对劲 dist 是标量,而不是另一个向量。 - japreiss
非常相似 stackoverflow.com/questions/1427422/... - hatchet
也类似于 stackoverflow.com/a/3441867/1615483 - Paul S.


答案:


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 直


11
2017-10-15 20:48



哇,我印象深刻。不同的是白天和黑夜。我不认为它会有如此戏剧性的差异。无论如何,谢谢你再次谢谢。 - Timothy Eckstein
@dergenialeein有人 修改它 使用引导我的多项式近似 这里,再次快两倍。请注意,这可能会有更大的错误。 - Paul S.
@shhac:那是我,我只是将'acos approximation'放入我们光荣的搜索引擎霸主。老实说,感到惊讶的是它要快得多。 - Phil H
嗯,一个可能的11度误差与6倍慢,这是更大的邪恶?我猜如果游戏代币经常计算他们的目标方向,它可以(大部分)补偿错误。谢谢shhac和Phil H,这是我正在寻找的那种东西。 - Timothy Eckstein


这绝对会比打电话要小 atan2,因为它是一个平方根,然后通过3600种可能性进行线性搜索。相反,许多处理器直接实现atan2 - 它是英特尔领域的FPATAN。


1
2017-10-15 20:42



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