Sign in to follow this  

Left or right direction?

This topic is 3374 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by mumblyjoe
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!
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 this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by mumblyjoe
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!
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!

Share this post


Link to post
Share on other sites

This topic is 3374 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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