Ergo - 1 year ago 70

Swift Question

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!

Following the suggestion of

The white part is created by the program of how he calculates the distance. I compute the angle

`phi`

What could be the problem? I cannot really understand this behavior (could it have something to do with atan2??)

I show also that in the other half of the ellipse it gives this result:

So we can see that the only case where this works is when we have

`phi = -+pi/2`

`phi = -+pi`

I tried using the implementation of

At first I thought it could be the center (that is not always the same) and I changed the implementation this way:

`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)

}

We can see what happens here:

This is pretty strange, all points stay in that "quadrant". But I also noticed when I move the green box far far away from the ellipse it seems to get the right vector for the distance.

What could it be?

Using updated version of

Answer Source

`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)
```