4
$\begingroup$

The $2D$ case is not a problem:

$$\ P(t) =(x,y)= s + t v = <s_x+tv_x, s_y+tv_y> $$

$$\ F(x,y) = (\frac{x}{a})^2 +(\frac{y}{b})^2 -1 = 0 $$ $$ \nabla F(x,y).v =0 $$

Finally solve for $y$ in terms of $x$, and plug into ellipse equation, $F(x,y)$.

For the $3D$ case, where I have $P(t)= (x,y,z)$ and am now using a $3D$ ellipsoid, the previous method does not work. I am left with more variables than equations. Any advice is appreciated.
$$\ P(t) =(x,y,z)= s + t v = <s_x+tv_x, s_y+tv_y, s_z+tv_z> $$

$$\ F(x,y,z) = (\frac{x}{a})^2 +(\frac{y}{b})^2 +(\frac{z}{c})^2-1 = 0 $$


EDIT: Thank you for the feedback.

@ja72: Your solution has been tested and works.

@Semiclassical: I have been looking at Lagrange Multipliers and have an idea for how to solve my problem. The steps below have been tested and work.

(1) Given a line defined by two points $\vec{x1}$ and $\vec{x2}$, $\vec{r}$ , I know the equation for the minimum distance between $\vec{r}$ and a point $\vec{x0}$ $$\ d(x_0,y_0,z_0) = \frac{|(\vec{x0}-\vec{x1})X(\vec{x0}-\vec{x2})|}{|\vec{x2}-\vec{x1}|} $$

(2) Given my constraint that the point $\vec{x0}$ must reside on the ellipse $$\ F(x_0,y_0,z_0) = (\frac{x_0}{a})^2 +(\frac{y_0}{b})^2 +(\frac{z_0}{c})^2-1 = 0 $$

