I am working on using a fault algorithm for my random terrain implementation. I tried to figure out how to find the distance between a line, given two points, and a third point with a whole lot of trigonometry that didn''t end up working very well. So could anyone else help me out with it? how do you find the distance between a line defined by two points and another point? Did your file get a virus or is your coding always this bad?

okay, three points (x1,y1), (x2,y2), (x3,y3) and there is a line defined by (x1,y1) and (x2,y2).

you dont need any trigonometry. you can use simply linear algebra.

first, the equation of the line:

(y - y1) = ( y2 - y1 ) / ( x2 - x1 ) * ( x - x1 )

in order to determine the distance of a third point to this line, you need a line perpendicular to this that goes through (x3,y3).

a perpendicular lines have a negative inverted slope, so if the slope of one line is m, then the slope of a perpendicular line is -1/m.

in the case of our line, the slope is:

m = ( y2 - y1 ) / ( x2 - x1 )

and -1/m would be:

-1/m = - ( x2 - x1 ) / ( y2 - y1 )

and lets get rid of the negative sign on the outside, like so:

-1/m = ( x1 - x2 ) / ( y2 - y1 )

and we can now create the equation for the other line:

y - y3 = ( x1 - x2 ) / ( y2 - y1 ) * ( x - x3 )

solve for y for both equations, like so:

y = ( x1 - x2 ) / ( y2 - y1 ) * ( x - x3 ) + y3
y = ( y2 - y1 ) / ( x2 - x1 ) * ( x - x1 ) + y1

set the equations equal to one another:

( x1 - x2 ) / ( y2 - y1 ) * ( x - x3 ) + y3 = ( y2 - y1 ) / ( x2 - x1 ) * ( x - x1 ) + y1

From here, solve for x (it winds up being a rather convoluted equation, but at least there's no trig). after you have solved for x, plug that x into either equation to get the y. you now have the point where the two lines cross. simply calculate the distance from (x3,y3) to this new point, and you've got it.


a slightly easier form to work with for the intersection of a line is the following:

a * x + b * y + c = 0
d * x + e * y + f = 0

the solution for x where the lines cross is:

x = ( b * f - c * e ) / ( b * d - a * e )

the solution for y:

y = ( a * f - c * d ) / ( a * e - b * d )

to convert from the point slope version of the equations into this form:

( y - y3 ) * ( y2 - y1 ) + ( x2 - x1 ) * ( x - x3 ) = 0

( x2 - x1 ) * x + (y2 - y1 ) * y + ( x2 - x1 ) * x + y3 * ( y1 - y2 ) + x3 * ( x1 - x2 ) = 0

a = ( x2 - x1 )
b = ( y2 - y1 )
c = ( y3 * ( y1 - y2 ) + x3 * ( x1 - x2 ) )

(y - y1) * ( x2 - x1 ) + ( y1 - y2 ) * ( x - x1 ) = 0

(y1 - y2 ) * x + ( x2 - x1 ) * y + (y1 - y2 ) * x + y1 * ( x1 - x2 ) + x1 * ( y2 - y1 ) = 0

d = ( y1 - y2 )
e = ( x2 - x1 )
f = ( y1 * ( x1 - x2 ) + x1 * ( y2 - y1 ) )

the full equations, then:

x = ( ( y2 - y1 ) * ( y1 * ( x1 - x2 ) + x1 * ( y2 - y1 ) ) - ( y3 * ( y1 - y2 ) + x3 * ( x1 - x2 ) ) * ( x2 - x1 ) ) / ( ( y2 - y1 ) * ( y1 - y2 ) - ( x2 - x1 ) * ( x2 - x1 ) )

y = ( ( x2 - x1 ) * ( y1 * ( x1 - x2 ) + x1 * ( y2 - y1 ) ) - ( y3 * ( y1 - y2 ) + x3 * ( x1 - x2 ) ) * ( y1 - y2 ) ) / ( ( x2 - x1 ) * ( x2 - x1 ) - ( y2 - y1 ) * ( y1 - y2 ) )

told you they were ugly, but not a single sin or cos in sight!

p.s. i didn't do double checking on these equations, so i may have made an error somewhere along the line, but the basic method is outlined for doing this task.

Alternately use vectors: simpler and does not depend on it being in 2D.

If the points are A, B and C so the line is through AB and the distance from this line to point C is needed.

The most ovbious way is work out the point D on AB which is nearest C. To do this

Treating AC and AB as vectors and using the dot product and modulus work out:

d = (AC . AB) / |AB|

This is the distance of D along the line. To work out the coordinates of D we need to multiply this by a normal vector parallel to AB, e.g.

AD = d(AB / |AB|)

so

D = A + d(AB / |AB|)

And the distance is then just the length of CD, i.e. |CD|

Slow down cowboy, there is a lot simpler way to figure it out

Perpendicular distance can be found by this formula:

distance = (|ax + by + c|) / (Sqr(a^2 + b^2))

Where ax + by + c = 0 is the line and (x, y) is the point.



Trying is the first step towards failure.

Oh yeah, and if you get rid of the absolute value signs in that formula, then it will tell you whether 2 points are on the same side of the line or not (negative for 1 side, positive for the other)

Trying is the first step towards failure.