Finding the nearest/farthest point between a line and an ellipse

Question

An ellipse is given in parametric form as follows

$P(t) = C + E_1 \cos(t) + E_2 \sin(t) $

where $C, E_1, E_2 $ are $2-$ or $3-$ dimensional vectors, and $ t \in [0, 2 \pi)$. I would like to find the points on the ellipse that are nearest and farthest from a straight line given in parametric form as

$L(t) = Q_0 + t V $

with $ t \in \mathbb{R} $, and $Q_0, V$ are $2-$ or $3-$ dimensional vectors.

This problem is an exercise in constrained optimization, and that is its context.

Answer 1

The way I would probably approach this normally is

1. Write the line as $y=mx+b$
2. Write the ellipse as $Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$
3. Change coordinates to $x' = \frac{1}{\sqrt{m^2+1}}(mx + y)$ and $y' = \frac{1}{\sqrt{m^2+1}}(mx - y)$. This rotates the system so the line is horizontal and finding the nearest/farthest points becomes a simple problem of finding the highest/lowest point on the ellipse.
4. Now the line becomes simply $y' = \frac{-b}{\sqrt{m^2+1}}$ and the ellipse is $A'x'^2 + B'x'y' + C'y'^2 + D'x' + E'y' + F' = 0$.
5. The maximal and minimal values of $y'$ occur when $\frac{dy'}{dx'}=0$ so we take the implicit derivative: $$2A'x'dx' + B'y'dx' + B'x'dy' + 2C'y'dy' + D'dx' + E'dy' = 0$$ $$B'x'dy' + 2C'y'dy' + E'dy' = - 2A'x'dx' - B'y'dx' - D'dx'$$ $$\frac{dy'}{dx'} = -\frac{2A'x' + B'y'+ D'}{B'x' + 2C'y' + E'}$$
6. Set this to $0$ as mentioned before: $0 = 2A'x' + B'y'+ D'$, and solve for $x'$ to plug back into the equation for the ellipse: $x' = -\frac{B'}{2A'}y' - \frac{D'}{2A'}$ $$A'\left(-\frac{B'}{2A'}y' - \frac{D'}{2A'}\right)^2 + B'\left(-\frac{B'}{2A'}y' - \frac{D'}{2A'}\right)y' + C'y'^2 + D'\left(-\frac{B'}{2A'}y' - \frac{D'}{2A'}\right)+E'y'+F'=0$$
7. Collect this into a quadratic equation in $y'$ and solve using the quadratic formula. This will give two solutions for $y'$, which correspond to the top and bottom of the ellipse, and since rotations preserve distance, the minimal and maximal distance can be found by finding the difference between these two extremal values for $y'$ and $\frac{-b}{\sqrt{m^2+1}}$. There are three cases: this value (corresponding to the position of the line in rotated coordinates) is $\ge$ both extremal values for $y'$, in which case the min distance is the $y'$ coordinate of the line minus the maximal $y'$ value and the max distance is said $y'$ coordinate minus the minimal value; $\le$ both extremal values, in which case the opposite is true; or finally the $y'$ coordinate of the line could be between the extremal $y'$ values, meaning the line and ellipse intersect and the minimal distance is $0$ while the maximal distance is the greater absolute difference of $y'$ of the line to one of the extremal $y'$ values.

As a constrained optimization problem

Since you are expected to solve this as constrained optimization, there are two other ways you could approach it: 1) Direct optimization over the parametric forms. 2) Optimization of the distance to the line of a point whose total distance to the foci of the ellipse is constrained.

I will also go over (1) briefly. To find the minimal distance, we seek to find $$\min_\limits{t}\min_\limits{u}||P(u)-L(t)||,$$ and to find the maximal distance, we seek to find $$\min_\limits{t}\max_\limits{u}||P(u)-L(u)||.$$ The outer optimization is min in both cases because the distance from a line to a point is defined as the minimal distance from a point on the line to the point. Once again, the easiest way to solve this is by changing coordinates and then exploiting properties of the ellipse, but we will go over how to do it from the definition. It is pretty much impossible to do this without rotating though, because look at the equations:

