Wie finde ich die (x, y) -Koordinaten des Punktes q auf einer geschlossenen 2D-Komposit-Beziér-Kurve, die den (x, y) -Koordinaten eines beliebigen Punktes p am nächsten kommt?

Question

Ich habe eine Reihe von 2D kartesischen Punkte [b], die im Uhrzeigersinn von Anfang an verlaufen und eine geschlossene Form bilden. Jeder von diesen hat seine eigenen begleitenden 2D-Kartesischen Punkte q0 und q1, die die Beziér-Kurve um den Punkt herum definieren (zusammen mit den vorhergehenden und nachfolgenden Punkten). Zusammen definieren alle diese Punkte eine geschlossene 2D composite Beziér curve.

Ich habe einen separaten Punkt , die eine beliebige 2D-kartesischen Punkt auf der gleichen Ebene ist. Gibt es einen einfachen Algorithmus zum Auffinden der (x, y) Koordinaten eines neuen kartesischen 2D-Punktes q welcher ist der nächste Punkt auf dem Pfad zu p?

Wie hier dargestellt, ich habe die Punkte b[0]-b[3] und ihre Griffe b[n].q0 und b[n].q1, und ich habe den beliebigen Punkt p. Ich versuche den Punkt q zu berechnen, nicht als eine Gleitkomma-Position entlang der Kurve, sondern als ein Paar (x, y) Koordinaten.

Ich habe versucht, dies zu suchen, aber einige schienen nur for a very small curve, andere waren weit über meinen Kopf mit abstract mathematics und scientific research papers.

Jede Hilfe, die mich zu einer algorithmischen Lösung führt, wird sehr geschätzt, besonders wenn sie in eine C-ähnliche Sprache übersetzt werden kann, anstatt in die reine Mathematik in den obigen SO Antworten.

Answer 1

Durch the algorithm posted by Tatarize Anpassung kam ich mit dieser Lösung in Swift auf, die in anderen Sprachen übersetzbar sein sollten:

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}