Comparando ângulos e calculando a diferença

27

Quero comparar ângulos e ter uma idéia da distância entre eles. Para esta aplicação, estou trabalhando em graus, mas também funcionaria para radianos e graduados. O problema dos ângulos é que eles dependem da aritmética modular, ou seja, de 0 a 360 graus.

Digamos que um ângulo esteja em 15 graus e um em 45. A diferença é 30 graus e o ângulo de 45 graus é maior que o de 15 graus.

Mas, isso ocorre quando você tem, por exemplo, 345 e 30 graus. Embora eles sejam comparados corretamente, a diferença entre eles é de 315 graus, em vez dos 45 graus corretos.

Como posso resolver isso? Eu poderia escrever código algorítmico:

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

Mas eu prefiro uma solução que evite comparações / ramificações e dependa inteiramente da aritmética.

Thomas O
fonte
Sobre esse problema, podemos assumir que os ângulos dados estão no intervalo [0,360] ou (-infinito, + infinito)? Por exemplo, o algoritmo também deve funcionar na comparação de -130 graus com 450?
egarcia
Suponha que os ângulos sejam normalizados para esse intervalo.
Thomas O

Respostas:

29

Aqui está minha versão simplificada, sem ramificação, sem comparação, sem mín / máx:

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

Removido o módulo, pois as entradas são suficientemente restritas (obrigado a Martin por apontar isso).

Dois abdominais, três subtrai.

JasonD
fonte
Você não precisa do módulo, os valores de entrada são restritos ao intervalo [0,360] (consulte o comentário de Thomas ao envio original). Muito arrumado.
Martin Sojka
Ah, sim, você está certo. Eu tive uma entrada menos rigorosa quando tentei.
JasonD
mas e se você quisesse preservar o sinal da diferença para saber qual estava à esquerda?
Jacob Phillips
9

Embora eles sejam comparados corretamente, a diferença entre eles é de 315 graus, em vez dos 45 graus corretos.

O que faz você pensar que o 315 está incorreto? Em uma direção, são 315 graus, na outra direção, são 45. Você quer escolher o que for o menor dos 2 ângulos possíveis e isso parecer intrinsecamente exigir uma condicional. Você não pode resolvê-lo com aritmética envolvente (por exemplo, através do operador de módulo) porque, à medida que você aumenta gradualmente um ângulo, o ângulo entre eles aumenta até atingir 180 e depois começa a diminuir.

Eu acho que você precisa verificar os dois ângulos e decidir qual direção deseja medir ou calcular as duas direções e decidir qual resultado deseja.

Kylotan
fonte
Desculpe, eu deveria esclarecer. Se você fez isso ao contrário, 30 - 345 é -315 e um ângulo negativo não faz muito sentido. Acho que estou procurando o menor ângulo entre os dois. ou seja, 45 graus é menor que 315.
Thomas O
2
Mas não há 'reversão' - você tem 2 ângulos e 2 tipos de rotação que podem ser executados para fazer uma corresponder à outra. Um ângulo negativo faz todo o sentido - afinal, é apenas uma medida de rotação de um eixo arbitrário.
Kylotan
Se você deseja o menor ângulo, o abs (a1% 180 - a2% 180) fornecerá esse ângulo. No entanto, não dirá a direção. Remover os abdominais dará a você o menor ângulo "de" a1 "para" a2 "
Chewy Gumball
2
@Chewy, hein? A diferença entre 180 e 0 não é 0, e a diferença entre 181 e 0 não é 1 ...
dash-tom-bang
11
@ dash-tom-bang Você está certo. Não sei o que estava pensando, mas não estava correto agora que olho novamente. Por favor, desconsidere meu comentário anterior.
quer
4

Sempre há o truque de fazer as duas ramificações e deixar o resultado da comparação escolher uma:

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

Não sei como fazê-lo sem comparações , mas geralmente o ramo é o que torna o código lento e longo, não a comparação. Pelo menos na minha opinião, isso é mais legível do que a resposta de Martin (qualquer bom programador C o reconhecerá como um equivalente sem ramificação e verá o que está fazendo), mas também menos eficiente.

Mas, como eu disse no meu comentário, algoritmos sem ramificações são bons em processadores com pipelines profundos e previsões ruins - um microcontrolador geralmente possui um pipeline minúsculo e um PC de mesa geralmente apresenta boas previsões, portanto, a menos que você esteja direcionando um console para jogos, a versão ramificada é provavelmente a melhor rota se reduzir a contagem de instruções.

Como sempre, a criação de perfil - que pode ser tão simples quanto a contagem de operações para o seu sistema - fornecerá a resposta real.


fonte
2

Assumindo avaliações verdadeiras para -1 e avaliações falsas para 0 e '~', '&' e '|' são bit a bit não , e e ou operadores respectivamente, e estamos trabalhando com complemento de dois aritmética:

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 */
Martin Sojka
fonte
+1 porque é inteligente, mas em um microcontrolador isso provavelmente tem um desempenho muito pior que a versão ramificada.
Depende um pouco do microcontrolador, mas, sim, geralmente não vale a pena; um salto condicional (curto) geralmente é rápido o suficiente. Além disso, a terceira e a quinta linhas podem ser reescritas para serem um pouco mais rápidas usando a operação xor (^) como esta, mas as deixei na forma atual para maior clareza: temp1: = temp2 ^ ((temp2 ^ -temp2) & ~ temp1), temp2: = temp1 ^ ((temp1 ^ (360 - temp1)) & ~ temp2)
Martin Sojka
1

