首页 文章

从点到椭圆的距离

提问于
浏览
2

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

我想计算点P和椭圆之间的最短距离 . 我的想法是从我的椭圆中心和点P计算矢量,然后找到从中心开始并在点P的方向到达椭圆的末端的矢量,并在末尾减去两个矢量距离(thi可能没有给出最短的距离,但它仍然适合我需要的 . 问题是我不知道如何计算第二个向量 . 有人有更好的想法或者可以告诉我如何找到第二个缩放的矢量?

提前致谢!


EDIT1:

ISSUE:COMPUTED ANGLE DOESN'T SEEM TO GIVE RIGHT POINT ON ELLIPSE

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

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

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

EDIT2: 我还表明,在椭圆的另一半,它给出了这个结果:

所以我们可以看到,只有当我们有 phi = -+pi/2phi = -+pi


IMPLEMENTATION FAILED

我尝试使用 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)

}

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

这很奇怪,所有的点都留在那个“象限” . 但是我也注意到当我将绿色框移动到远离椭圆的位置时,似乎得到了距离正确的向量 .

会是什么呢?


END RESULT

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

4 回答

  • 0

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

  • 2

    我使用Latex编写了一个解释,因此它可以更具可读性,只需要拍摄一些屏幕截图 . 我分享的方法是使用基于牛顿步骤的优化方法来解决问题 .

    请注意,对于主轴和短轴长度之间的比例较小的椭圆的情况,最多只需要几次迭代即可获得非常好的精度 . 对于较小的比率,您甚至可能只是初步猜测的结果,这实际上是 Martin R 显示的结果 . 但是,如果您的椭圆可以是任何形状,您可能需要添加一些代码来改进近似值 .

  • 0

    你有(a,b)的省略号中心和P(Px,Py)的任意点 . 由这两点定义的线的等式如下所示:

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

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

  • 1

    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)
    

    你是对的,这不会给出点到椭圆的最短距离 . 这将需要求解4次多项式方程,例如参见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)
    

相关问题