Tuesday, July 2, 2013

Solutions: Shortest distance between two skew lines in 3D

See the previous post for the question.

U mode: there are only 4 given things, two (n1 and n2) are already vectors, each tangent to its line. From the other two things, construct the difference, d = C1C2, which is a vector joining the two lines. Since the tangent vectors may be parametrization dependent, which we don't want, perhaps they have to be normalized.
Then the shortest distance has to be proportional to |d·n1 X n2|. The simplest way to determine the proportionality constant would be to do it for some test cases: pairing in each case the x-axis (s, 0, 0) with one of: (0, s, 0), (s, 1, 0), (0, s, 1), (s, s, 1) etc. and for different choices of points along the lines.

BTW the conjectured formula fails for one of the above, even though the shortest distance is well-defined. From the computational geometry point of view, the formula is computationally fragile in that is certain special cases it will be very sensitive to machine precision rounding errors.

I mode: The shortest distance between the two lines has to be the length of a segment perpendicular to both. (Why?) Hence that line segment has to be parallel to S = n1 X n2, and the distance between the two given lines is the length of that line segment.
How do we find its length if we don't even know where it lies?
We could, in M-mode, find that line by doing all sorts of stuff requiring that it intersect L1 and L2, then finding its intersection points and finally the distance between them.
Or, in U-mode, we could notice that the projection onto the unit vector s = S/|S| -of a segment joining any two points one each on the two original lines- is exactly the length of the shortest segment. How so? The line joining any two points one each on the original lines is a linear combination of s, n1 and n2. So projecting it onto s, since s n1 and s n2, will yield exactly its component along s, which is d. I know this sounds as if I've been going around in circles, but what all the above means is that we can take any two arbitrary points on L1 and L2, say C1 and C2, and calculate
d = |(C1C2)s|.

This yields the proportionality constant we were looking for in U mode, the reciprocal of the norm of S.

Another way of thinking about the solution in I mode is that the answer we are looking for is the distance between two parallel planes each of which contains one of the given lines.

No comments: