c++ - 如何在没有数学函数(arctan)的情况下计算点和 org(0,0) 之间的快速角度(最接近八个提供值之一)？

Question

如何在没有数学函数(arctan)的情况下快速计算点和 org(0,0) 之间的角度(最接近八个提供值之一)？我将 xy 坐标系分成 8 个部分(0、45、90、135、180、225、270、315)，我需要找到点和 org 之间的角度(不准确只是上面八个最接近的值)没有重数学函数。我可以找到类似的

std::pair<float,float> point;
float angle =arctan(point.second/point.first);
int index =static_cast<int>( (angle+22.5)/45);

然后按索引从数组中读取。(我添加了 22.5 度，因为 [-22.5, 22.5)=>0, [22.5,67.5)=>45,[67.5,112.5)=>90... )有没有更快的方法，任何想法(执行时间非常重要)？

Answer 1

给定一分 (a,b)与 a<b , a>=0和 b>=0 , 它更接近 45 度还是 0 度？

嗯，tan(theta) = opposite/adjacent , tan在0°到45°范围内单调递增。

tan(22.5 degrees) =~ 207107/500000 .所以如果a/b > 207107/500000 ，最近的角度是45度。如果a/b < 207107/500000 , 最近的角度是 0度。我们甚至可以通过说 500000*a < 207107*b 而不用 float 学来做到这一点。 .

对于任意点 (a,b) ，我们可以通过a和b上的标志找出它在哪个象限。我们可以将问题旋转(通过否定)到正-正象限，然后在生成的角度上反转该旋转(这是一个非常简单的 map )。

对于任意(a,b)在正-正象限中，如果a>b把a和b倒过来，同上解，“接近0度”对应“接近90度”。

上面的一些分支过于分支，但您应该能够将这些分支变成整数操作并以数组访问结束。

现在，请注意，在某些系统上，三角函数内在函数可以非常快，比一堆无分支整数操作和数组查找快得多。你的第一步应该是看看你是否可以更换你的 arctan更快arctan .

bool neg_a = a<0;
bool neg_b = b<0;
a *= (1-2*neg_a);
b *= (1-2*neg_b);
bool near_0 = 500000*a<207107*b; // a/b < 207107/500000
bool near_90 = 207107*a>500000*b; // a/b > 500000/207107
bool near_45 = !near_0 & !near_90;
// 3 CW 2     1
//   -+ | ++
//  2-4 | 0-2 CCW
//4 ----+---- 0
//CCW-- | +- CW
//  4-6 | 6-8
// 5    6     7

// 0 1 or 2
int index = near_45 + 2*near_90;
// negating a or b reverses angle
index *= (1-2*neg_a);
index *= (1-2*neg_b);
// base is 4 if a is negative:
index += 4*(neg_a);
// base is 8 if b is negative, and a is not negative:
index += 8*(neg_b&!neg_a);
index &= 7;

return index;

这很荒谬，但是没有分支。也没有调试。