algorithmbezierclosest-points

How do I find the (x, y) coordinates of the point q on a closed 2D composite Beziér curve closest to the (x, y) coordinates of some arbitrary point p?


I have a set of 2D Cartesian points [b], which proceed clockwise from the start and form a closed shape. Each one of these has its own companion 2D Cartesian points q0 and q1 which define the Beziér curve around the point (along with the preceding and succeeding points). Together, all these points define a closed 2D composite Beziér curve.

I have a separate point p which is an arbitrary 2D Cartesian point on the same plane. Is there a simple algorithm for finding the (x, y) coordinates of a new 2D Cartesian point q which is the closest point on the path to p?

Four blue points labeled b[0] through b[4], each with two child green points labeled b[n].q0 and b[n].q1 connected to their blue parent by grey lines, forming a red path whose basic shape is dictated by the positions of the blue points, and curvature by the green ones. Above the curve there lies an orange point p, connected by a grey line to a purple point q, which lies on the red path at the closest point to p.

As illustrated here, I have the points b[0] to b[3] and their handles b[n].q0 and b[n].q1, and I have the arbitrary point p. I'm trying to calculate the point q, not as a floating-point position along the curve, but as a pair of (x, y) coordinates.

I tried searching this, but some seemed to only be for a very small curve, others were way over my head with abstract mathematics and scientific research papers.

Any help that leads me toward an algorithmic solution is greatly appreciated, especially if it can be translated into a C-like language rather than the pure math in the above SO answers.


Solution

  • By adapting the algorithm posted by Tatarize, I came up with this solution in Swift, which should be translatable to other languages:

    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