An unimaginative approach is to treat this as minimization of a convex function of two real variables. The input consists of:
- given points $M_1,M_2$
- first line determined by a point $P_1$ and direction vector $v_1$
- second line determined by a point $P_2$ and direction vector $v_2$
The function to be minimized is $$f(s,t)=|M_1-P_1-tv_1|+|P_1+tv_1-P_2-sv_2|+|P_2+sv_2-M_2| \tag1$$
where $|\cdot|$ means Euclidean norm. That is, assuming that we know in which order the lines should be visited. If we don't, then we look for shortest path for each order, and pick the shorter of two.
We can exclude the case where $M_1$ lies on the first line or $M_2$ lies on the second line (because then you would drop that line from consideration and simplify the problem). Then none of the terms in (1) can be zero, which implies that $f$ is differentiable. Its partial derivatives are
$$\frac{\partial f}{\partial s}
= \left\langle \frac{P_2+sv_2-M_2}{|P_2+sv_2-M_2|}-\frac{P_1+tv_1-P_2-sv_2}{|P_1+tv_1-P_2-sv_2|} ,v_2\right\rangle
\tag2$$
$$\frac{\partial f}{\partial t}
= \left\langle \frac{P_1+tv_1-P_2-sv_2}{|P_1+tv_1-P_2-sv_2|} - \frac{M_1-P_1-tv_1}{|M_1-P_1-tv_1|},v_1\right\rangle \tag3$$
After staring at (2)-(3) for a little while, I did not find any clever way to solve the system for $s,t$ symbolically.
And we'd have to do numeric comparison of two ways to visit the lines, anyway...
This looks like an appropriate problem for numeric routines, which are happy to minimize differentiable convex functions with few parameters. I tried it in Scilab, although Sage seemed to work about the same.
With your example data, the shortest path is
$( - 2, 3, - 4)$, $ ( 3.8102572, - 0.3794857, - 1.3794857)$, $(2.1548545, - 2.309709, 2.8451455)$, $ (4, - 1, 3 ) $. Its total length is $14.413266 $. Here is the picture (path in red, given lines in blue):
And here is my Scilab code (pretty ugly even by my low standards, mostly because of considering two types of paths).
function [path,path_length,tmin]=findPath(M1,M2,P1,V1,P2,V2)
function d=totalDistance(t)
d=norm(M1-P1-t(1)*V1)+norm(P1+t(1)*V1-P2-t(2)*V2)+norm(P2+t(2)*V2-M2)
endfunction
tmin = fminsearch ( totalDistance , [0,0] )
path_length = totalDistance(tmin)
path = [M1;P1+tmin(1)*V1;P2+tmin(2)*V2;M2]
endfunction
M1 = [-2,3,-4]; M2 = [4,-1,3]
P1 = [3,-4,2]; V1 = [-1,2,1]
P2 = [4,0,-1]; V2 = [1,2,2]
[path1,path_length1,tmin1] = findPath(M1,M2,P1,V1,P2,V2)
[path2,path_length2,tmin2] = findPath(M2,M1,P1,V1,P2,V2)
if path_length1<path_length2 then
path = path1; path_length = path_length1; tmin=tmin1
else
path = path2; path_length = path_length2; tmin=tmin2
end
print(%io(2),path_length, path)
clf()
line1 = [P1+(tmin(1)-2)*V1; P1+(tmin(1)+2)*V1]
line2 = [P2+(tmin(2)-2)*V2; P2+(tmin(2)+2)*V2]
param3d1(line1(:,1),line1(:,2),list(line1(:,3),[2]))
param3d1(line2(:,1),line2(:,2),list(line2(:,3),[2]))
param3d1(path(:,1),path(:,2),list(path(:,3),[5]))
Best Answer
The idea is that for the line segment of the shortest length, it has to be perpendicular to both the other lines.
Let the perpendicular line start from a point $P_1+t_1V_1$ of the first line, and have tangent vector $V_3$, i.e.: $$L_3=P_1+t_1V_1+t_3V_3$$
It should be that $$V_3\cdot V_2=0$$ $$V_3 \cdot V_1=0$$ which means that you can get $V_{3}$ as $$ V_3=V_2\times V_1$$
Now for this line to meet also the second line you need to have
$$P_1+t_1V_1+t_3V_3=P_2+t_2V_2$$
With this you have 3 linear equations in 3 variables, $t_1$,$t_2$ and $t_3$.
Once you solve for them, then:
- the distance between line 1 and line 2 will be $d=t_{3}/|V_{3}|$, to be taken, in case, as absolute value ($d$ is the "algebraic" distance in the direction of vector $V_{3}$);
- the closest points will of course be $Q_{1}=P_{1}+t_{1}V_{1}$ on line 1, and $Q_{2}=P_{2}+t_{2}V_{2}$ on line 2.