Sign in to follow this  
SPuntte

Determining whether angle is in given range

Recommended Posts

For some reason I happen not to succeed - still after several attempts - in implementing a bulletproof algorithm for solving the following problem: What I know are the limiting angles of an arc. What I want to know is if a given third angle is in that arc. All angles are wrapped to range -π < angle =< π. Of course, the sides of the arc are distinguishable from each other so it matters in which order they are given. Positive angle direction is counterclockwise. Here's a helper pic imageshack.us failed Can anyone pwn this, thx? :)

Share this post


Link to post
Share on other sites
I dont know how fast this needs to happen, and I'm making an assumption that your working in 2D space which seems to be the case. Try this:

1) Define all the angles as normalized vectors.
2) Generate two additional vectors that are 90, from you limiting vectors in the direction of you 'in range' space.

a)you can do this by creating a normal vector pointing up, then getting the cross product.

3) Get the dot product of angle(vector) your testing with both of the two new vectors. If the dot product is negative on both, your out of range.



Share this post


Link to post
Share on other sites
I didn't even think about anything like that :O

unfortunately, that sounds a bit slow for my purposes as this will used for a kind of "angle constraint" in a constrained verlet dynamics scheme.

I've come this far:
	outOfRange = True
If leftAngle < 0 And rightAngle >= 0 Then
If currentAngle < 0 Then
If currentAngle + 360 > rightangle And currentAngle + 360 < leftAngle + 360 Then
outOfRange = False
EndIf
ElseIf currentAngle + 360 > rightangle And currentAngle < leftAngle + 360 Then
outOfRange = False
EndIf
ElseIf currentAngle > rightAngle And currentAngle < leftAngle Then
outOfRange = False
EndIf



The only case it fails is when left and right hand side angles of the arc are both negative. o.O

Share this post


Link to post
Share on other sites
It might not be that slow depending on what your really doing, might be worth a shot. It may not matter, but the inherinet problem I see with your current method is your stuck with these absolute angles, there's probably alot of translation to move your degree system from world space to local space.

Share this post


Link to post
Share on other sites
This keeps bothering me. I tried the method of perpendicular vectors but discovered almost instantly that it won't work in case of an 'in range'-arc with the central angle smaller than π radians (180 degrees). Maybe my first post was unclear but the angle can be anywhere in ]0, 2π[. I still need more ideas to solve this. Thanks in advance!

Share this post


Link to post
Share on other sites
I find it a bit confusing on what you are trying to do. I assume that an angle of 0 would mean that a vector with that angle would point up in your picture and leftAngle is the angle of the red vector and rightAngle the angle of the green vector. If this is the case you should be able to check with:

assert (leftAngle >= rightAngle);
if (leftAngle >= currentAngle && currentAngle >= rightAngle)
return true;
esle
return false;



Or did I get something wrong?

Share this post


Link to post
Share on other sites
It is confusing, to me as well :S

I think the reason of my problem is the periodic nature of angles. If angles weren't periodic the solution to this problem would be as easy as checking whether (rightAngle < currentAngle && currentAngle < leftAngle) is true.

However, any virtually equal angles a and b may be different since a ≡ b mod 2π. On the other hand, this means, that any angle beyond interval [0, 2π[ will be transformed into that interval. And that is what makes the problem hard to solve.

Consider the following case:

rightAngle = 60°
leftAngle = 390° (= 360° + 30°)
currentAngle = 180°

This should yield the result 'in range', however the computer sees leftAngle as 30° and the simple check described above won't work. I think adding ±360° to one of the three angles should make it solvable as beore. Only problem is to determine the angle that needs tweaking.

I don't care if the solution applies simple binary comparsion with angles, vector math or any other method. As long as it works and is optimized I'd love it :)

fng: Since leftAngle can be (virtually) less than rightAngle, that assert-macro must not be used. The Variables rightAngle and leftAngle can hold any values. Only constraint is that the 'in range'-arc is measured ccw from rightAngle to leftAngle.

Share this post


Link to post
Share on other sites
Ah, right. I assumed that leftAngle would always be left of the 0° line.

I think I might have a solution if you use clamped values.

The simplest case is when leftAngle >= rightAngle. In this case we are on a well defined ground, as currentAngle simply has to lie in between the two.

For the other case we have the problem, that the 0° line is in our interior and this happens when leftAngle is smaller than rightAngle. If the interior contains the 0° line which makes the whole thing a bit complicated. To literally circumvent this, we check whether currentAngle is in the exterior. Now the exterior is the interior if you switch leftAngle and rightAngle. So this case does reduces to the negated check of the first case.

In code this should be:


if (leftAngle >= rightAngle)
return (rightAngle <= currentAngle && currentAngle <= leftAngle);
else
return ( !(leftAngle < currentAngle && currentAngle < rightAngle) );



You might condense this to a single if-statement to enhance speed and to completely destroy readability.

Hope it helps.

Share this post


Link to post
Share on other sites
DUDE! Thanks, a lot, it works :]

That was less complicated than I thought. Maybe I messed things up already in the beginning as I tried to implement it using angles in range ]-π, π] (What I really measure here is an angle from a vector to another so the clockwiseness is significant. That's why I wanted to keep it signed.). Now as you used range [0, 2π[ everything was a lot easier to figure and you explanation was excellent and simple.

Thank you one more time.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this