Find control points to produce a given curve

Question

I've been reading all possible papers about splines for a couple of days now and couldn't answer my own question.

• All papers I was able to find start the definition of Bezier Curve by either introducing it's parametric form with known positions of control points. Wikipedia.
• Or by fitting natural splines to the curve

None of the above actually covers my problem, which is, simply put: I have the numerical values of coordinates $(x, f(x))$ of a curve and I need to find the positions of control points.

So basically I want to find the position of control points so that the generated spline would fit perfectly over my coordinates. I'd also need knots values, obviously. Any ideas?

Answer 1

It is not clear whether the "control points" you need is for Bezier curve or for B-spline curve. Since many graphic toolkits only take quadratic/cubic Bezier curves, I will assume this is what you want.

For creating multiple Bezier curves interpolating a given set of data points, you can go with Catmull-Rom spline interpolation or natural spline interpolation. Both schemes will produce a cubic Bezier curve in between each two data points but the natural spline interpolation will require solving a linear equation set.

If you really want to do B-spline interpolation, please refer this link for more details. You will have to decide a knot vector in advance, which is typically derived from the parameters for the points so that the linear equation matrix is not ill-conditioned.

Answer 2

Check David Eberly's "Least-Squares Fitting of Data with B-Spline Curves":

https://www.google.com.ar/url?sa=t&source=web&rct=j&url=https://pdfs.semanticscholar.org/c285/3cda7a849fee18bcc8bbf2136b1493acb92a.pdf&ved=2ahUKEwiUsvzRutHYAhVFlJAKHUpiCOMQFjAGegQIDRAB&usg=AOvVaw3cMGSLne8D5W2ly8X-Bghf

It is one of the best explanations that I have seen. The C++ implementation is given in his Open Source software library named Geometric Tools.

Basically you have your sample points $P_k$ and you want to compute the control points $Q_i$ such that:

$ \sum_i^n {N_i(t_k) Q_i} = P_k$

This system can be writen in matrix form. Let us define the column vector $\textbf Q = \{ Q_0, ..., Q_n \}$, the column vector $\textbf P= \{ P_0, ..., P_m \}$ and the matrix $\textbf A = \{ a_{ij} = N_j(t_i) \}$ the system is:

$\textbf A \textbf Q = \textbf P$

The system need to be solved once per component of $\textbf Q$, so matrix decomposition is best suited in terms of performance and accuracy. The matrix $\textbf A$ is sparse and banded so can be efficiently pre-factored. However, often its condition number is high so numerical precision is needed (avoid gaussian elimination).

If you have more sample points than control points (as is usually the case $m > n$) then the matrix $\textbf A$ is skinny (the system is overdetermined) and the best solution can be found in the least squares sense as:

$(\textbf A^T \textbf A) \textbf Q =\textbf A^T \textbf P$

Knot vector can be chosen Uniform as Dr Eberly suggest in his paper.