E isso?

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

A adição de 360 ​​existe para evitar diferenças negativas, porque um módulo de um número negativo retorna um resultado negativo. Então você obtém o menor dos dois resultados possíveis.

Ainda existe uma decisão implícita, mas não sei como evitá-la. Basicamente, você compara os dois ângulos calculando a diferença no sentido horário ou anti-horário, e parece que você deseja explicitamente a menor dessas duas diferenças. Não sei como obter esse resultado sem compará-los. Ou seja, sem usar "abs", "min", "max" ou algum operador semelhante.

CeeJay
fonte
Existem várias maneiras de calcular min, max e abs de ints sem instruções de ramificação, embora, como este seja um microcontrolador, a ramificação seja provavelmente a maneira mais rápida. graphics.stanford.edu/~seander/bithacks.html#IntegerAbs
1

Enquanto sua pergunta não fez referência a eles, vou trabalhar no pressuposto de que sua pergunta de cálculo de ângulo deriva de querer saber o ângulo mínimo entre dois vetores .

Esse cálculo é fácil. Supondo que A e B são seus vetores:

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

Se você não tivesse vetores e desejasse usar essa abordagem, poderia construir vetores de comprimento unitário, considerando seus ângulos new Vector2( cos( angle ), sin ( angle ) ).

Tetrad
fonte
11
O processador no qual estou trabalhando é um pequeno microcontrolador. Não faz sentido usar funções trigonométricas para gerar um vetor apenas para obter a diferença entre ângulos, todo ciclo é precioso.
Thomas O
11
Em um microcontrolador, fico surpreso que não seja melhor usar uma ramificação, mas não há muita aritmética na minha resposta se você realmente deseja evitar ramificações.
JasonD
Bem, uma ramificação tem dois ciclos e uma adição / subtração / etc é um ciclo, mas a ramificação também ocupa memória adicional do programa. Não é crítico, mas seria bom.
Thomas O
Sinto que sua resposta está correta e a minha está errada, mas não consigo entender por que esse é o caso. :)
Kylotan 13/10/10
1

Basicamente, o mesmo que a resposta de JasonD, exceto usando operações bit a bit em vez da função de valor absoluto.

Isso pressupõe que você tenha números inteiros curtos de 16 bits!

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
fonte
0

eu acho que

delta = (a2 + Math.ceil( -a2 / 360 ) * 360) - (a1 + Math.ceil( -a1 / 360 ) * 360);
Saad Ahmed
fonte
0

Como você se preocupa apenas em eliminar ramificações e operações "complexas" além da aritmética, eu recomendaria o seguinte:

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

Você ainda precisa de um abs lá, apesar de todos os ângulos serem positivos. Caso contrário, o resultado mais negativo será sempre escolhido (e sempre haverá exatamente uma resposta negativa para positivo, único aeb ao comparar ab e ba).

Nota: Isso não preservará a direção entre o ângulo1 e o ângulo2. Às vezes, você precisa disso para fins de IA.

Isso é semelhante à resposta de CeeJay, mas elimina todos os módulos. Não sei qual é o custo do ciclo abs, mas acho que é 1 ou 2. Difícil dizer qual é o custo min. Talvez 3? Portanto, juntamente com um ciclo por subtração, essa linha deve ter um custo entre 4 e 9.

DrZ214
fonte
0

Obtenha o ângulo relativo menor no formato assinado (+/-), da perspectiva de ter em direção à falta :

  • no máximo 180 graus | Radianos PI
  • -assinado se sentido anti-horário
  • + assinado se sentido horário

Graus

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

Radianos

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

Fundamentação

Me deparei com esse tópico depois de descobrir isso, procurando uma solução que evite o módulo; até agora não encontrei nenhum . Esta solução é para preservar o sinal de perspectiva, como @ jacob-phillips pediu neste comentário . Existem soluções mais baratas se você só precisa do menor ângulo não assinado.

ansioso
fonte
0

É uma pergunta antiga, mas me deparei com o mesmo caso - tinha que ter uma diferença angular assinada e, de preferência, sem ramificações e matemática pesada. Foi assim que acabei:

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

A limitação é que 'b' não deve ter mais que rotações 'N' em comparação com 'a'. Se você não pode garantir isso e pode permitir operações extras, use-o como primeira linha:

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

Eu tive a ideia do 13º comentário deste post: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-two-angles-keeping-the- placa

Mikk L.
fonte
-1

eu acho que eu poderia dizer

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

claro, considerando que o ângulo é medido em graus.

Vishnu
fonte
11
Não acredito que isso resolva o problema da questão. 345% 360 == 345, e os abdominais (345-30) ainda são 315.
Gregory Avery-Weir
@ Gregory: ok !, desculpe-me pelo erro. Estou editando a resposta, verifique esta nova. :)
Vishnu
11
A propósito, angle1 = angle1% 360; angle2 = angle2% 360; var distance = Math.abs (ângulo1-ângulo2); é o mesmo que var distance = Math.abs (angle1-angle2)% 360 - apenas mais devagar.
Martin Sojka