Distance between ellipse path and point?

Question

So, I am working with an ellipse on a drawing surface, and I need to know the shortest distance from the ellipse path (center of the line thickness is fine) to a given point.

I can do this with raw math, if I need to, since I know Major and Minor axis of the ellipse. As far as I can tell, this will be rather complex.

I was wondering if my view can calculate this for me?

I am using an EllipseGeometry and setting the axis. The EllipseGeometry is then handed to the path (Path.Data) and it gets drawn.

Any thoughts to know what the shortest distance to the path is?

Answer 1

Just check this out

http://www.geometrictools.com/Documentation/DistancePointToEllipse2.pdf

Answer 2

Just to close the loop on this:

I found some C++ code that did this with math, and translated over to C#. I don't know how it works, but it does.

Ultimately, I was looking to highlight an ellipse when the mouse got near it. I was able to accomplish this with a different approach as well (but stayed with the pure-math approach):

Create a second path with the same geometry and translation as the path I am showing, but with a much thicker StrokeThickness and an opacity of 0.1. Do some hit testing on the larger, opaque path.

Answer 3

If you're going to be doing a lot of stuff with Geometries, measurements, etc., I would highly recommend the Farseer Physics Engine for Silverlight. I used it in a puzzle game, and it does a great job of managing all of the math for you.

I just create the shapes I need in the physics simulator, and then use their positions in the physics simulator to render them on a canvas.

Answer 4

I read the article mentioned above. I have the math background to implement it, but not the patience. If you are going to use Newton's method to approximate something, why go to the bother of doing the derivatives, the algebra, and all that as well?

Here is my idea:

1) Assume ellipse is (x/a)^2 + (y/b)^2 = 1
   That is, the origin is at zero and the rotation angle is zero. 
(Transform your ellipse and point of interest P1 by rotation and translation if necessary before beginning.)
2) Convert the ellipse into parametric form.
       x = a cos t  
       y = b sin t
3) Divide the parametric range of "t" into N parts, from 0 to 2*PI.
N = 16 seems like a good number (22.5 degrees).
4) Iterate through the N points along the ellipse, stepping t by 2*PI/N each time.
5) Compute the point P2 on the ellipse.
6) Compute the distance from P1 to P2.
7) Keep track of the closest distance dmin found so far, and the value of the parameter as tmin.
8) Start a second loop, but shrink the range for t to being  (tmin - 2*PI/N, tmin + 2*PI/N).
9) Repeat the search, dividing this smaller range by N again.
10) Add new loops as necessary until the distance between successive points is less than the tolerance that matters to you.

Approximating the ellipse as a circle with the major radius, since C = 2*PI*R, successive points being tested will be one pixel apart when N = 2*PI*R.

Using 16 steps per loop, the number of points to be compared is 16*log8(PI*R).

As a further refinement, I would reflect the point into the first coordinate (positive x & y). That saves computations against 3/4 of the ellipse.

The above algorithm leads to much simpler code: easier to write and debug. Efficiency is another matter. For many applications, it should be good enough.

Answer 5

Just a quick addemdum to Paul Chernoch's approach (long after the fact, for those who might happen by) - don't get lulled into a false sense of precision. Each time you slice a section down into further subsections, you inherit the error of the "parent" section. Put another way, the refined results are never more accurate than the tmin and tmax values you started with on that iteration.

If you need a very accurate result, be sure to start with a large value of N in the first loop.