To work from the definition:

1. Expand the definition of Euclidean distance $$\min_\limits{t}\min_\limits{u}||P(u)-L(t)||$$ $$\sqrt{\min_\limits{t}\min_\limits{u}(C_x + E_{1,x}\cos(u)+E_{2,x}\sin(u) - Q_{0,x} - tV_x)^2 + (C_y + E_{1,y}\cos(u)+E_{2,y}\sin(u) - Q_{0,y} - tV_y)^2}$$
2. We'll focus on the inner optimization: $$\min_\limits{u}(C_x - Q_{0,x} - tV_x + E_{1,x}\cos(u)+E_{2,x}\sin(u))^2 + (C_y - Q_{0,y} - tV_y + E_{1,y}\cos(u)+E_{2,y}\sin(u))^2$$
3. Take the $u$ derivative of the inside: $$(C_x - Q_{0,x} - tV_x + E_{1,x}\cos(u)+E_{2,x}\sin(u))(-E_{1,x}\sin(u)+E_{2,x}\cos(u)) + (C_y - Q_{0,y} - tV_y + E_{1,y}\cos(u)+E_{2,y}\sin(u))(-E_{1,y}\sin(u)+E_{2,y}\cos(u))=0$$

How can we solve the last part? We can solve in numerically since $u$ is restricted to one period of sine/cosine, but solving it explicitly is quite a mess, and since $t$ is a free variable in the inner optimization, we can't solve this numerically as a one dimensional optimization problem. We could solve numerically in $u$ and $t$ at the same time however.

Actually Solving

This is why rotating the problem is so important. If we rotate the parametric equations, then we end up minimizing the sum of the square distances in $x'$ and $y'$ instead of in $x$ and $y$.

We use the same formulas for $x'$ and $y'$ as in the first approach, but to be explicit, $m=\frac{V_y}{V_x}$. Components like $E_{1,x'}$ can be found by projecting $E_1$ onto the unit vector in the $x'$ direction, in other words, taking the dot product.

Then, for any $u$, there will be some $t$ such that $L(t)$ and $P(u)$ have the same $x'$ coordinate, so the outer optimization will always be able to set the $x'$ distance to 0. Additionally, the $y'$ distance is independent of $t$, so we are now free to minimize only the $y'$ distance in the inner optimization.

This is fantastic because it reduces it to $C_{y'}-Q_{0,y'}+E_{1,y'}\cos(u)+E_{2,y'}\sin(u)$ ($V_{y'}$ is 0 by definition).

This is easy to solve using the identity $a\cos(x)+b\sin(x) = c\cos(x+\phi)$ where $c=sgn(a)\sqrt{a^2+b^2}$ and $\phi=\arctan{-\frac{b}{a}}$ (this is pretty easy to prove from the fact that a linear combination of sine and cosine with the same period is just a scaled and shifted cosine with the same period). For us, only the amplitude matters because it gives us the extremal $y'$ distances as $$C_{y'}-Q_{0,y'} \pm \sqrt{E_{1,y'}^2+E_{2,y'}^2}$$

Answer 2

Assuming $C, E_1, E_2, V$ are two dimensional vectors the near and far points of the elipse from the line will have tangent vectors parallel to $V=(v_1,v_2)$ and orthogonal to $V^\perp=(-v_2,v_1)$. So

$$ V^\perp\cdot\frac{d}{dt}P(t)=0 $$

Solving the equation gives

$$ \tan(t)=\frac{V^\perp\cdot E_2}{V^\perp\cdot E_1} $$

There will be two solutions for $t\in[0,2\pi)$ separated by $\pi$ radians.

Substituting into $P(t)$ will give the near and far points which may be distinguished geometrically.