点到椭圆的距离

Distance from point to ellipse

我需要以某种方式计算点和椭圆之间的距离。 我在程序中将椭圆描述为坐标 x = a cos phi 和 y = b sin phi(其中 a、b 是常数,phi 是变化的角度)。

我想计算点 P 和我的椭圆之间的最短距离。 我的想法是从我的椭圆中心和点 P 计算向量,然后找到从中心开始并沿点 P 的方向到达椭圆末端的向量,最后减去两个向量得到距离(这可能不会给出最短距离,但它仍然可以满足我的需要。 问题是我不知道如何计算第二个向量。 有人有更好的想法或者可以告诉我如何找到第二个向量吗?

提前致谢!


编辑1:

问题:计算出的角度似乎没有给出椭圆上的正确点

根据 MARTIN R 的建议,我得到了这个结果:

白色部分是他计算距离的程序创建的。我使用从中心 P(椭圆)到 body 中心的向量计算角度 phi。但是当我使用我的椭圆方程中的角度来获得应该留在椭圆上但也具有与第一个计算向量相同方向的点时(如果我们将该点视为向量)它实际上给出了 "delayed"上面显示的向量。

可能是什么问题?我无法真正理解这种行为(它可能与 atan2 有关吗??)

编辑2: 我还展示了在椭圆的另一半中它给出了这个结果:

所以我们可以看到唯一可行的情况是当我们有 phi = -+pi/2phi = -+pi


实施失败

我尝试使用 MARTIN R 的实现,但我仍然出错。

起初我以为它可能是中心(并不总是相同的),我这样改变了实现方式:

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)

}

我们可以看到这里发生了什么:

这很奇怪,所有的点都留在"quadrant"。但我也注意到,当我将绿色框移离椭圆很远时,它似乎获得了正确的距离矢量。

会是什么?


最终结果

使用 MARTIN R 的更新版本(3 次迭代)

你有 (a, b) 的椭圆中心和 P(Px, Py) 的任意点。由这两点定义的直线方程如下所示:

(Y - Py) / (b - Py) = (X - Px) / (a - Px)

你的另一种形式是椭圆。您需要找出哪些是既在椭圆上又在中心和点之间的线上的 (X, Y) 点。将有两个这样的点,您需要计算它们与 P 的距离并选择较小的距离。

x = a cos(phi), y = b sin (phi)是一个椭圆,中心在 您问题中描述的起源和方法可以这样实现:

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

你是对的,这并没有给出最短距离 的点到椭圆。那将需要解决第四度 多项式方程,参见 distance from given point to given ellipseCalculating Distance of a Point from an Ellipse Border.

这是算法的一个可能实现 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))
}

您可能需要调整最大迭代次数和 epsilon 根据您的需要,但这些价值观对我很有效。 对于椭圆外的点,最多需要 3 次迭代 找到解决方案的良好近似值。

使用它你可以计算出距离

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)

创建新的坐标系,将椭圆转化为圆https://math.stackexchange.com/questions/79842/is-an-ellipse-a-circle-transformed-by-a-simple-formula,然后求点到圆的距离,并转换距离

我使用 Latex 写了一个解释,这样它可以更具可读性,并且只拍了一些屏幕截图。我分享的方法是使用基于牛顿步的优化方法来解决问题。

请注意,对于椭圆的长轴和短轴长度之比较小的情况,最多只需要几次迭代即可获得相当不错的精度。对于较小的比率,您甚至可能只得到初始猜测的结果,这基本上就是 Martin R 显示的结果。但是如果你的椭圆可以是任何形状,你可能想添加一些代码来改进近似值。