Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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