Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
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 ? –  egarcia Oct 13 '10 at 23:34
    
Assume the angles are normalised to that range. –  Thomas O Oct 14 '10 at 6:34

8 Answers 8

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.

share|improve this answer
    
Thanks! I will give this a try. –  Thomas O Oct 13 '10 at 12:41
1  
I don't believe this solves the issue in the question. 345%360 == 345, and abs(345-30) is still 315. –  Gregory Avery-Weir Oct 13 '10 at 13:15
    
@Gregory: okay!, I'm sorry for the mistake. I'm editing the reply, check this new one. :) –  Vishnu Oct 14 '10 at 4:31
1  
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. –  Martin Sojka Oct 14 '10 at 7:35

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.

share|improve this answer
    
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. –  Thomas O Oct 13 '10 at 14:55
2  
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. –  Kylotan Oct 13 '10 at 15:28
    
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 –  Chewy Gumball Oct 13 '10 at 19:45
    
@Chewy, huh? The difference between 180 and 0 is not 0, and the difference between 181 and 0 is not 1... –  dash-tom-bang Oct 13 '10 at 22:30
1  
@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. –  Chewy Gumball Oct 14 '10 at 3:54

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.

share|improve this answer
    
+1 & Thanks for this. I will check it. –  Thomas O Oct 13 '10 at 14:56
    
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 –  user744 Oct 14 '10 at 10:48

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.

share|improve this answer
    
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. –  Martin Sojka Oct 14 '10 at 18:27
    
Ah, yes, you're right. I had less strict input when I tried it out. –  JasonD Oct 14 '10 at 18:36

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 ) ).

share|improve this answer
1  
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. –  Thomas O Oct 13 '10 at 14:55
1  
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. –  JasonD Oct 13 '10 at 14:58
    
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. –  Thomas O Oct 13 '10 at 15:11
    
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. :) –  Kylotan Oct 13 '10 at 15:28

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 */
share|improve this answer
    
+1 because it's clever, but on a microcontroller this is probably much worse-performing than the branching version. –  user744 Oct 14 '10 at 10:46
    
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) –  Martin Sojka Oct 14 '10 at 12:12

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.

share|improve this answer

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);
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.