I need to somehow compute the distance between a point and an Ellipse.
I describe the Ellipse in my program as coordinates x = a cos phi and y = b sin phi (where a,b are constants and phi the changing angle).
I want to compute the shortest distance between a point P and my ellipse.
My thought were to calculate the vector from the center of my ellipse and the point P and then find the vector that start from the center and reaches the end of the ellipse in the direction of the point P and at the end subtract both vectors to have the distance (thi may not give the shortest distance but it's still fine for what I need.
The problem is I don't know how to compute the second vector.
Does someone has a better Idea or can tell me how I can find the second vetor?
Thanks in advance!
phi
phi = -+pi/2
phi = -+pi
func pointOnEllipse(ellipse: Ellipse, p: CGPoint) -> CGPoint {
let maxIterations = 10
let eps = CGFloat(0.1/max(ellipse.a, ellipse.b))
// Intersection of straight line from origin to p with ellipse
// as the first approximation:
var phi = atan2(ellipse.a*p.y, ellipse.b*p.x)
// Newton iteration to find solution of
// f(θ) := (a^2 − b^2) cos(phi) sin(phi) − x a sin(phi) + y b cos(phi) = 0:
for _ in 0..<maxIterations {
// function value and derivative at phi:
let (c, s) = (cos(phi), sin(phi))
let f = (ellipse.a*ellipse.a - ellipse.b*ellipse.b)*c*s - p.x*ellipse.a*s + p.y*ellipse.b*c - ellipse.center.x*ellipse.a*s + ellipse.center.y*ellipse.b*c
//for the second derivative
let f1 = (ellipse.a*ellipse.a - ellipse.b*ellipse.b)*(c*c - s*s) - p.x*ellipse.a*c - p.y*ellipse.b*s - ellipse.center.x*ellipse.a*c - ellipse.center.y*ellipse.b*s
let delta = f/f1
phi = phi - delta
if abs(delta) < eps { break }
}
return CGPoint(x: (ellipse.a * cos(phi)) + ellipse.center.x, y: (ellipse.b * sin(phi)) + ellipse.center.y)
}
x = a cos(phi), y = b sin (phi)
is an ellipse with the center at
the origin, and the approach described in your question can be realized like this:
// Point on ellipse in the direction of `p`:
let phi = atan2(a*p.y, b*p.x)
let p2 = CGPoint(x: a * cos(phi), y: b * sin(phi))
// Vector from `p2` to `p`:
let v = CGVector(dx: p.x - p2.x, dy: p.y - p2.y)
// Length of `v`:
let distance = hypot(v.dx, v.dy)
You are right that this does not give the shortest distance of the point to the ellipse. That would require to solve 4th degree polynomial equations, see for example distance from given point to given ellipse or Calculating Distance of a Point from an Ellipse Border.
Here is a possible implementation of the algorithm described in http://wwwf.imperial.ac.uk/~rn/distance2ellipse.pdf:
// From http://wwwf.imperial.ac.uk/~rn/distance2ellipse.pdf .
func pointOnEllipse(center: CGPoint, a: CGFloat, b: CGFloat, closestTo p: CGPoint) -> CGPoint {
let maxIterations = 10
let eps = CGFloat(0.1/max(a, b))
let p1 = CGPoint(x: p.x - center.x, y: p.y - center.y)
// Intersection of straight line from origin to p with ellipse
// as the first approximation:
var phi = atan2(a * p1.y, b * p1.x)
// Newton iteration to find solution of
// f(θ) := (a^2 − b^2) cos(phi) sin(phi) − x a sin(phi) + y b cos(phi) = 0:
for i in 0..<maxIterations {
// function value and derivative at phi:
let (c, s) = (cos(phi), sin(phi))
let f = (a*a - b*b)*c*s - p1.x*a*s + p1.y*b*c
let f1 = (a*a - b*b)*(c*c - s*s) - p1.x*a*c - p1.y*b*s
let delta = f/f1
phi = phi - delta
print(i)
if abs(delta) < eps { break }
}
return CGPoint(x: center.x + a * cos(phi), y: center.y + b * sin(phi))
}
You may have to adjust the maximum iterations and epsilon according to your needs, but those values worked well for me. For points outside of the ellipse, at most 3 iterations were required to find a good approximation of the solution.
Using that you would calculate the distance as
let p2 = pointOnEllipse(a: a, b: b, closestTo: p)
let v = CGVector(dx: p.x - p2.x, dy: p.y - p2.y)
let distance = hypot(v.dx, v.dy)