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.

| cite | improve this question | |
$\endgroup$
14
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 7
    $\begingroup$ A little explanation would be nice.... What's the function PE(u,v) represent, and what's 'u', 'v' and 't' represent? $\endgroup$ – Griffin Dec 13 '11 at 4:50
  • 2
    $\begingroup$ @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 :) $\endgroup$ – matt Dec 13 '11 at 6:02
  • 1
    $\begingroup$ 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? $\endgroup$ – Griffin Dec 13 '11 at 6:28
  • 1
    $\begingroup$ 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. $\endgroup$ – matt Dec 13 '11 at 6:45
  • $\begingroup$ Thanks for the helpfulness, let me know if you can think of any other less-precise, faster methods for approximating the distances! $\endgroup$ – Griffin Dec 13 '11 at 22:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.