Fit $n$ Bézier paths to coordinates

Question

I have a some coordinates $(X_i, Y_i)$ and I have to fit exactly $4$ cubic Bézier-paths to them (in other words, I have to find the 4 best fitting Bézier-paths, and by best fitting I mean that the vertical distance at all $X_i$ should be less than some predifend value between the Bézier-paths and $Y_i$)

The start and end $X$ coordinate of each bezier path is also not fixed (so for example if the interval on for the fitting on the $X$ axis is between $[0, 100]$, it is possible that $3$ bezier paths are in the interval $[0-10]$ and the last one is in $[10-100]$)

Are there any iterative methods to find such cubic Bézier-paths?

Answer 1

Least-squares fitting with a cubic b-spline is probably a good approach. Your b-spline will consist of four cubic Bézier curves, joined end-to-end.

To construct a b-spline curve, you need a set of "knots". A knot is an $x$-values where two cubic segments join together. In addition, each knot value can be repeated -- in other words it can have a "multiplicity" that is larger than 1. The multiplicity of a knot determines the smoothness of the join. Specifically, on a cubic curve

• Multiplicity of 1 gives you continuity of second derivative
• Multiplicity of 2 gives you continuity of first derivatives (no sharp corner)
• Multiplicity of 3 gives you continuity of position (no break in the curve)

The first and last knot values are typically given a multiplicity of 4, to force interpolation of the first and last control points. So, if your domain is $[0,100]$, an example knot sequence would be: $$ 0,0,0,0, \;30,30, \;60,60, \;80,80, \;100,100,100, 100 $$ This will give you a cubic b-spline with segment joins at $x=30$, $x=60$, $x=80$, and with continuity of first derivative at each join.

To find out how to do least-squares fitting with a b-spline curve, please consult these notes.

But the big questions are why I chose the knots $30, 60, 80$, and whether a different choice of knots will give us a better fit. My choice was arbitrary, and is almost certainly not optimal. But, if you use the knot values as indepenedent variables in the fitting process, it turns into a fairly nasty non-linear problem. The only approach I know is to toss the problem to your favorite general-purpose optimization algorithm and hope for the best.

As one of the comments said, there is no guarantee that the error you obtain will be less than some predefined value.