Algorithm to min-square-distance fit a cubic Bezier curve to a set of points

Question

There are some answered questions on fitting Bezier to data, but I'm looking for an algorithm rather than a ready solution. Something that I could implement according to other requirements.

Input: a small set of 2D data points, a dozen or so; the pre-defined Bezier endpoints.

Output: a planar cubic Bezier curve with the specified endpoints that minimizes mean square distance to the data points.

What I thought of: compute the square distance of a data point to a parametrized Bezier; take derivative over the parameter t; compute the distance where the derivative is 0; add that up for all the data points; take the derivative over the free control points; optimize that.

Where the problem lies: When you compute the derivate of the square distance from a point to a cubic Bezier curve you get a 5th degree equation. There is no analytic solution for that, so you have to Newton-Raphson iterate to get a numerical solution. Because of that when you are adding up the distance to all the data points and optimize the free Bezier control points you have to optimize numerically with a gradient-free algorithm, and that tends to be slow. This is doable, but will take way more compute time that should be necessary. What make the runtime issue even worse is that the problem needs to be solved for millions of Bezier curves, each fitting a dozen or so of its own data points. If each of the Beziers requires a numerical optimization wrapped around another numerical optimization that would make the solution unacceptably slow.

Therefore I'm looking for a reasonably fast, preferably analytic solution for Bezier curve fitting. If an exact solution is impossible then a reasonably fast numerical one would do.

Answer 1

Simple approach. Just use gradient descent to solve for the control points at the same time that you also solve for where the closest points are.

You are given start_point, end_point, data_points. Come up with some semi-reasonable guess for c1, c2, t where c1 and c2 are control points, and t[i] is a parameter for a point on that Bezier curve which is fairly close to data_points[i]. And now use gradient descent to minimize the sum of the squares of the errors.

Answer 2

I am not aware of an analytic solution to bezier curve fitting problem. Whether the optimization methods are efficient or not depends also on the constraints as well as the implementation.

If you need G1 continuity between the curves, I think it would be faster if you can estimate the tangents at the predefined end points (catmull-rom type perhaps?). In this case, the method described in "Spline approximation of offset curves" -- Hoschek could work —offset distance being 0. Depending on precision necessary this can converge in a few iterations.