34
\$\begingroup\$

I want to compare angles and get an idea of the distance between them. For this application, I'm working in degrees, but it would also work for radians and grads. The problem with angles is that they depend on modular arithmetic, i.e. 0-360 degrees.

Say one angle is at 15 degrees and one is at 45. The difference is 30 degrees, and the 45 degree angle is greater than the 15 degree one.

But, this breaks down when you have, say, 345 degrees and 30 degrees. Although they compare properly, the difference between them is 315 degrees instead of the correct 45 degrees.

How can I solve this? I could write algorithmic code:

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

But I'd prefer a solution that avoids compares/branches, and relies entirely on arithmetic.

\$\endgroup\$
3
  • \$\begingroup\$ On this problem, can we assume that the angles given are in the range [0,360] or (-infinite, +infinite) ? For instance, should the algorithm also work on comparing -130 degrees with 450 ? \$\endgroup\$
    – egarcia
    Oct 13, 2010 at 23:34
  • \$\begingroup\$ Assume the angles are normalised to that range. \$\endgroup\$
    – Thomas O
    Oct 14, 2010 at 6:34
  • \$\begingroup\$ I used this solution, its worked for me stackoverflow.com/a/2007279/7604281 \$\endgroup\$
    – edu
    May 20, 2020 at 13:42

14 Answers 14

46
\$\begingroup\$

Here's my simplified, branchless, compare-free, no min/max version:

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

Removed the modulo, as the inputs are sufficiently constrained (thanks to Martin for pointing that out).

Two abs, three subtracts.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ You don't need the modulo, the input values are restricted to the [0,360] range (see Thomas' comment to the original submission). Pretty neat. \$\endgroup\$ Oct 14, 2010 at 18:27
  • 1
    \$\begingroup\$ Ah, yes, you're right. I had less strict input when I tried it out. \$\endgroup\$
    – JasonD
    Oct 14, 2010 at 18:36
  • 2
    \$\begingroup\$ but what if you wanted to preserve the sign of the difference so that you could tell which was on the left? \$\endgroup\$ Feb 18, 2019 at 23:07
  • 1
    \$\begingroup\$ The only thing I adapted from this code is that it does not return signal, as Jacob Philips stated. I did it in the quickest (and ugliest) way, expressed as ternary (a1 + angle == a2) ? angle : -angle. Man, it is ugly, but it worked! \$\endgroup\$ Jan 22, 2020 at 17:11
  • 1
    \$\begingroup\$ @E.Zacarias That shouldn't be correct because it only works if a1 is smaller than a2. For example, f(50, 20) would return -30, however f(350,20) also returns -30. Did you notice that? \$\endgroup\$
    – Shomz
    Jun 14, 2020 at 2:20
10
\$\begingroup\$

Although they compare properly, the difference between them is 315 degrees instead of the correct 45 degrees.

What makes you think 315 is incorrect? In one direction, it is 315 degrees, in the other direction, it's 45. You want to choose whichever is the smallest of the 2 possible angles and this seems to intrinsically require a conditional. You can't solve it with wrap-around arithmetic (ie. via modulus operator) because as you gradually increase one angle the angle between them grows until it hits 180 and then starts declining.

I think you either have to check both angles and decide which direction you want to measure, or calculate both directions and decide which result you want.

\$\endgroup\$
5
  • \$\begingroup\$ Sorry I should clarify. If you did it in reverse, 30 - 345 is -315 and a negative angle doesn't make much sense. I guess I'm looking for the smallest angle between the two. i.e. 45 degrees is smaller than 315. \$\endgroup\$
    – Thomas O
    Oct 13, 2010 at 14:55
  • 2
    \$\begingroup\$ But there is no 'reverse' - you have 2 angles and 2 types of rotation you can perform to make one match the other. A negative angle makes perfect sense - it's just a measure of rotation from an arbitrary axis, after all. \$\endgroup\$
    – Kylotan
    Oct 13, 2010 at 15:28
  • \$\begingroup\$ If you want the smallest angle then abs(a1%180 - a2%180) will give you that angle. It will not tell you the direction, however. Removing the abs will give you the smallest angle "going from" a1 "to" a2 \$\endgroup\$ Oct 13, 2010 at 19:45
  • 2
    \$\begingroup\$ @Chewy, huh? The difference between 180 and 0 is not 0, and the difference between 181 and 0 is not 1... \$\endgroup\$ Oct 13, 2010 at 22:30
  • 1
    \$\begingroup\$ @dash-tom-bang You are quite right. I don't know what I was thinking, but it wasn't correct at all now that I look at it again. Please disregard my previous comment. \$\endgroup\$ Oct 14, 2010 at 3:54
