Сравнение углов и отработка разницы

27

Я хочу сравнить углы и получить представление о расстоянии между ними. Для этого приложения я работаю в градусах, но оно также будет работать для радианов и градов. Проблема с углами заключается в том, что они зависят от модульной арифметики, то есть от 0 до 360 градусов.

Скажем, один угол составляет 15 градусов, а другой - 45. Разница составляет 30 градусов, а угол 45 градусов больше, чем 15 градусов.

Но это ломается, когда у вас есть, скажем, 345 градусов и 30 градусов. Хотя они сравниваются правильно, разница между ними составляет 315 градусов вместо правильных 45 градусов.

Как я могу решить это? Я мог бы написать алгоритмический код:

if(angle1 > angle2) delta_theta = 360 - angle2 - angle1;
else delta_theta = angle2 - angle1;

Но я бы предпочел решение, которое избегает сравнений / ветвей и полностью полагается на арифметику.

Томас О
источник
По этой проблеме, можем ли мы предположить, что данные углы находятся в диапазоне [0,360] или (-бесконечно, + бесконечно)? Например, должен ли алгоритм работать при сравнении -130 градусов с 450?
egarcia 13.10.10
Предположим, что углы нормализованы к этому диапазону.
Томас О,

Ответы:

29

Вот моя упрощенная, без ветвлений, без сравнения, без мин / макс версия:

angle = 180 - abs(abs(a1 - a2) - 180); 

Удален по модулю, поскольку входы достаточно ограничены (спасибо Мартину за то, что указал на это).

Два пресса, три вычитания.

JasonD
источник
Вам не нужно по модулю, входные значения ограничены диапазоном [0,360] (см. Комментарий Томаса к исходному представлению). Довольно аккуратно.
Мартин Сойка
Ах да, ты прав. У меня был менее строгий ввод, когда я попробовал это.
JasonD
но что, если вы хотите сохранить знак различия, чтобы вы могли определить, что было слева?
Джейкоб Филлипс
9

Хотя они сравниваются правильно, разница между ними составляет 315 градусов вместо правильных 45 градусов.

Что заставляет вас думать, что 315 неверно? В одном направлении это 315 градусов, в другом направлении - 45. Вы хотите выбрать, какой из наименьших из двух возможных углов, и это, по сути, требует условного. Вы не можете решить эту проблему с помощью арифметики обтекания (т. Е. С помощью оператора модуля), поскольку при постепенном увеличении одного угла угол между ними увеличивается, пока не достигнет 180, а затем начнет уменьшаться.

Я думаю, что вы должны либо проверить оба угла и решить, какое направление вы хотите измерить, либо рассчитать оба направления и решить, какой результат вы хотите.

Kylotan
источник
Извините, я должен уточнить. Если вы сделали это в обратном порядке, 30 - 345 - это -315, и отрицательный угол не имеет большого смысла. Я думаю, что я ищу наименьший угол между двумя. то есть 45 градусов меньше, чем 315.
Томас О
2
Но «обратного хода» нет - у вас есть 2 угла и 2 типа поворота, которые вы можете выполнить, чтобы один соответствовал другому. Отрицательный угол имеет смысл - это всего лишь мера вращения от произвольной оси, в конце концов.
Kylotan
Если вы хотите наименьший угол, то abs (a1% 180 - a2% 180) даст вам этот угол. Это не скажет вам направление, как бы то ни было. Удаление абс даст вам наименьший угол "переход от" a1 "к" a2
Chewy Gumball
2
@ Чуви, а? Разница между 180 и 0 не равна 0, а разница между 181 и 0 не равна 1 ...
dash-tom-bang
1
@ dash-tom-bang Вы совершенно правы. Я не знаю, о чем я думал, но теперь я не совсем правильно смотрю на это. Пожалуйста, не обращайте внимания на мой предыдущий комментарий.
Chewy Gumball
4

Всегда есть способ сделать обе ветви и позволить результату сравнения выбрать один:

delta_theta = (angle1 > angle2) * (360 - angle2 - angle1)
              + (angle2 > angle1) * (angle2 - angle1);

