Connect two Line Segments

Question

Given two 2D line segments, A and B, how do I calculate the length of the shortest 2D line segment, C, which connects A and B?

Answer 1

This page has information you may be looking for.

Answer 2

Gernot Hoffmann paper (algorithm and Pascal code):

http://www.fho-emden.de/~hoffmann/xsegdist03072004.pdf

Answer 3

Quick tip: if you want to compare distances based on points, it's not necessary to do the square roots.

E.g. to see if P-to-Q is a smaller distance than Q-to-R, just check (pseudocode):

square(P.x-Q.x) + square(P.y-Q.y) < square(Q.x-R.x) + square(Q.y-R.y)

Answer 4

This page has a nice short description for finding the shortest distance between two lines, although @strager's link includes some code (in Fortran!)

Answer 5

Consider your two line segments A and B to be represented by two points each:

line A represented by A1(x,y), A2(x,y)

Line B represented by B1(x,y) B2(x,y)

First check if the two lines intersect using this algorithm.

If they do intersect, then the distance between the two lines is zero, and the line segment joining them is the intersection point.

If they do not intersect, Use this method: http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/ to calculate the shortest distance between:

1. point A1 and line B
2. Point A2 and line B
3. Point B1 and line A
4. Point B2 and line A

The shortest of those four line segments is your answer.

Answer 6

Afterlife's said, "First check if the two lines intersect using this algorithm," but he didn't indicate what algorithm he meant. Obviously, it's the intersection of the line segments not the extended lines which matters; any non-parallel line segments (excluding coincident endpoints which don't define a line) will intersect, but the distance between the line segments would not necessarily be zero. So I assume he meant "line segments" rather than "lines" there.

The link Afterlife gave is a very elegant approach to finding the closest point on a line (or line segment, or ray) to another arbitrary point. This works for finding the distance from each endpoint to the other line segment (constraining the calculated parameter u to be no less than 0 for a line segment or ray and to be no more than 1 for a line segment), but it doesn't handle the possiblity that an interior point on one line segment is closer than either endpoint because they actually intersect, thus the extra check about intersection is required.

As for the algorithm for determining line-segment intersection, one approach would be to find the intersection of the extended lines (if parallel then you're done), and then determine whether that point is within both line segments, such as by taking the dot-product of the vectors from the intersection point, T, to the two endpoints:

((Tx - A1x) * (Tx - A2x)) + ((Ty - A1y) * (Ty - A2y))

If this is negative (or "zero") then T is between A1 and A2 (or at one endpoint). Check similarly for the other line segment. If either was greater than "zero" then the line segments do not intersect. Of course, this depends on finding the intersection of the extended lines first, which may require expressing each line as an equation and solving the system by Gaussian reduction (etc).

But there may be a more direct way without having to solve for the intersection point, by taking the cross-product of the vectors (B1-A1) and (B2-A1) and the cross product of the vectors (B1-A2) and (B2-A2). If these cross-products are in the same direction, then A1 and A2 are on the same side of line B; if they are in opposite directions, then they are on opposite sides of line B (and if 0, then one or both are on line B). Similarly check the cross-products of vectors (A1-B1) and (A2-B1) and of (A1-B2) and (A2-B2). If any of these cross-products is "zero", or if the endpoints of both line segments fall on opposite sides of the other line, then the line segments themselves must intersect, otherwise they do not intersect.

Of course, you need a handy formula for computing a cross-product of two vectors from their coordinates. Or if you could determine the angles (being positive or negative), you wouldn't need the actual cross-product, since it's the direction of the angles between the vectors which we actually care about (or the sine of the angle, really). But I think the formula for cross-product (in 2-D) is simply:

Cross(V1,V2) = (V1x * V2y) - (V2x * V1y)

This is the z-axis component of the 3-D cross-product vector (where the x and y components must be zero, because the initial vectors are in the plane z=0), so you can simply look at the sign (or "zero").

So, you could use one of these two methods to check for line-segment intersection in the algorithm Afterlife describes (referencing the link).