How to get distance from point to line with distinction between side of line?

Question

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?

Answer 1

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).

Answer 2

// 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.

Answer 3

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.