Find the minimum distance to move an ellipse to be inside another ellipse?

Question

For the problem of ellipse intersection,

I would like to know an accurate "general, including the cases of two non intersected ellipses, and non aligned ellipses" method to calculate the minimum Euclidean distance to translate an ellipse to be inside another ellipse, so that:

• I have an ellipse "A" and "B"
• I want ellipse "A" to be inside ellipse "B"

Answer 1

Write the stationary ellipse $B$ in implicit form: $V(x,y) = 1$ where $V$ is a quadratic polynomial in $x,y$. Write the ellipse $A$ in parametric form: $x = f(\theta)$, $y = g(\theta)$, $0 \le \theta \le 2\pi$ where $f$ and $g$ are linear combinations of $\cos(\theta)$, $\sin(\theta)$ and $1$. Ellipse $A$ translated by $(s,t)$ is $x = s + f(\theta)$, $y = t + g(\theta)$. To have the translated $A$ inside $B$, you need $V(s+f(\theta), t+g(\theta)) \le 1$ for all $\theta \in [0,2\pi]$. The optimal solution will have $$V(s+f(\theta_0), t + g(\theta_0)) = 1$$ for (at least) one $ \theta_0$, with $$\left.\dfrac{\partial}{\partial \theta} V(s+f(\theta), t+g(\theta))\right|_{\theta = \theta_0} = 0$$ Eliminating $\theta_0$ from these two equations will give you a polynomial equation $P(s,t) = 0$. Then you want to minimize $s^2 + t^2$ subject to that. Use a Lagrange multiplier.

Caution: $P(s,t) = 0$ gives you $(s,t)$ where the two ellipses are tangent. Not all of these solutions will have the translate of $A$ inside $B$, so you need to examine each local extremum found in the last paragraph. You also need to look at self-intersections of $P(s,t)=0$, where the two ellipses are tangent at two (or more) points.

Unfortunately, this approach will require high-precision solving of some rather nasty high-degree polynomials. I don't see any way around that.

For example, I tried the ellipses $x^2/4 + y^2 = 1$ (red) and $x = 2+\cos(\theta)/2, 2 - \cos(\theta)/2 - \sin(\theta)/4$ (blue).

The polynomial $P(s,t)$ turns out to be

$$ 400\,{s}^{8}+1280\,{s}^{7}t+4864\,{s}^{6}{t}^{2}+11264\,{s}^{5}{t}^{3} +19968\,{s}^{4}{t}^{4}+28672\,{s}^{3}{t}^{5}+28672\,{s}^{2}{t}^{6}+ 16384\,s{t}^{7}+4096\,{t}^{8}+8960\,{s}^{7}+37376\,{s}^{6}t+125952\,{s }^{5}{t}^{2}+272384\,{s}^{4}{t}^{3}+446464\,{s}^{3}{t}^{4}+516096\,{s} ^{2}{t}^{5}+344064\,s{t}^{6}+98304\,{t}^{7}+94072\,{s}^{6}+465472\,{s} ^{5}t+1400096\,{s}^{4}{t}^{2}+2781696\,{s}^{3}{t}^{3}+3785344\,{s}^{2} {t}^{4}+2958336\,s{t}^{5}+988672\,{t}^{6}+624160\,{s}^{5}+3222272\,{s} ^{4}t+8672512\,{s}^{3}{t}^{2}+14565376\,{s}^{2}{t}^{3}+13627904\,s{t}^ {4}+5394432\,{t}^{5}+2822609\,{s}^{4}+13608256\,{s}^{3}t+31176712\,{s} ^{2}{t}^{2}+36580608\,s{t}^{3}+17556240\,{t}^{4}+8565512\,{s}^{3}+ 35372960\,{s}^{2}t+57681440\,s{t}^{2}+35238528\,{t}^{3}+16651594\,{s}^ {2}+49842824\,st+43031000\,{t}^{2}+18303224\,s+29487984\,t+8741466 $$

Here is a plot of $P(s,t) = 0$:

The outer curve has the two ellipses tangent externally. The closest point to the origin on the inner curve is the cusp at approximately $$s = -.51323143831669984893354538119451, t = -1.4084700967403685126969584735633$$

But that doesn't work: it seems to correspond to a third-order contact, and the blue ellipse is not inside the red one:

The next point to try is the self-intersection at approximately

$$s = -.548586303703105857310127208690, t = -1.69940238118988100188408119644$$

This one does work: the two ellipses are internally tangent at two points.

Rather close to that point, and slightly closer to the origin, there is a local minimum of $s^2 + t^2$ on the curve, approximately

$$ s= -.53385128947026720961128611, t =-1.70397049534824072399428450222 $$

The picture here is very similar to the previous one, but it turns out that the blue ellipse sticks out of the red one slightly in this case: the maximum value of $V$ on the blue ellipse is about $1.0165$.

Answer 2

What if you would take a point $x\in B$. Then consider a line perpendicular to your ellipse $B$, through $x$. Now if this line intersects $A$ in a point $y_1$ and possibly $y_2$, where we suppose $y_1$ and $y_2$ to be outside $B$. Take then $d_x = max(d(x,y_1),d(x,y_2))$, where $d(x,y)$ is the distance between $x$ and $y$. Then we do this for all $x\in B$ and take the maximum for all these values. This should be your desired answer.

