2
$\begingroup$

I have two lines, "mosquitoes", in a 3D space with equations $r_A=(-2,2,3)+t(6,-4,5)$ and $r_B=(3,5,1)+t(-7,-3,4)$. Now I want to find the equation of a line, a "spray",with direction vector $(-3,-2,-3.5)$, or rather velocity $\sqrt{25.25}$ units per second, that intersects both lines. The difficulty is is that for my problem, these lines are not really vector lines, but moving objects, and I need to make sure that after the spray hits the first mosquito, by the time it hits the second mosquito the mosquito is actually there. Basically, I want the spray to "kill two birds with one stone". This is what I've done so far:

I know that this exact question has been asked before and I know that the first solution provided works, however I am not very sure if this is the optimum solution (the least amount of distance). For the second solution, I didn't really understand where the quadratic form came from. I get that the distance is described by $d=(3,5,1)+t_2(-7,-3,4)-(-2,2,3)-t_1(6,-4,5)=(5-7t_2-6t_1,3-3t_2+4t_1,-2+4t_2-5t_1)$, where $t_1$ is the when mosquito A is hit and $t_2$ is when mosquito B is hit. I then found $|d|^2=(5-7t_2-6t_1)^2+(3-3t_2+4t_1)^2+(-2+4t_2-5t_1)^2$ and substituted in $t_2=t_1+\frac{|d|}{v}$ (as $\frac{|d|}{t_2-t_1}=v$), where $v=\sqrt{25.25}$.

I get an implicit equation, $$171t_1^2-120t_1+\frac{168}{\sqrt{25.25}}|d|t_1+\frac{74}{25.25}|d|^2-\frac{104}{\sqrt{25.25}}|d|+38=0,$$

so I used partial differentiation to optimise the values, giving me $t_1=\frac{4}{311}$, $t_2=\frac{218}{311}$ and $|d|=3.45767...$, however the time values are equal to the values I get for the shortest distance between the two lines when they are described by different parameters (where the two dot products equal $0$), and the distance value isn't even correct (it should be ~$1.203$). Obviously since I used two parameters, this seems more obvious, but I'm still confused on why this wouldn't work.

Also, even if I form a vector line with the two points of intersection, the velocity I used originally is nowhere to be found, and when I tried using random numbers for the velocity, the time values didn't change. Basically, what I'm asking is, what am I missing? There must be a way to do this but I just can't figure it out. I've thought maybe if I just decide one of the intersection points, maybe I could just use trial and error to find the most optimum? But I don't really know and any help would be greatly appreciated.

$\endgroup$
2
  • $\begingroup$ Hi! Interesting question, but please rewrite the title so that it accurately reflects the content. Thanks! $\endgroup$
    – Brian Tung
    Commented Sep 12 at 5:03
  • 1
    $\begingroup$ Oh! You had a sensible title before, and you recently edited it to something irrelevant that would almost surely eventually draw down-votes and close-votes. Please don't do that! :-) I changed your title back to the original. $\endgroup$
    – Brian Tung
    Commented Sep 12 at 5:05

1 Answer 1

1
$\begingroup$

The first mosquito trajectory is modelled by the $3D$ line

$r_A(t) = r_1 + t V_1 $

And the second mosquito trajectory is modelled by

$ r_B(t) = r_2 + t V_2 $

Note that $t$ is the same variable in both equations. Also note that $r_1, r_2, V_1, V_2 $ are known quantities.

The "missile" or "spray" is modelled by

$ r_C(t) = r_3 + t V_3 $

where $r_3$ and $V_3$ are unknown, however it is known that $|V_3| = s $ (i.e. the speed of the interceptor (the missile) is known). And the objective is to find $r_3$ and $V_3$ such that the distance travelled by the missile after hitting $r_A$ till it hits $r_B$ is minimum.

Equations:

Let $t_1$ and $t_2$ be the interception ("hitting") times for $r_A$ and $r_B$ then

$ r_1 + t_1 V_1 = r_3 + t_1 V_3 \tag{1} $

$ r_2 + t_2 V_2 = r_3 + t_2 V_3 \tag{2}$