Я не знаю способа сделать это без сравнений , но обычно ветвь делает код медленным и длинным, а не сравнение. По крайней мере, на мой взгляд, это более читабельно, чем ответ Мартина (любой хороший программист на Си распознает его как эквивалент без ветвей и увидит, что он делает), но также менее эффективно.

Но, как я уже сказал в своем комментарии, алгоритмы без ответвлений хороши для процессоров с глубокими конвейерами и плохим предсказанием - микроконтроллер обычно имеет крошечный конвейер, а настольный ПК обычно имеет хороший прогноз, поэтому, если вы не ориентируетесь на игровую консоль, версию ветвления вероятно, лучший маршрут, если он уменьшает количество команд.

Как всегда, профилирование - которое может быть таким же простым, как подсчет операций для вашей системы - даст вам реальный ответ.


источник
2

Предполагая, что значение true равно -1, а значение false равно 0, а '~', '&' и '|' поразрядно нет , и и или операторы соответственно, и мы работаем с арифметикой с двумя дополнениями:

temp1 := angle1 > angle2
/* most processors can do this without a jump; for example, under the x86 family,
   it's the result of CMP; SETLE; SUB .., 1 instructions */
temp2 := angle1 - angle2
temp1 := (temp1 & temp2) | (~temp1 & -temp2)
/* in x86 again: only SUB, AND, OR, NOT and NEG are used, no jumps
   at this point, we have the positive difference between the angles in temp1;
   we can now do the same trick again */
temp2 := temp1 > 180
temp2 := (temp2 & temp1) | (~temp2 & (360 - temp1))
/* the result is in temp2 now */
Мартин Сойка
источник
+1, потому что это умно, но на микроконтроллере это, вероятно, намного хуже, чем версия с ветвлением.
Немного зависит от микроконтроллера, но, как правило, оно того не стоит; (короткий) условный переход обычно достаточно быстр. Кроме того, третью и пятую строки можно переписать так, чтобы они выполнялись немного быстрее с помощью такой операции xor (^), но я оставил их в текущей форме для ясности: temp1: = temp2 ^ ((temp2 ^ -temp2) & ~ temp1), temp2: = temp1 ^ ((temp1 ^ (360 - temp1)) & ~ temp2)
Мартин Сойка,
1

Как насчет этого?

min( (a1-a2+360)%360, (a2-a1+360)%360 )

Добавление 360 есть во избежание отрицательных различий, потому что по модулю отрицательного числа возвращается отрицательный результат. Тогда вы получите меньший из двух возможных результатов.

Есть еще неявное решение, но я не знаю, как его избежать. По сути, вы сравниваете два угла, вычисляя разницу по часовой стрелке или против часовой стрелки, и кажется, что вам явно требуется меньшее из этих двух различий. Я не знаю, как получить этот результат, не сравнивая их. То есть без использования «abs», «min», «max» или какого-либо подобного оператора.

CeeJay
источник
Существует несколько способов вычисления минимальных, максимальных и абсолютных значений для целых чисел без инструкций ветвления, хотя, поскольку это микроконтроллер, ветвление, вероятно, является самым быстрым способом. graphics.stanford.edu/~seander/bithacks.html#IntegerAbs
1

Хотя ваш вопрос о них не упоминается, я буду работать с предположением, что ваш вопрос об определении угла связан с желанием узнать минимальный угол между двумя векторами .

Этот расчет прост. Предполагая, A и B ваши векторы:

angle_between = acos( Dot( A.normalized, B.normalized ) )

Если у вас не было векторов и вы хотели использовать этот подход, вы могли бы делать векторы единичной длины с учетом ваших углов new Vector2( cos( angle ), sin ( angle ) ).

тетрада
источник
1
Процессор, над которым я работаю, - это небольшой микроконтроллер. Нет смысла использовать функции триггера для генерации вектора, просто чтобы получить разницу между углами, каждый цикл драгоценен.
Томас О
1
На микроконтроллере я немного удивлен, что не лучше использовать ветку, но в моем ответе не так много арифметики, если вы действительно хотите избежать ветвления.
JasonD
Хорошо, ветвь - это два цикла, а сложение / вычитание / и т. Д. - это один цикл, но ветвление также требует дополнительной памяти программы. Это не критично, но было бы неплохо.
Томас О
Я чувствую, что ваш ответ правильный, а мой неправильный, но я не могу понять , почему это так. :)
Kylotan
1

