algorithm - 任意の点 p の (x, y) 座標に最も近い、閉じた 2D 複合ベジエ曲線上の点 q の (x, y) 座標を見つけるにはどうすればよいですか?

Question

最初から時計回りに進み、閉じた形状を形成する2Dデカルト ポイントのセットがあります。[b]これらのそれぞれには、独自のコンパニオン 2D デカルト ポイントがq0ありq1、ポイントの周りのベジエ曲線を定義します (前後のポイントと共に)。これらすべての点が一緒になって、閉じた 2D合成ベジエ曲線を定義します。

p同じ平面上の任意の 2D デカルト ポイントである別のポイントがあります。へのパス上の最も近い点である新しい 2D デカルト点の座標を見つけるための簡単なアルゴリズムはありますか?(x, y)qp

ここに示されているように、ポイントb[0]とb[3]そのハンドルb[n].q0およびb[n].q1があり、任意のポイント がありpます。q曲線に沿った浮動小数点位置としてではなく、(x, y)座標のペアとしてpoint を計算しようとしています。

これを検索してみましたが、非常に小さな曲線だけのように見えるものもあれば、抽象的な数学や科学研究論文で私の頭をはるかに超えているものもありました。

特に、上記のSOの回答の純粋な数学ではなく、Cのような言語に翻訳できる場合は特に、アルゴリズムの解決策に私を導く助けがあれば大歓迎です。

Answer 1

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 要点}