2

数学関数 (arctan) を使用せずに、ポイントと org(0,0) の間のクイック ウェイ アングル (提供された 8 つの値のうちの 1 つに最も近い) を計算するにはどうすればよいですか? xy 座標系を 8 つのセグメント (0、45、90、135、180、225、270、315) に分割しました。数学関数。私はのように見つけることができます

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)が与えられた場合、それは 45 度または 0 度に近いですか?a<ba>=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度に近い」に相当します。

上記のいくつかは過度に分岐していますが、これらの分岐を整数演算に変換し、配列アクセスで終了できるはずです。

ここで、一部のシステムでは、三角関数の組み込みが非常に高速であり、分岐のない整数演算と配列ルックアップの山よりもはるかに高速であることに注意してください。最初のステップは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

このソリューションは、cos(theta-theta_i) を最大化することに基づいています。ここで、theta_i は 0、45、90、...、315 度です。角度差単位 cos(ab)=cos(a)cos(b)-sin(a)sin(b) を使用し、x=r*cos(a) および y=r*sin(a) を使用してさまざまな式を単純化するため、実際の三角関数を使用する必要はありません。

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;

}

これを高速化するためにできる簡単なことがいくつかあります。たとえばrCosThetaMinusThetaI[i] == -rCosThetaMinusThetaI[i-4]、i>=4 の場合、必要な変数は 4 つだけです。明らかに、配列を使用する必要はありません。読みやすくするためにこれを行っただけです。また、rCosThetaMinusThetaI[0]==xとであるため、rCosThetaMinusThetaI[2]==y実際に必要な変数は 2 つだけです。したがって、上記を一連の 8 つのifステートメントとして書き直すことができます。

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;

}

これら 2 つの関数は C99 コードです。-std=c99 でコンパイルできます。定数 M_SQRT1_2=0.7071 を取得するには、math.h を含める必要があります...

于 2013-03-25T18:40:36.270 に答える
0

使用している8つの光線のうち、ポイントがy軸よりもx軸に近い（または同じ距離にある）場合は、4つの光線の1つのセットが使用されます。他の4つはそれ以外の場合に使用されます。
これらの4つのうち、xが正（またはゼロ）の場合、右の2つの光線が使用されます。他の2つはそれ以外の場合に使用されます。
これら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 に答える