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
If $m_1m_2 = -1$, then $\tan \theta_1 \tan \theta_2 = -1$, where $\theta_1, \theta_2$ are the angles of each line with the x axis. Therefore $\sin \theta_1 \sin \theta_2 + \cos \theta_1 \cos \theta_2 = 0$, so $\cos(\theta_1 - \theta_2) = 0$. Can you complete the proof from here?