Answer 3

Here is a first step.

• For each ellipse defined by the coefficients ABCDEF such that $$ A x^2 + B y^2 + C x y + D x + E y + F = 0 $$ the tangent line with normal vector $n=(\cos \psi,\sin \psi)$ is given by the equation $$ \begin{align} & \left(\frac{x}{2 R} + \frac{R ( 2 B D - C E)}{2} \right) \cos\psi + \left( \frac{y}{2 R} + \frac{R (2 A E - C D)}{2} \right) \sin \psi + K = 0 \\ R & = \frac{1}{\sqrt{4 A B - C^2}} \\ K & = R \sqrt{ A (4 B F-E^2) - B D^2 - C (C F -D E)} \sqrt{ (A-B)\cos^2\psi + C \sin\psi \cos\psi-A} \end{align}$$

Find the direction of minimum distance $b$ by measuring the distance between a line on the first ellipse oriented by $\psi$ and $\psi+\pi$ on the other ellipse. The orientation that maximizes the distance $b$ is the direction you want to translate the ellipse by.

The find the distance $d$ for inner tangency use the second line also with orientation $\psi$ and find the distance to the first line. Both lines would have normal vectors in the same direction.

Here is a picture of the process

Answer 4

Looking at Robert Israel's answer, it seems there will not be an "exact" solution, but that some sort of numerical methods must be used.

It is also clear that the answer will the the distance of a translation that makes ellipse $A$ tangent to ellipse $B$, with both ellipses curved in the same direction at the point of tangency.

Consider an ellipse in a Cartesian plane such that the center of the ellipse is at coordinates $(h,k)$, the major axis of the ellipse is rotated at an angle $\alpha$ counterclockwise from the $x$-axis, the length of the major radius is $a$, and the length of the minor radius is $b$, where $h$, $k$, $\alpha$, $a$, and $b$ are all known. Given an angle $\phi$, let us find the coordinates of a point $(x,y)$ on the ellipse such that an image of the $x$-axis, turned by angle $\phi$ counterclockwise about some point, is perpendicular to the ellipse at $(x,y)$ and is directed toward the outside of the ellipse at that point. In other words, find $(x,y)$ such that the outward normal vector of the ellipse at $(x,y)$ has direction angle $\phi$.

Any point on the ellipse can be expressed in the form $$ \newcommand{hata}{\hat{\mathbf a}} \newcommand{hatb}{\hat{\mathbf b}} (x,y) = (h,k) + (a \cos\theta) \hata + (b \sin\theta) \hatb, $$ where $\hata = (\cos\alpha, \sin\alpha)$ is a unit vector rotated at angle $\alpha$ counterclockwise from the positive $x$ direction (so $\hata$ is in the direction of the ellipse's major axis) and $\hatb = (-\sin\alpha, \cos\alpha)$ is at an angle $\pi/2$ counterclockwise from $\hata$ (so $\hatb$ is in the direction of the ellipse's minor axis). If the outward normal vector at that point has direction angle $\phi$, then $$ \tan \theta = \frac ba \tan(\phi - \alpha). $$ Given an angle $\phi$ we can then solve for $\theta$, choosing the value of $\theta$ in the same quadrant as $\phi - \alpha$, and use this value of $\theta$ to find the point $(x,y)$.

Now given the center $(h_A,k_A)$, major axis angle $\alpha_A$, semi-major axis $a_A$, and semi-minor axis $b_A$ of ellipse $A$, and $(h_B,k_B)$, $\alpha_B$, $a_B$, and $b_B$ the respective properties of ellipse $B$, for a given angle $\phi$ we can find points $(x_A,y_A)$ and $(x_B,y_B)$ on the respective ellipses that have outward normal vectors at angle $\phi$. The distance between those two points is therefore a function of $\phi$, which we'll write as $$ f(\phi) = \sqrt{(x_A - x_B)^2 - (y_A - y_B)^2}. $$

We can use numeric methods to find a minimum of this function over the domain $\phi \in [0,2\pi]$ (though this is not a simple task, as there may be multiple local minima). We then test to see whether ellipse $A$ is completely inside ellipse $B$ when $A$ is translated by the vector $(x_B - x_A, y_B - y_A)$. One way to test this is to find the polynomial $P$ such that $P(x,y) = 1$ is an equation of ellipse $B$, plug the coordinates of a point $(x_A', y_A')$ of the appropriately translated image of ellipse $A$ parameterized by $\theta$ into the polynomial $P$, and maximize $P(x_A'(\theta), y_A'(\theta))$ over $\theta \in [0,2\pi]$. If $\max(P(x_A'(\theta), y_A'(\theta))) \leq 1$, then $\min(f(\phi))$ is the answer.

If $\max(P(x_A'(\theta), y_A'(\theta))) > 1$, we find the nearest value of $\phi$, call it $\phi_1$, such that $\max(P(x_A'(\theta), y_A'(\theta))) = 1$ when we set $\phi = \phi_1$. The corresponding translation of ellipse $A$ makes it tangent to $B$ at two points, and $f(\phi_1)$ is the distance that ellipse $A$ must be moved. (I believe this corresponds to using the self-intersection of the inner curve in Robert Israel's solution. In fact, looking at that solution is the only thing that gives me any confidence that this one will work in general.)