The closest points on a line and an ellipsoid

Question

Inspired by this problem, I've devised the following problem where the cone is replaced with an ellipsoid.

Given the line

$$ p(t) = p_0 + t \ d $$

where WLOG, $d$ is a unit vector, and the ellipsoid,

$$ (r - r_0)^T Q (r - r_0) = 1 $$

find $p$ and $r$ that are closest to each other.

My attempt:

It is well-known that the vector connecting $p$ and $r$ at the minimum distance must be perpendicular to the line as well as the ellipsoid. This means that

$ (p(t) - r) \cdot d = 0 \hspace{50pt}(1)$

and

$ p(t) - r = K Q (r - r_0) \hspace{50pt}(2)$

where $K$ is constant but unknown.

Using the definition of $p(t)$ in the first equation, gives us

$( p_0 + t d - r ) \cdot d = 0 \hspace{50pt}(3)$

So

$ t = - (p_0 - r) \cdot d \hspace{50pt}(4)$

(because $d \cdot d = 1 $)

Substituting this into the second equation,

$ p_0 - ((p_0 - r) \cdot d) d - r = K Q (r - r_0) \hspace{50pt}(5) $

which simplifies to,

$ P (p_0 - r) = K Q (r - r_0) \hspace{50pt}(6)$

where

$P = I - {d d}^T \hspace{50pt}(7)$

So now I have four unknowns which are the $3$ coordinates of $r$ and the constant $K$, and I have $4$ equations comprised of $1$ quadratic equation which is the equation of the ellipsoid, and $3$ more quadratic equations involving $r$ and $K$ (vector equation (6) ). I don't know how to solve these $4$ equations.

Any hints, pointers, or solutions are highly appreciated. Thank you all.

Answer 1

I found that the constant $K$ in the body of the question can be eliminated through cross product of the the vectors involved. We want

$ P(p_0 - r) = K Q (r - r_0) \hspace{10pt}(1) $

This is equivalent to

$ P (p_0 - r) \times Q (r - r_0) = \mathbf{0} \hspace{10pt}(2) $

Let $e_1, e_2, e_3$ be the unit vectors along $x, y$ and $z$, and define

$ C_1 = e_2 e3^T - e_3 e_2^T $

$ C_2 = e_3 e_1^T - e_1 e_3^T $

$ C_3 = e_1 e_2^T - e_2 e_1 ^T $

Then $(2)$ is equivalent to

$ (p_0 - r)^T P C_1 Q (r - r_0) = 0 \hspace{10pt}(3) $

$ (p_0 - r)^T P C_2 Q (r - r_0) = 0 \hspace{10pt}(4)$

$ (p_0 - r)^T P C_3 Q (r - r_0) = 0 \hspace{10pt} (5)$

In addition to these three equations, we have

$ (r - r_0)^T Q (r - r_0) = 1 \hspace{10pt}(6)$

Equations $(3) - (6)$ are quadratic in $r$. Choosing two the equations $(3)-(5)$ in combination with equation $(6)$, generates possible candidates for the solution. The solutions generated have to satisfy the third equation in the set $(3) - (5)$ that was not chosen for the solver. For example, we can choose equations $(3), (4), (6)$ and generate all the possible solutions, then check each solution for satisfaction of equation $(5)$. If a solution does not satisfy $(5)$ we just discard it. Now out of the acceptable solutions, we calculate

$ t = - (p_0 - r) \cdot d \hspace{10pt}(7)$

And hence calculate the point on the line $p$, and the distance between $p$ and $r$. Then we choose the minimum value of the distance out of all acceptable solutions.

Answer 2

! not a solution

As you stated, a ray is described by

$$ \boldsymbol{r}(t)=\boldsymbol{p}_{0}+t\,\boldsymbol{d} $$

_{Notational note, boldface symbols are vectors, italic symbols are scalars, and bold upright symbols are matrices.}

Without loss of generality, place the coordinate origin at the center of the ellipsoid, and align it with the principal axes.

The equation for points on the surface of the ellipsoid is

$$\boldsymbol{r}^{\intercal}{\bf Q}\boldsymbol{r}=1$$

where the diagonal matrix ${\bf Q}=\begin{bmatrix}\tfrac{1}{r_{1}^{2}}\\ & \tfrac{1}{r_{2}^{2}}\\ & & \tfrac{1}{r_{3}^{2}} \end{bmatrix}$ describes the ellipsoid from the three principal radii.

Combine the two equations to get to

$$ \left(\boldsymbol{p}_{0}^{\intercal}{\bf Q}\boldsymbol{p}_{0}\right)+2\,t\,\left(\boldsymbol{p}_{0}^{\intercal}{\bf Q}\boldsymbol{d}\right)+t^{2}\left(\boldsymbol{d}^{\intercal}{\bf Q}\boldsymbol{d}\right)=1 $$

which is a quadratic of the form $c+2t\,b+t^{2}a=1$ with solutions

$$ t=-\frac{b}{a}\pm\sqrt{\left(\frac{b}{a}\right)^{2}+\frac{1-c}{a}} $$

This gives the two intersections points if any.

or in terms of the original vectors

$$ t=-\frac{\boldsymbol{p}_{0}^{\intercal}{\bf Q}\boldsymbol{d}}{\boldsymbol{d}^{\intercal}{\bf Q}\boldsymbol{d}}\pm\sqrt{\left(\frac{\boldsymbol{p}_{0}^{\intercal}{\bf Q}\boldsymbol{d}}{\boldsymbol{d}^{\intercal}{\bf Q}\boldsymbol{d}}\right)^{2}+\frac{1-\boldsymbol{p}_{0}^{\intercal}{\bf Q}\boldsymbol{p}_{0}}{\boldsymbol{d}^{\intercal}{\bf Q}\boldsymbol{d}}} $$

But if there is no intersection, taking only the real part of the above solution (by making the $\sqrt{\;}$ equal to zero) does not result in the closest point of the ellipsoid on the line. The reason for this is complex, but it does not. A hint is that the surface described by a foxed offset from an ellipsoid is no longer an ellipsoid and thus cannot be characterized by a matrix like $\bf Q$.

It only gets you close to where you need to be, and then you must proceed with numerical-root solving of two quadric equations (fourth order). Not an easy task at all.