Line-Line distance

Hi,

I've been trying to make a function that finds the distance between two lines (stored as a start point and an end point) in a 2-dimensional space, but I can't seem to be able to find a way of doing it. I managed to figure out a method of getting the distance between a point and a line but when I turn that point into a line I just can't figure it out.

I tried searching both on google and here but the closest thing I could find was the distance between two skew lines in 3d space.

I'll include the code I ended up with for my point-line function (mostly to "prove" that I actually tried before running in here asking for help), it's probably not the best way of doing it but at least it works. I tried modifying this function to get it to support 2 lines instead and also tried starting over, to no avail.

I don't necessarily need the solution, just a nudge in the right direction.

Code:

float linePointDistance( Vector3d l1, Vector3d l2, Vector3d p ) { // Get the distances between the start and end point on the line float dx = l2.x - l1.x; float dy = l2.y - l1.y; // Get t, which represents how far along the line we have to move to // get to the closest point. l1 + t[dx,dy] = closest. // (found this by setting the derivative of the distance equal to 0) float t = -((l1.x-p.x)*dx + (l1.y-p.y)*dy) / (dx*dx + dy*dy); // If t isn't >= 0 and <= 1 then the closest point is outside of the // line, we therefore use the end or start point instead. Vector3d usevector; if( t > 1 ) usevector = l2; else if( t < 0 ) usevector = l1; else usevector = l1+((l2-l1)*t); return (usevector-p).magnitude(); }

First, you might want to try the games forum here.

Second, do you really mean the "shortest distance between two line segments"?

The distance formula is

sqrt( (x2-x1)**2 + (y2-y1)**2 )

Todd

(edit - oops - you want line-line distance, not point to point distance).

Thread title says line-line distance, but the function seems to indicate point-line distance... which one is it?

In general, there is no such thing as line-line distance, since lines nearly always intersect. IOW, it's only meaningful for parallel lines.

If we're talking line segments, then:
(1) if the segments meet somewhere, then the distance is zero;
(2) if the segments don't meet, then look at the distance from endpoint of A to line B (using above) and other endpoint of A to line B. Whichever is smaller, there you go.

Quote:

Originally Posted by tabstop

In general, there is no such thing as line-line distance, since lines nearly always intersect. IOW, it's only meaningful for parallel lines.

If we're talking line segments, then:
(1) if the segments meet somewhere, then the distance is zero;
(2) if the segments don't meet, then look at the distance from endpoint of A to line B (using above) and other endpoint of A to line B. Whichever is smaller, there you go.

The other case in 2D-land is where the segments form a "T" that do not touch. Then, the endpoint of the top of the vertical (for conversation purposes) to either endpoint of the horizontal is not the shortest distance between the two lines.

In 3D-land, if they don't intersect, the shortest distance is the line that is forms a perpendicular between the two lines.

Quote:

Originally Posted by tabstop

If we're talking line segments, then:
(1) if the segments meet somewhere, then the distance is zero;
(2) if the segments don't meet, then look at the distance from endpoint of A to line B (using above) and other endpoint of A to line B. Whichever is smaller, there you go.

That's indeed what I meant. And that's quite helpful, thanks! :)

Quote:

Originally Posted by Waterbottle

That's indeed what I meant. And that's quite helpful, thanks! :)

Just remember to take into account the bit that I forgot that Todd mentioned: you should check endpoints on both lines, not just one.

Quote:

Originally Posted by tabstop

Just remember to take into account the bit that I forgot that Todd mentioned: you should check endpoints on both lines, not just one.

That's still not giong to find the closest points. As Todd said, what if you have this scenario:

Code:

------------------------------------------------------------ | | | | | |

the distance between two lines is not constant.

assuming they are straight lines, the distance between them will be a linear function, so you're going to need to express the result as a slope and an intercept.

Quote:

Originally Posted by medievalelks

That's still not giong to find the closest points. As Todd said, what if you have this scenario:

Code:

------------------------------------------------------------ | | | | | |

Then the shortest distance will be found at the top endpoint of the vertical bit. There is no situation, short of intersection, where the shortest distance in 2-D is in the middle of both lines.