Hence,

$ r_2 + t_2 V_2 - r_1 - t_1 V_1 = (t_2 - t_1) V_3 \tag{3} $

And immediately, we have a condition on $t_1$ and $t_2$ that follows from the fact that $V_3^T V_3 = s^2 $

Namely,

$ (r_2 + t_2 V_2 - r_1 - t_1 V_1)^T (r_2 + t_2 V_2 - r_1 - t_1 V_1) = (t_2 - t_1)^2 s^2 \tag{4} $

This is an equation of a conic in the $t_1 t_2$ plane. It could be an ellipse, a hyperbola, or a parabola.

We're interested in minimizing $t_2 - t_1$. The contours of this function (of two variables) are straight lines that make an angle of $45^\circ$ with the $t_1$ axis, and the value of $t_2 - t_1$ decreases as the contour line moves down and right.

Once the tangency point is determined, then $t_1$ and $t_2$ are known, and everything else follows from it.

Applying this method to the numerical values given in this problem, we have:

$ r_1 = (-2, 2, 3) , V_1 = (6, -4, 5) $

$ r_2 = (3,5,1) , V_2 = (-7, -3, 4) $

$s = \sqrt{25.25}$

The tangent point to the ellipse is

$(t_1, t_2) = (0.152823, 0.556005)$

So

$ V_3 = (0.473803, 4.819857, -1.33959) $

and

$ r_3 = (-1.15547, 0.652123, 3.968835) $

The minimum distance is

$ d = (t_2 - t_1) s = (0.556005-0.152823) (\sqrt{25.25} ) = 2.025963 \text{ units}$

The figure below shows the ellipse on which $t_1$ ($x$ coordinate) and $t_2$($y$ coordinate) lie. We're only concerned with the part of this ellipse that satisfies $t_2 \gt t_1 \ge 0 $. The green line is the tangent line to the ellipse having a slope of $1$.

The critical point (the tangent point) is the point colored in red. It is very close to the vertex of the ellipse along the major axis of the ellipse because of the numerical values of vectors $V_1$ and $V_2$.

enter image description here

If we change the numerical values as follows:

$ r_1 = (-2, 2, 3) , V_1 = (6, -4, 5) $

$ r_2 = (3,5,1) , V_2 = (-4, -2, 1) $

$s = \sqrt{25.25}$

Then the resulting relation between $t_1$ and $t_2$ will be a hyperbola, which is shown below

In this case, the resulting values of $t_1$ and $t_2$ corresponding to the tangent point (the red dot in the graph) are:

$t_1 = 0.137357 $

$ t_2 = 0.747268 $

And this gives

$ V_3 = (1.945835, 3.36917, -3.18) $

$ r_3 = (-1.44313, 0.987792, 4.123582) $

The minimum possible distance between the two interceptions is

$ d = (t_2 - t_1) s = (0.747268 - 0.137357) \sqrt{25.25} = 3.064763 \text{ units}$

enter image description here

Noteworthy:

The problem of finding the minimum of the function $(t_2 - t_1)$ subject to equation $(4)$ can be approached using Lagrange multiplier method. The objective function is defined as

$ f(t_1, t_2, \lambda) = t_2 - t_1 + \lambda g(t_1, t_2) \tag{5}$

where

$ g(t_1, t_2) = (r_2 + t_2 V_2 - r_1 - t_1 V_1)^T (r_2 + t_2 V_2 - r_1 - t_1 V_1) - (t_2 - t_1)^2 s^2 \tag{6}$

The function $g$ is quadratic in $t_1$ and $t_2$, and can be written compactly as

$ g(t_1, t_2) = x^T A x + x^T B + C $

where

$ x = \begin{bmatrix} t_1 \\ t_2 \end{bmatrix} $

$ A = \begin{bmatrix} V_1^T V_1 - s^2 && - V_1^T V_2 + s^2 \\ - V_1^T V_2 + s^2 && V_2^T V_2 - s^2 \end{bmatrix} $

$ B = \begin{bmatrix} -2 V_1^T (r_2 - r_1) \\ 2 V_2^T (r_2 - r_1) \end{bmatrix}$

