Eudicon 122 Report post Posted September 16, 2008 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? 0 Share this post Link to post Share on other sites
Wolfdog 268 Report post Posted September 16, 2008 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 = V1C - B = V2Take 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. 0 Share this post Link to post Share on other sites
jyk 2095 Report post Posted September 16, 2008 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)); 0 Share this post Link to post Share on other sites
mumblyjoe 122 Report post Posted September 16, 2008 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! 0 Share this post Link to post Share on other sites
jyk 2095 Report post Posted September 16, 2008 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). 0 Share this post Link to post Share on other sites
mumblyjoe 122 Report post Posted September 16, 2008 Quote:Original post by jykQuote: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! 0 Share this post Link to post Share on other sites