algorithm - 如何在最接近任意点 p 的 (x, y) 坐标的闭合二维复合贝塞尔曲线上找到点 q 的 (x, y) 坐标？

Question

我有一组 2D 笛卡尔点 [b]，它们从一开始就顺时针方向移动并形成一个闭合形状。其中每一个都有自己的二维笛卡尔点 q0 和 q1，它们定义了围绕该点(以及之前和之后的点)的 Beziér 曲线。所有这些点一起定义了一个封闭的二维 composite Beziér curve .

我有一个单独的点p，它是同一平面上的任意二维笛卡尔点。 是否有一种简单的算法可以找到新的二维笛卡尔点 q 的 (x, y) 坐标，它是到 路径上最近的点p?

如此处所示，我有点 b[0] 到 b[3] 及其句柄 b[n].q0和 b[n].q1，我有任意点 p。我正在尝试计算点 q，不是作为沿曲线的浮点位置，而是作为一对 (x, y) 坐标。

我试着搜索这个，但有些似乎只是 for a very small curve , 其他人对 abstract mathematics 感到困惑。和 scientific research papers .

非常感谢任何引导我找到算法解决方案的帮助，特别是如果它可以翻译成类似 C 的语言而不是上述 SO 答案中的纯数学。

Answer 1

通过改编the algorithm posted by Tatarize ，我在 Swift 中想出了这个解决方案，它应该可以翻译成其他语言:

struct BezierPoint {
    let q0: CGPoint
    let point: CGPoint
    let q1: CGPoint
}

struct SimpleBezierCurve {
    let left: BezierPoint
    let right: BezierPoint
}

class BezierPath {
    var pathPoints = [BezierPoint]()

    func findClosestPoint(to targetPoint: CGPoint) -> CGPoint {
        let segments = allSegments()
        guard segments.count > 0 else { return targetPoint }
        var closestPoint = (distance: CGFloat.infinity, point: CGPoint(x: CGFloat.infinity, y: CGFloat.infinity))
        segments.forEach{ curve in
            let thisPoint = BezierPath.findClosestPoint(to: targetPoint, along: curve)
            let distance = findDistance(from: targetPoint, to: thisPoint)

            if (distance < closestPoint.distance) {
                closestPoint = (distance: distance, point: thisPoint)
            }
        }
        return closestPoint.point
    }

    func allSegments() -> [SimpleBezierCurve] {
        guard pathPoints.count > 0 else { return [] }
        var segments = [SimpleBezierCurve]()
        var prevPoint = pathPoints[0]
        for i in 1 ..< pathPoints.count {
            let thisPoint = pathPoints[i]
            segments.append(SimpleBezierCurve(left: prevPoint, right: thisPoint))
            prevPoint = thisPoint
        }
        segments.append(SimpleBezierCurve(left: prevPoint, right: pathPoints[0]))
        return segments
    }

    static func findClosestPoint(to point: CGPoint, along curve: SimpleBezierCurve) -> CGPoint {
        return findClosestPointToCubicBezier(to: point, slices: 10, iterations: 10, along: curve)
    }

    // Adapted from https://stackoverflow.com/a/34520607/3939277
    static func findClosestPointToCubicBezier(to target: CGPoint, slices: Int, iterations: Int, along curve: SimpleBezierCurve) -> CGPoint {
        return findClosestPointToCubicBezier(iterations: iterations, to: target, start: 0, end: 1, slices: slices, along: curve)
    }

    // Adapted from https://stackoverflow.com/a/34520607/3939277
    private static func findClosestPointToCubicBezier(iterations iterations: Int, to: CGPoint, start: CGFloat, end: CGFloat, slices: Int, along curve: SimpleBezierCurve) -> CGPoint {
        if iterations <= 0 {
            let position = (start + end) / 2
            let point = self.point(for: position, along: curve)
            return point
        }
        let tick = (end - start) / slices
        var best = CGFloat(0)
        var bestDistance = CGFloat.infinity
        var currentDistance: CGFloat
        var t = start

        while (t <= end) {
            //B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3
            let point = self.point(for: t, along: curve)

            var dx = point.x - to.x;
            var dy = point.y - to.y;
            dx *= dx;
            dy *= dy;
            currentDistance = dx + dy;
            if (currentDistance < bestDistance) {
                bestDistance = currentDistance;
                best = t;
            }
            t += tick;
        }
        return findClosestPointToCubicBezier(iterations: iterations - 1, to: to, start: max(best - tick, 0.0), end: min(best + tick, 1.0), slices: slices, along: curve);
    }

    static func point(for t: CGFloat, along curve: SimpleBezierCurve) -> CGPoint {
        // This had to be broken up to avoid the "Expression too complex" error

        let x0 = curve.left.point.x
        let x1 = curve.left.q1.x
        let x2 = curve.right.q0.x
        let x3 = curve.right.point.x

        let y0 = curve.left.point.y
        let y1 = curve.left.q1.y
        let y2 = curve.right.q0.y
        let y3 = curve.right.point.y

        let x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3
        let y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3

        return CGPoint(x: x, y: y)
    }
}

// Possibly in another file
func findDistance(from a: CGPoint, to b: CGPoint) -> CGFloat {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

^{GitHub Gist}