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'm making a 2d racing game. I'm taking the nice standard approach of having a set of points defining the center of the track and detecting whether the car is off the track by detecting its distance from the nearest point. The nicest way I've found of doing this is using the formula:

d = |Am + Bn + C| / sqrt(A^2 + B^2)

Unfortunately, to have proper collision resolution, I need to know which side of the line the car is hitting, but I can't do that with this formula because it only returns positive numbers.

So my question is: is there a formula that will give me positive or negative numbers based on which side of the line the point is on? Can I just get rid of the absolute value in the formula or do I need to do something else?

share|improve this question
    
Just in case this changes anything, I'm using Löve and Lua. I'm pretty sure it'll have all of the same math functions as any other programming language, but I'm not completely sure. I'm kind of a programming noob. :P –  tesselode Sep 14 '12 at 13:20
add comment

3 Answers

up vote 4 down vote accepted

you could multiply to the formula the sign of the z component from the resulting cross product of two vectors v, w.

given segment s with points s1,s2 you compute.

v = vector from s1 to car_pos.

w = vector from s1 to s2.

if the z component of the resulting vector r = v x w is positive then car is on the right, otherwise (z negative) the car is on the left. In practice you just need to compute the following:

float rz = v.x * w.y - w.x * v.y;
return (rz > 0);

These types of methods are known as predicates in the field of computational geometry. In particular, this one is known as is_left(segment s, point p) or equivalently is_right(segment s, point p).

share|improve this answer
    
+1 Didn't know about the 2d cross product, always had to think in terms of (1) Find perpendicular of w, call it w'. (2) Take dot product of v and w'. –  michael.bartnett Sep 14 '12 at 14:51
add comment

Consider the line with two points A (xa, ya) and B (xb, yb) and the line y = m*x + c

yb      B    /
|       |   /
y1      |  /|
|       | / |
y2      |/  |
|       /   |
|      /    |
ya    /     A
|    /
|   /
|------xb---xa-----------

To check at which side the point lies, you can just compare the y-coordinates of the point with that of line at same x position.

For A,

y1 = m*xa + c
y1 > ya

For B,

y2 = m*xb + c
y2 < yb

Then you can know to which side does the point belong.

share|improve this answer
add comment
// l1 - line start, l2 - line end, x - point
// perp() returns vec2(y,-x)  -- a perpendicular vector
// dot() returns v1.x * v2.x + v1.y * v2.y  -- it's the 2D vector dot product
// normalized() returns vec2(x/length,y/length), where length = sqrt(x*x+y*y)
ln = ( l2 - l1 ).perp().normalized();
distance = dot( ln, x ) - dot( ln, l1 );
// positive distance means that point's on the left side, negative - on the right

Note: this assumes screen-space axis directions, not the mathematical (Y+ points down, not up).

"ln" is the line normal - a normalized vector that points away from line and is perpendicular to it. The "perp" function returns the vector, turned 90 degrees counter-clockwise.

Both "dot" functions return projections of points on an axis that is defined by the line normal. "distance" is a subtraction of those projections, which makes it a distance from an infinite version of the line defined by the two points "p1" and "p2".

Now it wasn't clearly defined whether you need a finite or an infinite line (and if this, what kind of infinite). I initially assumed infinite so... this code works with all kinds of "infinite" - you really need one point and the line normal to use this method.

share|improve this answer
    
This is a good approach, and what I was going to write, but you should probably provide more explanation. –  michael.bartnett Sep 14 '12 at 14:44
add comment

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.