Left or right direction?

Recommended Posts

Hi. Given two line segments simulating a person walking some distance where one line segment starts at the tail of the other, I need to determine if a person need to walk left, right or straight. So I figure, I just calculate the angle between the two line segments using dot and cross products for the two vectors. It will answer if there is a turn, but not whether it is left or right. Example: A = (0, 10) B = (0, 0) C = (10, 0) Person starts at A, walks to B, and makes a 90 degree left turn and walks to C. But: A = (0, 10) B = (0, 0) C = (-10, 0) Person starts at A, walks to B, and makes a 90 degree right turn and walks to C. The angle is the same in the two examples. So maybe some clever person here can tell me of an easy way to determine if a left or right turn is made at B given the two line segments and the angle between them?

Share on other sites
First we need two vectors, we want to calculate the angle at point B so we get the vectors to A and C:

A - B = V1
C - B = V2

Take the relative arctan2 of the two vectors.

angle = atan2(V2.y,V2.x) - atan2(V1.y,V1.x);

You will get a negative angle for left turn and positive for right turn. The angle will be in radians so you will need to multiply it by 180/pi to get degrees.

Share on other sites
Quote:
 angle = atan2(V2.y,V2.x) - atan2(V1.y,V1.x);
I'm not sure that this will produce consistent results (although I admit I haven't checked).

In any case, I think there are better solutions. The following will tell you the direction of the turn (without error):
float perp_dot(vector2 a, vector2 b) {    return -a.y*b.x + a.x*by;}int sign(float value) {    return (value < 0) ? -1 : (value > 0 ? 1 : 0);}int relative_direction(vector2 a, vector2 b, vector2 c) {    vector2 v1 = b - a;    vector2 v2 = c - b;    return sign(perp_dot(v1, v2));}
If you need the signed angle as well, it can be computed as follows:
float angle = atan2(perp_dot(v1, v2), dot(v1, v2));

Share on other sites
We often use something like this as an interview question. :)

You don't need the angle at all to decide whether to turn left or right.

First: construct two vectors (A-B) and (C-B). These vectors are both based at B, so they're not the actual movement vectors, but that's OK since you're trying to decide what to do at B.

The cross products of these two vectors results in another vector. The dot product of that vector with the "up" vector (in this case, (0,0,1) will result in either a positive, negative, or zero result, which can be interpreted as the sin of the smaller angle between the two vectors (if they were normalized)

Assuming you're using right-handed coordinates, a positive result means making a left-hand turn, and a negative result means making a right-hand turn. A zero result is a singularity: it could be no turn, or it could be a 180-degree turn; you need to detect that separately.

You may want to double-check my math... but that's the overview. Have fun!

Share on other sites
Quote:
 Original post by mumblyjoeWe often use something like this as an interview question. :)You don't need the angle at all to decide whether to turn left or right.First: construct two vectors (A-B) and (C-B). These vectors are both based at B, so they're not the actual movement vectors, but that's OK since you're trying to decide what to do at B.The cross products of these two vectors results in another vector. The dot product of that vector with the "up" vector (in this case, (0,0,1) will result in either a positive, negative, or zero result, which can be interpreted as the sin of the smaller angle between the two vectors (if they were normalized)Assuming you're using right-handed coordinates, a positive result means making a left-hand turn, and a negative result means making a right-hand turn. A zero result is a singularity: it could be no turn, or it could be a 180-degree turn; you need to detect that separately.You may want to double-check my math... but that's the overview. Have fun!
That's the same as the solution I presented above (although I provided the 2-d version, since the OP's example was in 2-d).

Share on other sites
Quote:
Original post by jyk
Quote:
 Original post by mumblyjoeWe often use something like this as an interview question. :)You don't need the angle at all to decide whether to turn left or right.First: construct two vectors (A-B) and (C-B). These vectors are both based at B, so they're not the actual movement vectors, but that's OK since you're trying to decide what to do at B.The cross products of these two vectors results in another vector. The dot product of that vector with the "up" vector (in this case, (0,0,1) will result in either a positive, negative, or zero result, which can be interpreted as the sin of the smaller angle between the two vectors (if they were normalized)Assuming you're using right-handed coordinates, a positive result means making a left-hand turn, and a negative result means making a right-hand turn. A zero result is a singularity: it could be no turn, or it could be a 180-degree turn; you need to detect that separately.You may want to double-check my math... but that's the overview. Have fun!
That's the same as the solution I presented above (although I provided the 2-d version, since the OP's example was in 2-d).

Indeed it is! I misread your last line and thought you required the angle calculation. Sorry!

Create an account

Register a new account

• Forum Statistics

• Total Topics
627719
• Total Posts
2978789

• 9
• 21
• 14
• 12
• 42