0
$\begingroup$

Possible Duplicate:
Calculating Distance of a Point from an Ellipse Border

Given a point $A = (x_1, y_1)$ and a $2$D ellipse, how could we find a point $B = (x_2, y_2)$ on the ellipse so that it has the shortest distance between point $A$ and $B$?

The point $A$ can be anywhere on the same plane of the ellipse. If possible, please list the final expression of the point $B.$

  • 0
    @Jin: You have not told us what are the given data about the ellipse, e.g., whether its axes are parallel to the coordinate axes or not. Maybe the ellipse is given by $5$ of its points; then the solution of your problem looks very unintuitive.2012-10-22

2 Answers 2

2

An arbitrary ellipse can be parameterised as $x=h+a\cos t,\, y=k+b\cos t$ $(0\leq t\leq 2\pi)$, which is an ellipse centred at $(h,k)$, with axis lengths $a$ and $b$.

Minimising the square of the distance is an equivalent problem to minimising the distance.

Approach 1:

The point $(x_2,y_2)$ lies on the above parametised ellipse.

Then, $f=(x_1-h-a\cos t)^2 +(x_2-k-b\sin t)$ is the distance to any point on the ellipse.

As $d$ is a simple function of $t$ only, the value of $t$ which is minimised when $\dfrac{d f}{d t}=0$.

Approach 2:

The point $p_1=(x_1,y_1)$ can be written as $p_1=p_2+\lambda n$ where $p_2=(x_2,y_2)$ is the point on the ellipse and $n$ is the vector normal to the ellipse. Using the above parameterisation for the ellipse, you obtain the system of nonlinear equations $\begin{bmatrix}x_1\\y_1\end{bmatrix}=\begin{bmatrix}h+a\cos t\\k+b\sin t\end{bmatrix}+\lambda \begin{bmatrix}b\cos t\\a\sin t\end{bmatrix},$ which has to be solved for $t$ and $\lambda$.

Approach 3:

A third way to formulate this problem is as a constrained optimisation problem, so that this is formulated as $\min\limits_{x_1,x_2} f = (x_1-x_2)^2+(y_1-y_2)^2$ subject to $\frac{(x_2-h)^2}{a^2}+\frac{(y_2-k)^2}{b^2}-1=0.$

This can be solved using lagrange multipliers to give $L(x_1,x_2,\lambda)=(x_1-x_2)^2+(y_1-y_2)^2+\lambda\left(\frac{(x_2-h)^2}{a^2}+\frac{(y_2-k)^2}{b^2}-1\right).$ The optimal solution can be found by solving the system of equations $\frac{d L}{d x_1}=0,\,\frac{d L}{d x_2}=0,\,\frac{d L}{d \lambda}=0.$

  • 0
    @Daryl - I have set this up and obtained equations $2(p_x-q_x) = \lambda (2Ap_x + Bp_y + D), 2(p_y-q_y) = \lambda (Bp_x + 2Cp_y + E), Ap_x^2 + Bp_x p_y + Cp_y^2 + Dp_x + Ep_y + F = 0$ where $(p_x,p_y)$ is a point on the ellipse and $(q_x,q_y)$ is the query point. I have tried solving these using Sage and Matlab Symbolic Toolbox for $p_x$, $p_y$, and $\lambda$, and the expressions are either completely out of control or the system cannot find a solution. Is there a way to actually write the solution in closed form?2013-03-18
1

Not the easiest. Let the unknown point $B$ be $(x, y).$ $B$ is on the ellipse so $(x/a)^2 + (y/b)^2 = 1,$ i.e. $y = \frac{b}{a}\sqrt{a^2 - x^2}.$ Hence the squared distance between $A = (x_1, y_1)$ and $B$ is $\begin{eqnarray} d & = & (x-x_1)^2 + (y -y_1)^2 \\ & = & (x-x_1)^2 + \Big(\frac{b}{a}\sqrt{a^2 - x^2} - y_1 \Big)^2. \end{eqnarray}$ That's a function in $1$ variable, namely $x$, which you can minimize using calculus.

  • 1
    The problem is that $y=\pm \frac{b}{a}\sqrt{a^2-x^2}$. So if the point $(x_1,y_1)$ is in the bottom half of the domain (y_1<0), you won't find the shortest distance as you are neglecting the bottom half of the ellipse.2012-08-22