1
$\begingroup$

EDIT: I notice that the link is hidden, but this post is made with reference to
THIS PAPER

I'm trying to solve quite an old problem (once again) - to find the distance between a point (in 3d space) and the ellipse. - Or actually the furthest distance on said ellipse (but the algorithm is similar so...). The first step is obviously a change of coordinate system so that I have the projection of a point on the plane of the ellipse, and the middle point of the ellipse at the origin.

Once that has happend the problem is transformed from a 3d problem to a 2d problem. And I can follow a paper on it. Now I'm having a lot of trouble understand the paper. Especially why the paper takes it's long winded approach.

Then the ellipse is defined by: $$\left(\frac{x_0}{e_0}\right)^2 + \left(\frac{x_1}{e_1}\right)^2 = 1$$ And the point: $$\mathbf{Y} = (y_0, y_1)$$

Now (following also the obvious steps given at page 3 of the paper, equations 4 & 5) I can parametirize the ellipse as: $$\mathbf{X}(\theta) = (e_0 \cos(\theta), e_1 \sin(\theta)) \qquad \theta \in [0,2\pi)$$

The (squared) distance formula is obvious:

$$F(\theta) = |\mathbf{X}(\theta) - \mathbf{Y}|^2$$

Now if the distance is maximized/minimized, so is the squared distannce. And furthermore, the derivative is zero at that point (logical step to equation 5):

$$F'(\theta) = 2(\mathbf{X}(\theta) - \mathbf{Y}) \cdot \mathbf{X}'(\theta) = 0$$

Now the paper deviates from what I would take as steps. The paper goes through great lengths stating this means that distance vector must be perpendicular to the tangent of the ellipse (logical). And uses this information with the general equation of the ellipse to find ($x_0, x_1$ of the closest point). However to do, the paper does still have to take a numerical approach in the final step.

Now looking at above derivative ($F'(\theta)$), there is only a single unknown and a single equation. There are multiple roots, corresponding to (local) maxima and minima. But a simple analysis shows easily in which of the 4 quadrants one has to look, and in that quadrant only a single minimum will be found.

So writing out the derivative:

$$\begin{pmatrix}e_0 \cos(\theta) - y_0 \\ e_1 \sin(\theta) - y_1\end{pmatrix} \cdot \begin{pmatrix}- e_0 \sin(\theta) \\ e_1 \cos(\theta)\end{pmatrix} = 0$$ $$(e_0 \cos(\theta) - y_0) (- e_0 \sin(\theta)) + (e_1 \sin(\theta) - y_1) ( e_1 \cos(\theta) ) = 0$$

$$-e_0^2 \sin(\theta) \cos(\theta) + y_0 e_0 \sin(\theta) + e_1^2 \sin(\theta)\cos(\theta) - y_1 e_1 \cos(\theta) = 0$$ $$-\frac{e_0^2}{2} \sin(2 \theta) + y_0 e_0 \sin(\theta) + \frac{e_1^2}{2} \sin(2 \theta) - y_1 e_1 \cos(\theta) = 0$$

Which can be solved numerically in the quadrant where it lays. There are only 4 edge cases.

If $y_0 = y_1 = 0$ the point is the center of the ellipse and the solution is trivial.
If $y_1 = 0$ The point is at the short axis (definition), and the minimum is simply at either $\theta = 0$ or $\theta = \pi$ (depending on the sign).
If $y_0 = 0$ the point is at the long axis. If $\mathbf{Y}$ is before the focal point of the ellipse there are potentially two equal solutions, and any of those is correct. If $\mathbf{Y}$ is after the focal point there is only a single solution at either $\theta = \pm \frac{\pi}{2}$

Now this is a complete different approach that the paper I linked used. Is above method correct? Did I miss something? Why is the paper using a complete different approach? Is that faster to compute?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.