В основном так же, как ответ JasonD, за исключением использования побитовых операций вместо функции абсолютного значения.

Предполагается, что у вас есть 16-битные короткие целые числа!

short angleBetween(short a,short b) {
    short x = a - b;
    short y = x >> 15;
    y = ((x + y) ^ y) - 180;
    return 180 - ((x + y) ^ y);
}
MickLH
источник
0

я думаю

delta = (a2 + Math.ceil( -a2 / 360 ) * 360) - (a1 + Math.ceil( -a1 / 360 ) * 360);
Саад Ахмед
источник
0

Так как вы заботитесь только об исключении ветвей и «сложных» операций помимо арифметики, я бы порекомендовал это:

min(abs(angle1 - angle2), abs(angle2 - angle1))

Вам все еще нужно abs там, несмотря на то, что все углы положительны. В противном случае всегда будет выбран самый отрицательный результат (и всегда будет ровно один отрицательный ответ для положительных, уникальных a и b при сравнении ab и ba).

Примечание. Это не сохранит направление между углом1 и углом2. Иногда это нужно для целей ИИ.

Это похоже на ответ CeeJay, но устраняет все модули. Я не знаю, какова стоимость цикла abs, но я предполагаю, что это 1 или 2. Трудно сказать, minсколько стоит стоимость . Может 3? Таким образом, наряду с 1 циклом на вычитание, эта строка должна стоить где-то около 4-9.

DrZ214
источник
0

Получите меньший относительный угол в подписанном виде (+/-), с точки зрения иметь в стороне нужды :

  • максимум 180 градусов | Пи радианы
  • -подписан, если против часовой стрелки
  • + подписано, если по часовой стрелке

степени

PITAU = 360 + 180 # for readablility
signed_diff = ( want - have + PITAU ) % 360 - 180

Радиан

PI = 3.14; TAU = 2*PI; PITAU = PI + TAU;
signed_diff = ( want - have + PITAU ) % TAU - PI

обоснование

Я натолкнулся на эту тему после того, как понял это, в поисках решения, которое бы избегало по модулю; до сих пор я не нашел ни одного . Это решение предназначено для сохранения знака перспективы, поскольку @ jacob-phillips задал этот комментарий . Есть более дешевые решения, если вам нужен только самый короткий угол без знака.

апх
источник
0

Это старый вопрос, но я столкнулся с тем же случаем - нужно было получить угловую разницу со знаком, желательно без веток и тяжелой математики. Вот чем я закончил:

int d = (a - b) + 180 + N * 360; // N = 1, 2 or more.
int r = (d / 360) * 360;
return (d - r) - 180;

Ограничение состоит в том, что «b» не должно иметь более чем «N» оборотов по сравнению с «a». Если вы не можете гарантировать это и можете разрешить дополнительные операции, используйте следующую строку:

int d = ((a % 360) - (b % 360)) + 540;

Я получил идею из 13-го комментария этого поста: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-two-angles-keeping-the- подписать

Микк Л.
источник
-1

я думаю, что могу сказать

angle1=angle1%360;
angle2=angle2%360;
var distance = Math.abs(angle1-angle2);
//edited
if(distance>180)
  distance=360-distance;

Конечно, учитывая угол измеряется в градусах.

Вишну
источник
1
Я не верю, что это решает проблему в вопросе. 345% 360 == 345, а abs (345-30) все еще 315.
Грегори Эйвери-Вейр
@Gregory: ладно !, прошу прощения за ошибку. Я редактирую ответ, проверьте этот новый. :)
Вишну
1
Кстати, angle1 = angle1% 360; angle2 = angle2% 360; var distance = Math.abs (angle1-angle2); то же самое, что var distance = Math.abs (angle1-angle2)% 360 - только медленнее.
Мартин Сойка