How to find the shortest path between two points under the restriction?

Question

Let two different points $M_1(x_1,y_1,z_1)$, $M_2(x_2,y_2,z_2)$ and two nonintersecting lines $l_1$, $l_2$ be given. How to find the shortest path between $M_1$ and $M_2$ which intersects both $l_1$ and $l_2$?

Answer 1

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]))

Answer 2

There is a shorterst path that touches both lines, but needn't be a shortest path that intersects them. Treat any line that is not between $M_1$ and $M_2$ as a $1D$ mirror and the path as that taken by light with angle of incidence=angle of reflection.

In the worst (two mirror) case, if $l_i$ has direction vector $v_i$ and the ray from $M_1$ initially has direction vector $u$, then if the ray for example touches $l_1$ first then after reflection the new direction vector will be $u'=u-(2u.v_1)v_1$ and after the second reflection $u''=u'-(2u'.v_2)v_2$. From then on the algebra gets tedious.