$ C = (r_2 - r_1)^T (r_2 - r_1) $

Taking the gradient of the function defined in $(5)$, we get

$ \nabla_x f = N + \lambda \bigg( 2 A x + B \bigg) $

where $N = \begin{bmatrix} -1 \\ 1 \end{bmatrix} $

Setting the gradient equal to the zero vector, gives us

$ N = - \lambda \bigg( 2 A x + B \bigg) $

In other words, $N$ and $(2 A x + B)$ are along the same direction (parallel or opposite). This can only happen if

$ N \times (2 A x + B) = \mathbf{0} $

where the 2-vectors have been appended with a zero third component, so that the cross product is well-defined.

This cross multiplication is identical to the following matrix multiplication:

$ S_N (2 A x + B) = \mathbf{0} $

where

$ S_N = \begin{bmatrix} 0 && - N_z && N_y \\ N_z && 0 && -N_x \\ - N_y && N_x && 0 \end{bmatrix} = \begin{bmatrix} 0 && 0 && 1 \\ 0 && 0 && 1 \\ -1 && -1 && 0 \end{bmatrix} $

Note that the first two components of $ S_N (2 A x + B) $ will automatically be zero from the structure of $S_N$. Therefore, we only need to concentrate on the third components. It is straight forward to see that the third row of the above matrix-vector equation reads

$ 2 \bigg( (A_{11} + A_{21} ) t_1 + (A_{12} + A_{22} ) t_2 \bigg) + B_1 + B_2 = 0 \tag{7}$

Equation $(7)$ gives an additional relation (which is linear) between the variables $t_1$ and $t_2$.

All we have to do is solve the system of equations given by the linear equation $(7)$ and the quadratic equation $g(t_1, t_2) = 0 $.

Once we do that, we'll get $2$ solutions (or only one solution in case $g(t_1, t_2) = 0 $ represents a parabola).

Next, we have to take each of these two solutions, and validate it, that is , make sure that $t_2 \gt t_1 \ge 0 $. This validation process will result in the required solution.

Finally, once we have $t_1$ and $t_2$ we can compute $V_3$ from equation $(3)$, and then we can compute $r_3$ from $(1)$ or $(2)$.

$\endgroup$
7
  • $\begingroup$ Thank you so much for your answer, however I just have a question. I get that $V_3^T$ is the transpose of $V_3$, and that $V_3^T V_3 = s^2$, but how does this apply here? Also what do you mean by the $t_2-t_1$ plane? If I'm being honest I am a beginner when it comes to this stuff, so any clarification would be really appreciated. $\endgroup$
    – rk1625
    Commented Sep 5 at 3:00
  • $\begingroup$ Can you see the transition from equation $(3)$ to equation $(4)$? $\endgroup$
    – disgraced
    Commented Sep 5 at 7:20
  • $\begingroup$ If you do, then equation $(4)$ gives us a relation between $t_1$ and $t_2$. Plotting this equation using $x = t_1$ and $y = t_2$ gives us an ellipse in the $xy$ plane or the $t_1 t_2$ plane. That's what I meant by the $t_1 - t_2$ plane . Here the $-$ is just a connection not subtraction. I'll modify that to make it clearer. $\endgroup$
    – disgraced
    Commented Sep 5 at 7:25
  • 1
    $\begingroup$ @rk1625 If vectors $A$ and $B$ satisfy $A = \alpha B$ where $\alpha$ is a scalar, then $$A^T A = (\alpha B)^T (\alpha B) = (\alpha B^T )(\alpha B) = \alpha^2 B^T B $$. The reason why use the transpose property is to to include the magnitude of $V_3$ in the scenario, which as you can see resulted in relating the two variables $t_1$ and $t_2$. $\endgroup$
    – disgraced
    Commented Sep 5 at 9:31
  • 1
    $\begingroup$ Points $(t_1, t_2)$ on the ellipse belong to lines of the form $t_2 - t_1 = c $ for some $c$. When $c$ is minimized, then this line is becomes tangent to the ellipse. $\endgroup$
    – disgraced
    Commented Sep 8 at 11:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .