Distance between two axis-parallel ellipses

Question

I have two axis parallel ellipses. I want to find the gap (minimum distance) between the two. The ellipses are defined as :

$$\frac{(x-x_1)^2}{a_1^2} + \frac{(y-y_1)^2}{b_1^2} = 1$$ $$\frac{(x-x_2)^2}{a_2^2} + \frac{(y-y_2)^2}{b_2^2} = 1$$

I am not looking for a closed-form equation. I will be using this in a computer program and it is perfectly OK to loop through a set of values and compute the min or max.

My reasoning so far is:

1. The distance between circles is $|c_1 - c_2| - (r_1 + r_2)$ i.e. the norm of the difference between the two centers subtracted by the sum of the radiuses.
2. An axis parallel ellipse is a circle scaled on the axis.
3. But each of the two ellipses would be using a different scale.
4. I am wondering if we can translate the formula (1) to the ellipse case somehow. The point $c_1$ will be origin going through a transform $T_1$. The point $c_2$ will be the origin transformed by $T_2$. How do we calculate the "distance" between these two points. What can we say about $r_1$ and $r_2$.

Answer 1

You define the ellipses on the Cartesian form : $$\text{Ellipse 1 : }\quad \frac{x-x_1)^2}{a_1^2} + \frac{(y-y_1)^2}{b_1^2} = 1 $$ $$\text{Ellipse 2: }\quad \frac{(X-x_2)^2}{a_2^2} + \frac{(Y-y_2)^2}{b_2^2} = 1$$ But I think that for algoritmic process it is easier to use the equivalent parametric polar form : $$\text{Ellipse 1 :}\begin{cases} x=x_1+\frac{\cos(\theta)}{\sqrt{\frac{\cos^2(\theta)}{a_1^2}+\frac{\sin^2(\theta)}{b_1^2}}}\\ y=y_1+\frac{\sin(\theta)}{\sqrt{\frac{\cos^2(\theta)}{a_1^2}+\frac{\sin^2(\theta)}{b_1^2}}} \end{cases}\quad \text{Ellipse 2 :}\begin{cases} X=x_2+\frac{\cos(\Theta)}{\sqrt{\frac{\cos^2(\Theta)}{a_2^2}+\frac{\sin^2(\Theta)}{b_2^2}}}\\ Y=y_2+\frac{\sin(\Theta)}{\sqrt{\frac{\cos^2(\Theta)}{a_2^2}+\frac{\sin^2(\Theta)}{b_2^2}}} \end{cases}$$ Consider successive values of $\theta_k$ and $\Theta_k$ each varying independently from $0$ to $2\pi$.

Compute the corresponding $(x_k,y_k)$ and $(X_k,Y_k)$ with the above formulas.

Compute the distance between the two points : $$d_k=\sqrt{(X_k-x_k)^2+(Y_k-y_k)^2}$$
So you can find $(d_k)_{minimum}$ which gives an approximate value of the distance between the ellipses.

If the result is close to $0$ this means that the ellipses intersect. This doesn't mean that they are necessarily tangent.

Answer 2

I messed up the calculation. Another try which should give you an exact outcome:

The distance between two ellipses is so that the tangents at both ellipses are parallel. So you could calculate that exactly as follows:

1. Express the tangent and outer normal function at each point of the ellipse (I don't know how easy or hard that is)
2. Then look for which points the outer normal intersects with the other ellipse. One could probably calculate the general formula for their intersection point.
3. Calculate the tangent line or at least the slope of the other ellipse in that intersection point.
4. Calculate for which values the two slopes of the tangent line are equal. That are the nearest points on those ellipses.
5. The distance can then be easily calculated by calculating the distance between those two points.

However, I don't know how complicated it is to calculate this closed form of solution. Advantage of this method is the exactness and - given a final calculated formula - it doesn't require much calculation resources.

I don't have the time to calculate all this, maybe someone else can do this - if it helps the OP to solve his problem.

Answer 3

It is a bit more difficult than the formula for circles.

You can do the following (which can also easily be implemented into an algorithm):

1. Find the center points $c_1,c_2$ of each ellipse
2. Define the line segment between those center points
3. Find the intersection of this segment with each ellipse, denoted by $p_1$ and $p_2$
4. The distance you're looking for is $|p_1-p_2|$

This can be solved in closed form, here the important steps to get the algorithm running:

Center of ellipses are $c_1 = (x_1,y_1)$ and $c_2=(x_2,y_2)$, therefore the line segment between those points is given as

\begin{align} y & = \frac{y_2-y_1}{x_2-x_1} (x-x_1) + y_1 \\ &=\frac{y_2-y_1}{x_2-x_1} (x-x_2) + y_2 \end{align}

Let us now calculate the intersection with the first ellipse $E_1: \frac{(x-x_1)^2}{a_1^2} +\frac{(y-y_1)^2}{b_1^2}=1$ by just inserting the formula for $y$:

\begin{align} \frac{(x-x_1)^2}{a_1^2} +\frac{(y-y_1)^2}{b_1^2}&=1 \\ \frac{(x-x_1)^2}{a_1^2} +\frac{(\frac{y_2-y_1}{x_2-x_1} (x-x_1) + y_1-y_1)^2}{b_1^2}&= 1 \\ \frac{(x-x_1)^2}{a_1^2} +\frac{(y_2-y_1)^2}{(x_2-x_1)^2b_1^2}(x-x_1)^2&= 1 \\ \left(\frac{1}{a_1^2} +\frac{(y_2-y_1)^2}{(x_2-x_1)^2b_1^2}\right)(x-x_1)^2&= 1 \\ x^{(1)}_{1,2} = \pm \left(\frac{1}{a_1^2} +\frac{(y_2-y_1)^2}{(x_2-x_1)^2b_1^2}\right)^{-\frac 12}+x_1 \end{align} Remark: $x^{(1)}_{1/2}$ represents the two solutions (subscript $1,2$) of the intersection of the first ellipse with the connection line.

Analogously by entering the other formula for $y$ in the second equation we get $$ x^{(2)}_{1,2} = \pm \left(\frac{1}{a_2^2} +\frac{(y_2-y_1)^2}{(x_2-x_1)^2b_2^2}\right)^{-\frac 12}+x_2 $$

Because the line intersects with each ellipse at two points we have two different solutions. To find out the correct solution we can make a case-by-case analysis:

If $x_1 \leq x_2$: The $x$-value of the intersection must be inside the interval $[x_1,x_2]$, therefore choose $x^{(1)}$ and $x^{(2)}$ s.t. $x_1 \leq x^{(1)} \leq x^{(2)} \leq x_2$.

If $x_1 > x_2$: Change the order and choose those solutions s.t. $x_1 > x^{(1)} > x^{(2)} > x_2$.

The corresponding $y$ values can be calculated using the formula on top of this answer.

One could calculate the difference explicitly, but that requires more computing and simplifying terms. As you only need an algorithmic approach I think that this is the way to go.