15
$\begingroup$

I'm thinking about using oriented ellipses to represent curves (dents/bumps etc.) in my physics engine, and have a few questions about working with them:

  1. What methods are there to finding the minimum distance between a point and an ellipse? I need methods of varying cost (in terms of # of calculations) for different parts of my engine.

    • I'm currently aware of two methods to testing if a point is inside/outside an ellipse.

      1. In the first you plug in the point coordinates into the equation (x/a)^2 + (y/b)^2 and seeing if it's >, <, or = to 1 (does the output -1 give the min. distance to the ellipse border?)
      2. In the second you translate the point to the ellipse's coordinates and horizontally/vertically stretch both the ellipse and point in order to turn the ellipse into a circle. (I rarely see this method used... any reason I should be aware of?)
  2. How do you test the distance between two ellipses? I figure you could combine the two methods above by transforming both ellipses in a way that makes one a circle, then test the distance from the center of the circle ellipse to the regular ellipse's edge, and finally compare that distance to the radius of the circle ellipse.

1 Answers 1

13

Source: Exercise 2.3.18 (p.54) from Convex functions: constructions, characterizations and counterexamples, J.M. Borwein & J.D. Vanderwerff (2010).

Consider $E:=\{(x,y):x^2/a^2+y^2/b^2=1\}$ in standard form. Show that the best approximation is: $$P_E\,(u,v)=\left(\frac{a^2u}{a^2-t},\frac{b^2v}{b^2-t}\right)$$ where $t$ solves $\frac{a^2u^2}{(a^2-t)^2}+\frac{b^2v^2}{(b^2-t)^2}=1$.

  • 6
    A little explanation would be nice.... What's the function PE(u,v) represent, and what's 'u', 'v' and 't' represent?2011-12-13
  • 2
    @Griffin $P_E(u,v)$ denotes the projection of the point $(u,v)$ onto the ellipse $E$, where $u$ and $v$ are the $x$ and $y$ coordinates of your point. $P_E(u,v)$ will then give you the nearest point on the ellipse which will then allow you to find the distance between the two. As for the variable $t$ it solves the equation in my answer. I believe it can be interpreted as the *Lagrangian multiplier* for the problem: $\min_{(z_1,z_2)} (u-z_1)^2 + (v-z_2)^2$ subject to $z_1^2/a^2+z_2^2/b^2=1$. Its my understanding that there no simple 'formula' for $t$. Hope that helps :)2011-12-13
  • 1
    Great! that clears a lot up, but I have only a few more questions: The quote says this is the "best approximation;" so how accurate is the equation exactly? Also, do you know of any less expensive (in terms of # of calculations) formulas that would be acceptable for use in a physics engine?2011-12-13
  • 1
    The use of the phrase 'best approximation', in this case, does not refer an 'approximate answer' in the sense of not representing something exactly, but still being close enough to be useful. You could replace 'best approximation' with 'nearest point' in the quotation without changing meaning. The equation I have given, gives exactly the nearest point. As for a less expensive method, I'm not sure how simple you need to use your physics engine, but you could convert $\frac{a^2u^2}{(a^2-t)^2}+\frac{b^2v^2}{(b^2-t)^2}=1$ to a polynomial by multiplying by $(a^2-t)^2(b^2-t)^2$ and expanding.2011-12-13
  • 0
    Thanks for the helpfulness, let me know if you can think of any other less-precise, faster methods for approximating the distances!2011-12-13
  • 0
    The exercise does not say which of the roots should be used (there may be four real roots, corresponding to four different points on the ellipse). It seems that $t$ should be the smallest root of the equation. [Discussed here](http://math.stackexchange.com/questions/315287).2013-03-07
  • 0
    What do $a$ and $b$ represent? Are they the semi major and minor axis?2014-10-23
  • 0
    @matt Does the point (u,v) need to lie within an ellipse?2015-07-23