Comment trouver les coordonnées (x, y) du point q sur une courbe de Beziér composite 2D fermée la plus proche des coordonnées (x, y) d'un point arbitraire p?

Question

J'ai un ensemble de 2D Points cartésiens [b], qui partent dans le sens des aiguilles d'une montre et forment une forme fermée. Chacun d'entre eux a ses propres points 2D cartésiens q0 et q1 qui définissent la courbe de Beziér autour du point (avec les points précédents et suivants). Ensemble, tous ces points définissent un 2D fermé composite Beziér curve.

I ont un point p distinct qui est un point cartésien 2D arbitraire sur le même plan. Existe-t-il un algorithme simple pour trouver les coordonnées (x, y) d'un nouveau point cartésien 2D q qui est le point le plus proche sur le chemin de p?

Comme illustré ici, j'ai points b[0]-b[3] et leurs poignées b[n].q0 et b[n].q1, et j'ai le point arbitraire p. J'essaie de calculer le point q, pas comme une position à virgule flottante le long de la courbe, mais comme une paire de (x, y) coordonnées.

J'ai essayé de chercher, mais certains semblaient n'être que for a very small curve, d'autres étaient beaucoup sur ma tête avec abstract mathematics et scientific research papers.

Toute aide qui me conduit vers une solution algorithmique est très apprécié, surtout si elle peut être traduit en langage C comme plutôt que les mathématiques pures au-dessus des réponses SO.

Answer 1

En adaptant the algorithm posted by Tatarize, je suis venu avec cette solution à Swift, qui devrait être traduisible dans d'autres langues:

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}