Comparer les angles et calculer la différence

27

Je veux comparer les angles et avoir une idée de la distance entre eux. Pour cette application, je travaille en degrés, mais cela fonctionnerait également pour les radians et les diplômés. Le problème avec les angles est qu'ils dépendent de l'arithmétique modulaire, c'est-à-dire 0-360 degrés.

Disons qu'un angle est à 15 degrés et un à 45. La différence est de 30 degrés et l'angle de 45 degrés est supérieur à celui de 15 degrés.

Mais cela tombe en panne lorsque vous avez, disons, 345 degrés et 30 degrés. Bien qu'ils se comparent correctement, la différence entre eux est de 315 degrés au lieu des 45 degrés corrects.

Comment puis-je résoudre ça? Je pourrais écrire du code algorithmique:

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

Mais je préférerais une solution qui évite les comparaisons / branches, et repose entièrement sur l'arithmétique.

Thomas O
la source
Sur ce problème, peut-on supposer que les angles donnés sont compris entre [0,360] ou (-infini, + infini)? Par exemple, l'algorithme devrait-il également fonctionner pour comparer -130 degrés à 450?
egarcia
Supposons que les angles sont normalisés dans cette plage.
Thomas O

Réponses:

29

Voici ma version simplifiée, sans branche, sans comparaison, sans min / max:

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