(3) The Lagrange problem is stated below and is solved by following (http://tutorial.math.lamar.edu/Classes/CalcIII/LagrangeMultipliers.aspx):

Find the minimum of $\ d(x_0,y_0,z_0) $ subject to the constraint $\ F(x_0,y_0,z_0) $. enter image description here

$\endgroup$
6
  • $\begingroup$ What are the equations you have for the 3D case? $\endgroup$
    – John
    Commented Aug 12, 2014 at 18:11
  • $\begingroup$ Lagrangian multipliers are probably what you should use. They have the distinct advantage of dealing with all coordinates symmetrically, which is great for dimensions more than two. $\endgroup$ Commented Aug 12, 2014 at 18:25
  • $\begingroup$ I am curious, have you used homogeneous coordinates in the past, or is this your first exposure? There is a lot to explore there ... $\endgroup$ Commented Aug 14, 2014 at 14:06
  • $\begingroup$ Being a new user I cannot comment, so I will ask a follow up question to JA72's answer. Why the assumption that the closest point resides on the plane defined by the line and the origin? Unless I misunderstood, this does not seem to hold as far as I can tell. It will hold for a sphere, but not for an ellipsoid. $\endgroup$
    – user116697
    Commented Apr 3, 2021 at 19:33
  • $\begingroup$ This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review $\endgroup$
    – Sera Gunn
    Commented Apr 3, 2021 at 23:04

5 Answers 5

5
$\begingroup$
  1. A 3D line is defined with 6 Plücker coordinates $L=(\vec{e}, \vec{p}\times\vec{e})$ where $\vec{e}$ is the direction of the line, and $\vec{p}$ is any point along the line.
  2. Lemma, The point lies on the plane defined by the origin and the line.
  3. The ellipsoid is represented by the 4×4 matrix $$C = \begin{pmatrix} 1/a^2 & 0 & 0 & 0 \\ 0 & 1/b^2 & 0 & 0 \\ 0 & 0 & 1/c^2 & 0 \\ 0 & 0 & 0 & -1 \end{pmatrix}$$ and a point by the homogeneous coordinates $P= (\alpha x,\alpha y,\alpha z,\alpha)$ such that $P^\top C P =0$ gives the familiar equation $\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0$
  4. A 3D plane tangent to the ellipsoid through the closest point is perpendicular to the plane defined in (2) above. To find the normal of this plane, we use the vector describing the point on the line closest to the origin. This is given by $$\boxed{\vec{r} = -\dfrac{\vec{e} \times (\vec{e} \times \vec{p})}{|\vec{e}|^2} = (i,j,k)}$$ The homogeneous coordinates of this plane are $W=(i,j,k,-\ell)$ with normal direction $$\vec{n}=\frac{\vec{r}}{|\vec{r}|} = \frac{(i,j,k)}{\sqrt{i^2+j^2+k^2}}$$ and unknown distance from the origin $$d=\frac{\ell}{|\vec{r}|} = \frac{\ell}{\sqrt{i^2+j^2+k^2}}$$
  5. To make sure the plane is tangent to the ellipsoid we set $W^\top C^{-1} W =0$ and solve for $$\ell =\sqrt{a^2 i^2 + b^2 j^2 + c^2 k^2}$$.
  6. The point on the ellipse where the tangent plane touches (and closest to line) is defined in homogeneous coordinates by $P=C^{-1} W$ $$ P=(\alpha x, \alpha y, \alpha z, \alpha) = (a^2 i,b^2 j,c^2 k,-\ell) $$ $$ \boxed{ \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \dfrac{1}{\sqrt{a^2 i^2+b^2 j^2+c^2 k^2}} \begin{pmatrix} a^2 i \\ b^2 j \\ c^2 k \end{pmatrix} } $$

Appendix

The 6 Plüker coordinates of a line through points $\vec{r}_1$ and $\vec{r}_2$ are $$ L = (\vec{r}_2-\vec{r}_1, \, \vec{r}_1 \times \vec{r}_2 ) $$

$\endgroup$
4
  • $\begingroup$ Why do this problem with vector algebra when projective geometry and homogeneous coordinates are so much more elegant. $\endgroup$ Commented Aug 12, 2014 at 19:49
  • $\begingroup$ If you define the line in 2D then the result will also be in 2D and you can check it against you existing 2D solution. $\endgroup$ Commented Aug 13, 2014 at 5:30
  • $\begingroup$ How would you modify this to find the tangent line that goes through a point, rather than the closest point to a line? I believe your technique can be used to answer my question here: math.stackexchange.com/questions/1780342/… $\endgroup$
    – gct
    Commented May 11, 2016 at 21:21
  • $\begingroup$ See my post "How to test a proposed solution" for a disproof of this solution. $\endgroup$ Commented Feb 8 at 16:03
1
$\begingroup$

You have the ellipsoid

$ r^T Q r = 1 $

where $ Q = \begin{bmatrix} \dfrac{1}{a^2} && 0 && 0 \\ 0 && \dfrac{1}{b^2} && 0 \\ 0 && 0 && \dfrac{1}{c^2} \end{bmatrix}$

And the line $ p(t) = s + t v $

Now, pick a point $r_1$ on the ellipsoid, and a point $p_1$ on the line, then the displacement vector between them is

$ w = r_1 - p_1 = r_1 - (s + t_1 v ) $

From the well-known properties of the minimum distance, we know that if the pair $r_1$ and $p_1$ form a shortest distance, then their difference (vector $w$) must be perpendicular to the line direction $ v$ and at the same time be along the gradient vector of the ellipsoid at $r_1$.

So the first equation is that

$ v^T ( r_1 - s - t_1 v ) = 0 \tag{1}$

This equation enables us to find $t_1$ in terms of $r_1$

$ t_1 = \dfrac{1}{v^T v} ( v^T (r_1 - s) ) \tag{2}$

And the second condition is that

$ (Q r_1) \times ( r_1 - s - t_1 v) = 0 \tag{3} $

Plug in $t_1$ from $(2)$

$ (Q r_1) \times \bigg( I - \dfrac{v v^T}{v^T v} \bigg) (r_1 - s) = 0 \tag{4} $

Equation $(4)$ is a vector equation, that has three components.

Now recall that if $V$ and $W$ are two vectors, then

$ V \times W = (V_2 W_3 - V_3 W_2 , V_3 W_1 - V_1 W_3 , V_1 W_2 - V_2 W_1 )$

Since $V_i = e_i^T V$ , and $W_j = e_j^T W $, then

$ V \times W = ( V^T (e_2 e_3^T - e_3 e_2^T) W , V^T (e_3 e_1^T - e_1 e_3^T) W , V^T ( e_1 e_2^T - e_2 e_1^T ) W ) \tag{5}$

Define

$E_1 = e_2 e_3^T - e_3 e_2^T $

$E_2 = e_2 e_3^T - e_3 e_2^T $

$ E_3 = e_1 e_2^T - e_2 e_1^T $

Applying $(5)$ to $(4)$,

$r_1^T Q E_1 P (r_1 - s) = 0 \tag{6a}$

$r_1^T Q E_2 P(r_1 - s) = 0 \tag{6b}$

$r_1^T Q E_3 P (r_1 - s) = 0 \tag{6c}$

where $P = I - \dfrac{v v^T}{v^T v} $

only two of these three equations is needed, the third one is dependent.

So taking any two of equations $(6)$, and adding to this system the equation of the ellipsoid, which is

$ r_1^T Q r_1 = 1 \tag{7} $

Gives a system of three quadratic equations in $r_1$ which can be solved using numerical methods. For example, one can write script in Mathematica language or SAGE language to find all the possible solutions $r_1$.

I've worked an example on this SAGE page.

where $ a= 2 , b = 3, c = 4 , s = [11, 13, 17] , v = [1, 1, -2] $

The SAGE script uses Lagrange multiplier method to find the critical points. The results over $\mathbb{R}$ are

$ (x,y,z, t, \lambda) = (-0.65415929, -1.80604058, -2.91368788142, 2.2278625954, -84.88465499485) $

This corresponds to the maximum (perpendicular) distance between a point on the ellipsoid and a point on the line, with a distance of $26.86657783$

and

$ (x,y, z, t, \lambda) = (0.706861036285, 1.7273073989, 2.949106449, 1.08932584269, 64.411330049 ) $

which corresponds to the minimum perpendicular distance between a point on the ellipsoid and a point on the line, with the distance being $20.57498806 $. Since we're seeking the closest points then this our closest distance.

$\endgroup$
0
$\begingroup$

This equation

$$\nabla F(x,y,z) \cdot \vec{v} = 0$$

limits you to a locus of points on the surface of the ellipsoid, which isn't enough.

You can visualize this by a simple case. Take the line to be parallel to the major axis of the ellipsoid, but displaced from the ellipsoid. Then the gradient equation above will give you that the point lies somewhere on the circle that goes around the ellipsoid midway between the two ends.

Once you have this equation, then you need to determine the point from there that is minimum distance to the line.

$\endgroup$
0
$\begingroup$

You have another condition that the gradient, when extended to a line, must intersect the given line. In other words, there must exist an $\alpha$ and $t$ such that $P(t) = \alpha \nabla F$.

$\endgroup$
0
$\begingroup$

Victor's remark needs one more vector because $\nabla F$ only gives the direction of the gradient, but its starting point is needed too: $P(t) = (x,y,z) + \alpha \nabla F(x,y,z)$. This, together with John's observation, gives us four equations for five unknowns: $(x,y,z,\alpha,t)$. So one more condition is necessary: $F(x,y,z)=0$.

$\endgroup$
1
  • $\begingroup$ To find the point on the line nearest the ellipsoid, you can start with the solution provided by @ja72, which doesn't require solving any nonlinear equations, and then solve $P(t)=(x,y,z)+\alpha\nabla F(x,y,z)$ for $t$ and $\alpha$ ... but this is three equations for the two unknowns. If you pick any of the three sets of two equations, do you always get the same results? $\endgroup$
    – Van Snyder
    Commented May 12, 2016 at 19:55

You must log in to answer this question.

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