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?

Question

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?

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.

Answer 1

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}