6
\$\begingroup\$

There's always the trick of doing both branches and letting the comparison result pick one:

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

I don't know of a way to do it without comparisons, but usually the branch is what makes code slow and long, not the compare. At least in my opinion, this is more readable than Martin's answer (any good C programmer will recognize it as a branchless equivalent and see what it's doing), but also less efficient.

But like I said in my comment, branchless algorithms are good on processors with deep pipelines and bad prediction - a microcontroller usually has a tiny pipeline, and a desktop PC usually has good prediction, so unless you are targeting a gaming console, the branching version is likely best route if it reduces instruction count.

As always, profiling - which might be as simple as op-counting for your system - will give you the real answer.

\$\endgroup\$
2
\$\begingroup\$

Assuming true evaluates to -1 and false evaluates to 0, and '~', '&' and '|' are bitwise not, and and or operators respectively, and we're working with two's-complement arithmetic:

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 */
\$\endgroup\$
2
  • 1
    \$\begingroup\$ +1 because it's clever, but on a microcontroller this is probably much worse-performing than the branching version. \$\endgroup\$
    – user744
    Oct 14, 2010 at 10:46
  • 1
    \$\begingroup\$ Depends a bit on the microcontroller, but, yes, it's usually not worth it; a (short) conditional jump is typically fast enough. Also, the third and fifth lines can be rewritten to be a bit faster by using the xor (^) operation like this, but I left them in the current form for clarity: temp1 := temp2 ^ ((temp2 ^ -temp2) & ~temp1), temp2 := temp1 ^ ((temp1 ^ (360 - temp1)) & ~temp2) \$\endgroup\$ Oct 14, 2010 at 12:12
1
\$\begingroup\$

What about this?

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

The addition of 360 is there in order to avoid negative differences, because a modulo of a negative number returns a negative result. Then you get the smaller of the two possible results.

There is still an implicit decision, but I don't know how to avoid it. Basically you compare the two angles by computing the difference clockwise or counterclockwise, and it seems that you explicitly want the smaller of these two differences. I don't know how to get that result without comparing them. That is, without using "abs", "min", "max" or some similar operator.

\$\endgroup\$
1
  • \$\begingroup\$ There are several ways to compute min, max, and abs of ints without branch instructions, though since this is a microcontroller the branch is probably the fastest way. graphics.stanford.edu/~seander/bithacks.html#IntegerAbs \$\endgroup\$
    – user744
    Oct 14, 2010 at 10:48
1
\$\begingroup\$

While your question made no reference of them, I'm going to be working on the assumption that your angle calculation question stems from wanting to know the minimum angle between two vectors.

That calculation is easy. Assuming A and B are your vectors:

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

If you didn't have vectors and wanted to use this approach you could construct unit length vectors given your angles by doing new Vector2( cos( angle ), sin ( angle ) ).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ The processor I am working on is a small microcontroller. It doesn't make sense to use trig functions to generate a vector just to get the difference between angles, every cycle is precious. \$\endgroup\$
    – Thomas O
    Oct 13, 2010 at 14:55
  • 1
    \$\begingroup\$ On a microcontroller I'm kind of suprised it's not better to use a branch, but there's not a lot of arithmatic in my answer if you really want to avoid branching. \$\endgroup\$
    – JasonD
    Oct 13, 2010 at 14:58
  • \$\begingroup\$ Well, a branch is two cycles and an add/subtract/etc is one cycle, but branching also takes up additional program memory. It's not critical, but it would be nice. \$\endgroup\$
    – Thomas O
    Oct 13, 2010 at 15:11
  • \$\begingroup\$ I get the feeling your answer is correct and mine is wrong, but I can't get my head around why that is the case. :) \$\endgroup\$
    – Kylotan
    Oct 13, 2010 at 15:28
1
\$\begingroup\$

Basically the same as JasonD's answer, except using bitwise operations instead of absolute value function.

This is assuming you have 16-bit short integers!

short angleBetween(short a,short b) {
    short x = a - b;
    short y = x >> 15;
    y = ((x + y) ^ y) - 180;
    return 180 - ((x + y) ^ y);
}
\$\endgroup\$
1
\$\begingroup\$
theta = ((destAngle - startAngle) + 180) % 360 - 180;

Will return a signed angle in the range of [-180,180] so that you can get rotational direction along with the smallest distance.

\$\endgroup\$
1
\$\begingroup\$

If we assume that you want the function work for any input angles (which could be outside the range of 0 to 360)...

a1 = a - floor(a/360)*360
b1 = b - floor(b/360)*360
diff = a1 - b1
diff_ab = (360 + diff) % 360
diff_ba = (360 - diff) % 360
smallest_diff = min(diff_ab, diff_ba)

If you're looking for extra performance, perhaps map the 0 to 2pi range to 0 to 2^n-1 so that you can use bitwise-AND masking operations instead of divide (/) and mod (%) operations.

\$\endgroup\$
0
\$\begingroup\$

I think

delta = (a2 + Math.ceil( -a2 / 360 ) * 360) - (a1 + Math.ceil( -a1 / 360 ) * 360);
\$\endgroup\$
0
\$\begingroup\$

Since you only care about eliminating branches and "complex" operations beyond arithmetic, I would recommend this:

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

You still need an abs in there despite all angles being positive. Otherwise, the most negative result will always be chosen (and there will always be exactly one negative answer for positive, unique a and b when comparing a-b and b-a).

Note: This will not preserve direction between angle1 and angle2. Sometimes you need that for AI purposes.

This is similar to CeeJay's answer, but eliminates all modulos. I don't know what the cycle cost is of abs, but I'm gonna guess it's 1 or 2. Hard to say what the cost is of min as well. Maybe 3? So along with a 1 cycle per subtraction, this line should have a cost somewhere around 4 to 9.

\$\endgroup\$
0
\$\begingroup\$

Get the smaller relative angle in signed(+/-) form, from the perspective of have towards want:

  • at most 180 degrees | PI radians
  • -signed if anticlockwise
  • +signed if clockwise

Degrees

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

Rationale

I came across this thread after I had figured this out, looking for a solution that avoids modulo; so far I have found none. This solution is for preserving the perspective sign, as @jacob-phillips asked this comment . There are cheaper solutions if you just need the shortest unsigned angle.

\$\endgroup\$
0
\$\begingroup\$

It's an old question but I ran into same case - had to get signed angular difference and preferably without branches and heavy math. This is what I ended up with:

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

The limitation is that 'b' should not have more than 'N' rotations compared to 'a'. If you can't ensure it and can allow extra operations then use this as first line:

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

I got the idea from the 13th comment of this post: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-two-angles-keeping-the-sign

\$\endgroup\$
-1
\$\begingroup\$

i guess i could say

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

ofcourse, considering the angle is measured in degrees.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I don't believe this solves the issue in the question. 345%360 == 345, and abs(345-30) is still 315. \$\endgroup\$ Oct 13, 2010 at 13:15
  • \$\begingroup\$ @Gregory: okay!, I'm sorry for the mistake. I'm editing the reply, check this new one. :) \$\endgroup\$
    – Vishnu
    Oct 14, 2010 at 4:31
  • 1
    \$\begingroup\$ By the way,angle1=angle1%360; angle2=angle2%360; var distance = Math.abs(angle1-angle2); is the same as var distance = Math.abs(angle1-angle2)%360 - just slower. \$\endgroup\$ Oct 14, 2010 at 7:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .