2

如何在没有数学函数（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...）有更快的方法，任何想法（执行时间非常重要）？

4

4 回答 4

9

给定一个(a,b)带有和的点a<b，它是更接近 45 度还是 0 度？a>=0b>=0

嗯，tan(theta) = opposite/adjacent，并且在 0 度到 45 度的范围内，tan 是单调递增的。

tan(22.5 degrees) =~ 207107/500000. 所以如果a/b > 207107/500000，最近的角度是 45 度。如果a/b < 207107/500000，最接近的角度是0度。我们甚至可以在没有浮点数学的情况下通过说 来做到这一点500000*a < 207107*b。

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

(a,b)对于正-正象限中的任意一个，如果a>b只是将a和b颠倒，如上求解，“接近0度”对应“接近90度”。

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

现在，请注意，在某些系统上，trig 函数内在函数可以非常快，比一堆无分支整数操作和数组查找快得多。你的第一步应该是看看你是否可以用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;

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

于 2013-03-12T15:07:44.737 回答
1

您可以通过将其射线的梯度与 22.5、67.5 度等处的八分圆边界的梯度进行比较来计算该点所在的八分圆。所以：

static const float borders[] = { tan(-3 * PI / 8), tan(-PI / 8), tan(PI / 8), tan(3 * PI / 8) };
static const int angles[] = { 270, 315, 0, 45, 90, 135, 180, 225 };
float gradient = y / x;
int i = std::distance(borders, std::lower_bound(std::begin(borders), std::end(borders), gradient)) + (x < 0 ? 4 : 0);
int angle = angles[i];
于 2013-03-12T15:13:40.687 回答
1

This solution is based on maximizing cos(theta-theta_i) where theta_i is 0,45,90,...,315 degrees. I used the angle-difference identity cos(a-b)=cos(a)cos(b)-sin(a)sin(b) and worked with x=r*cos(a) and y=r*sin(a) to simplify the different expressions, so no actual trig functions have to be used:

int getIndex_simple(float x, float y){

  float rCosThetaMinusThetaI[8];
  rCosThetaMinusThetaI[0]=x;
  rCosThetaMinusThetaI[1]=(x+y)*M_SQRT1_2;
  rCosThetaMinusThetaI[2]=y;
  rCosThetaMinusThetaI[3]=(y-x)*M_SQRT1_2;
  rCosThetaMinusThetaI[4]=-x;
  rCosThetaMinusThetaI[5]=(-x-y)*M_SQRT1_2;
  rCosThetaMinusThetaI[6]=-y;
  rCosThetaMinusThetaI[7]=(x-y)*M_SQRT1_2;

  int best_i=0;
  float best_rCosThetaMinusThetaI=rCosThetaMinusThetaI[0];
  for(int i=1; i<8; i++)
    if( rCosThetaMinusThetaI[i]>best_rCosThetaMinusThetaI ){
      best_i=i;
      best_rCosThetaMinusThetaI=rCosThetaMinusThetaI[i];
    }

  return best_i;

}

There are a few simple things you can do to speed this up. For example rCosThetaMinusThetaI[i] == -rCosThetaMinusThetaI[i-4] for i>=4, so you only need four variables. Obviously you don't have to use an array, I just did this to make it easy to read. Also, since rCosThetaMinusThetaI[0]==x and rCosThetaMinusThetaI[2]==y, you only really need two variables. So we can rewrite the above as just a series of eight if statements:

int getIndex_optimized(float x, float y){

  float cosTheta1 = (x+y)*M_SQRT1_2;
  float cosTheta3 = (y-x)*M_SQRT1_2;

  int best_i=0;
  float best_cosTheta=x;
  if( best_cosTheta < cosTheta1 ){ best_i=1; best_cosTheta=cosTheta1; }
  if( best_cosTheta < y         ){ best_i=2; best_cosTheta=y; }
  if( best_cosTheta < cosTheta3 ){ best_i=3; best_cosTheta=cosTheta3; }
  if( best_cosTheta < -x        ){ best_i=4; best_cosTheta=-x; }
  if( best_cosTheta < -cosTheta1){ best_i=5; best_cosTheta=-cosTheta1; }
  if( best_cosTheta < -y        ){ best_i=6; best_cosTheta=-y; }
  if( best_cosTheta < -cosTheta3){ best_i=7; best_cosTheta=-cosTheta3; }

  return best_i;

}

These two functions are C99 code; you can compile them with -std=c99. You need to include math.h to get the constant M_SQRT1_2=0.7071...

于 2013-03-25T18:40:36.270 回答
0

在您使用的 8 条射线中，当点与 x 轴的距离比与 y 轴的距离更近（或相同距离）时，使用一组四条射线。其他四个以其他方式使用。
在这 4 条中，当 x 为正（或零）时，使用右边的两条光线。其他两个以其他方式使用。
在这 2 个中，当 y 为正时使用上光线。否则使用较低的。
因此，使用这些简单的测试在查找表中形成索引。

float ClosestAngle(std::pair<float,float> point) {
    float angle[8] = { 247.5 , 112.5f , 292.5 , 67.5f , 202.5 , 157.5 , 337.5 , 22.5f };

    int closerToXAxisThanYAxis = (abs(point.first) <= abs(point.second)) ? 4 : 0;
    int xIsPositive = (point.first >= 0) ? 2 : 0;
    int yIsPositive = (point.second >= 0) ? 1 : 0;

    return angle[closerToXAxisThanYAxis + xIsPositive + yIsPositive];
}
于 2013-03-12T16:24:31.927 回答