Suppression du modulo, car les entrées sont suffisamment contraintes (merci à Martin de l'avoir signalé).

Deux abdos, trois soustraits.

JasonD
la source
Vous n'avez pas besoin du modulo, les valeurs d'entrée sont limitées à la plage [0,360] (voir le commentaire de Thomas à la soumission d'origine). Génial.
Martin Sojka
Ah, oui, tu as raison. J'avais une entrée moins stricte quand je l'ai essayée.
JasonD
mais que se passe-t-il si vous voulez conserver le signe de la différence pour pouvoir voir lequel se trouve à gauche?
Jacob Phillips
9

Bien qu'ils se comparent correctement, la différence entre eux est de 315 degrés au lieu des 45 degrés corrects.

Qu'est-ce qui vous fait penser que 315 est incorrect? Dans un sens, c'est 315 degrés, dans l'autre sens, c'est 45. Vous voulez choisir le plus petit des 2 angles possibles et cela semble intrinsèquement nécessiter un conditionnel. Vous ne pouvez pas le résoudre avec l'arithmétique enveloppante (c'est-à-dire via l'opérateur de module) parce que lorsque vous augmentez progressivement un angle, l'angle entre les deux augmente jusqu'à ce qu'il atteigne 180, puis commence à décliner.

Je pense que vous devez soit vérifier les deux angles et décider dans quelle direction vous voulez mesurer, soit calculer les deux directions et décider quel résultat vous voulez.

Kylotan
la source
Désolé, je dois clarifier. Si vous l'avez fait à l'envers, 30 - 345 est -315 et un angle négatif n'a pas beaucoup de sens. Je suppose que je cherche le plus petit angle entre les deux. soit 45 degrés est plus petit que 315.
Thomas O
2
Mais il n'y a pas de «marche arrière» - vous avez 2 angles et 2 types de rotation que vous pouvez effectuer pour faire correspondre l'un à l'autre. Un angle négatif est parfaitement logique - ce n'est qu'une mesure de rotation à partir d'un axe arbitraire, après tout.
Kylotan
Si vous voulez le plus petit angle, alors abs (a1% 180 - a2% 180) vous donnera cet angle. Cependant, il ne vous dira pas la direction. La suppression des abdominaux vous donnera le plus petit angle "allant de" a1 "à" a2
Chewy Gumball
2
@Chewy, hein? La différence entre 180 et 0 n'est pas 0, et la différence entre 181 et 0 n'est pas 1 ...
dash-tom-bang
1
@ dash-tom-bang Vous avez tout à fait raison. Je ne sais pas à quoi je pensais, mais ce n'était pas correct du tout maintenant que je le revois. Veuillez ignorer mon commentaire précédent.
Chewy Gumball
4

Il y a toujours l'astuce de faire les deux branches et de laisser le résultat de la comparaison en choisir une:

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

Je ne connais pas de moyen de le faire sans comparaisons , mais généralement la branche est ce qui rend le code lent et long, pas la comparaison. Au moins à mon avis, c'est plus lisible que la réponse de Martin (tout bon programmeur C le reconnaîtra comme un équivalent sans branche et verra ce qu'il fait), mais aussi moins efficace.

Mais comme je l'ai dit dans mon commentaire, les algorithmes sans branche sont bons sur les processeurs avec des pipelines profonds et une mauvaise prédiction - un microcontrôleur a généralement un petit pipeline, et un PC de bureau a généralement une bonne prédiction, donc à moins que vous ne cibliez une console de jeu, la version de branchement est probablement le meilleur itinéraire s'il réduit le nombre d'instructions.

Comme toujours, le profilage - qui peut être aussi simple que le comptage d'opérations pour votre système - vous donnera la vraie réponse.


la source
2

En supposant que true est évalué à -1 et false à 0, et '~', '&' et '|' ne sont pas au niveau du bit , et et ou des opérateurs respectivement, et nous travaillons avec l'arithmétique du complément à deux:

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
la source
+1 parce que c'est intelligent, mais sur un microcontrôleur, c'est probablement beaucoup moins performant que la version de branchement.
Cela dépend un peu du microcontrôleur, mais, oui, cela n'en vaut généralement pas la peine; un saut conditionnel (court) est généralement assez rapide. En outre, les troisième et cinquième lignes peuvent être réécrites pour être un peu plus rapides en utilisant l'opération xor (^) comme ceci, mais je les ai laissées dans la forme actuelle pour plus de clarté: temp1: = temp2 ^ ((temp2 ^ -temp2) & ~ temp1), temp2: = temp1 ^ ((temp1 ^ (360 - temp1)) & ~ temp2)
Martin Sojka
1

Et ça?

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

L'ajout de 360 ​​est là pour éviter les différences négatives, car un module d'un nombre négatif renvoie un résultat négatif. Ensuite, vous obtenez le plus petit des deux résultats possibles.

Il y a toujours une décision implicite, mais je ne sais pas comment l'éviter. Fondamentalement, vous comparez les deux angles en calculant la différence dans le sens horaire ou antihoraire, et il semble que vous souhaitiez explicitement la plus petite de ces deux différences. Je ne sais pas comment obtenir ce résultat sans les comparer. C'est-à-dire sans utiliser "abs", "min", "max" ou un opérateur similaire.

CeeJay
la source
Il existe plusieurs façons de calculer les valeurs min, max et abs des entiers sans instructions de branchement, mais comme il s'agit d'un microcontrôleur, la branche est probablement le moyen le plus rapide. graphics.stanford.edu/~seander/bithacks.html#IntegerAbs
1

Bien que votre question n'en fasse aucune référence, je vais travailler sur l'hypothèse que votre question de calcul d'angle découle de vouloir connaître l'angle minimum entre deux vecteurs .

Ce calcul est facile. En supposant que A et B sont vos vecteurs:

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

Si vous n'aviez pas de vecteurs et que vous vouliez utiliser cette approche, vous pourriez construire des vecteurs de longueur unitaire en fonction de vos angles new Vector2( cos( angle ), sin ( angle ) ).

Tetrad
la source
1
Le processeur sur lequel je travaille est un petit microcontrôleur. Il n'est pas logique d'utiliser des fonctions trigonométriques pour générer un vecteur juste pour faire la différence entre les angles, chaque cycle est précieux.
Thomas O
1
Sur un microcontrôleur, je suis en quelque sorte surpris qu'il ne vaut pas mieux utiliser une branche, mais il n'y a pas beaucoup d'arithmatique dans ma réponse si vous voulez vraiment éviter de créer une branche.
JasonD
Eh bien, une branche est de deux cycles et un ajout / soustraction / etc est un cycle, mais la ramification prend également de la mémoire de programme supplémentaire. Ce n'est pas critique, mais ce serait bien.
Thomas O
J'ai l'impression que votre réponse est correcte et la mienne est fausse, mais je ne peux pas comprendre pourquoi c'est le cas. :)
Kylotan
1

Fondamentalement la même que la réponse de JasonD, sauf en utilisant des opérations au niveau du bit au lieu de la fonction de valeur absolue.

Cela suppose que vous avez des entiers courts 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
la source
0

je pense

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

Puisque vous ne vous souciez que d'éliminer les branches et les opérations "complexes" au-delà de l'arithmétique, je recommanderais ceci:

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

Vous avez toujours besoin d'un absdedans malgré tous les angles positifs. Sinon, le résultat le plus négatif sera toujours choisi (et il y aura toujours exactement une réponse négative pour positif et unique a et b lors de la comparaison de ab et ba).

Remarque: Cela ne préservera pas la direction entre l'angle1 et l'angle2. Parfois, vous en avez besoin à des fins d'IA.

Ceci est similaire à la réponse de CeeJay, mais élimine tous les modules. Je ne sais pas quel est le coût du cycle abs, mais je suppose que c'est 1 ou 2. Difficile de dire également quel est le coût min. Peut-être 3? Ainsi, avec un cycle par soustraction, cette ligne devrait avoir un coût d'environ 4 à 9.

DrZ214
la source
0

Obtenez l' angle relatif le plus petit sous forme signée (+/-), du point de vue de l' avoir vers le besoin :

  • au plus 180 degrés | PI radians
  • -signé si dans le sens inverse des aiguilles d'une montre
  • + signé si dans le sens horaire

Degrés

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

Radians

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

Raisonnement

Je suis tombé sur ce fil après avoir compris cela, à la recherche d'une solution qui évite le modulo; jusqu'à présent, je n'en ai trouvé aucun . Cette solution est pour conserver le signe de perspective, comme @ jacob-phillips a demandé ce commentaire . Il existe des solutions moins chères si vous avez juste besoin de l'angle non signé le plus court.

anx
la source
0

C'est une vieille question mais je suis tombé sur le même cas - j'ai dû obtenir une différence angulaire signée et de préférence sans branches et mathématiques lourdes. Voici ce que j'ai fini avec:

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

La limitation est que «b» ne devrait pas avoir plus de «N» rotations que «a». Si vous ne pouvez pas le garantir et pouvez autoriser des opérations supplémentaires, utilisez-le comme première ligne:

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

J'ai eu l'idée du 13ème commentaire de cet article: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-two-angles-keeping-the- signe

Mikk L.
la source
-1

je suppose que je pourrais dire

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

bien sûr, étant donné que l'angle est mesuré en degrés.

Vishnu
la source
1
Je ne crois pas que cela résout le problème dans la question. 345% 360 == 345, et abs (345-30) est toujours 315.
Gregory Avery-Weir
@Gregory: ok !, je suis désolé pour l'erreur. J'édite la réponse, vérifiez cette nouvelle. :)
Vishnu
1
Par ailleurs, angle1 = angle1% 360; angle2 = angle2% 360; var distance = Math.abs (angle1-angle2); est identique à var distance = Math.abs (angle1-angle2)% 360 - juste plus lentement.
Martin Sojka