Как рассчитать угол быстрого пути (ближайший к одному из восьми предложенных значений) между точкой и орг (0,0) без математических функций (арктан)?
Как рассчитать угол быстрого пути (ближайший к одному из восьми предложенных значений) между точкой и орг (0,0) без математических функций (арктан)?
Я разделил систему координат 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... )
Есть ли более быстрый способ, любая идея (время исполнения очень важно)?
Решение
Учитывая точку (a,b) с a<b, a>=0 а также b>=0это ближе к 45 градусов или 0 градусов?
Что ж, tan(theta) = opposite/adjacentи в диапазоне от 0 до 45 градусов загар монотонно увеличивается.
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;
что довольно смешно, но без веток. Также не отлажен.
Другие решения
Вы можете вычислить, в каком октанте находится точка, сравнивая градиент ее луча с градиентами границ октанта, при 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];
Это решение основано на максимизации cos (theta-theta_i), где theta_i равно 0,45,90, …, 315 градусов. Я использовал тождество разности углов cos (ab) = cos (a) cos (b) -in (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, поэтому вам нужно только четыре переменные. Очевидно, вам не нужно использовать массив, я просто сделал это, чтобы его было легко читать. Кроме того, так как rCosThetaMinusThetaI[0]==x а также rCosThetaMinusThetaI[2]==yВам нужны только две переменные. Таким образом, мы можем переписать вышесказанное как просто серию из восьми 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;
}
Эти две функции являются кодом C99; Вы можете скомпилировать их с -std = c99. Вам нужно включить math.h, чтобы получить константу M_SQRT1_2 = 0,7071 …
Из 8 лучей, которые вы используете, один набор из четырех используется, когда точка находится ближе (или на том же расстоянии) к оси x, чем к оси y. Остальные четыре используются иначе.
Из этих 4 правые два луча используются, когда х положительно (или ноль). Два других используются иначе.
Из этих 2 верхний луч используется, когда у положительно. В противном случае используется нижний.
Поэтому используйте эти простые тесты для формирования индекса в таблице поиска.
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];
}