Re: [Algorithms] Curve fitting problem

[Fabian G. <f.g...@49...>]

> Hi, guys.
> 
> I have a problem that I think has been solved many times,
> hope somebody can point me to appropriate technique.
> 
> I have an ordered set of points in 2-d space, that represents a curve
> (like set of pixels, drawn with pencil in Paint).
> I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
> of these points (control points) and will pass CLOSE to other points
> from the given set.

It depends on what kind of spline you need, how it is parametrized, and 
what type of smoothness you need.

The parametrization (i.e. at what "time" the curve passes through or 
close to a given point) in particular makes a large difference; 
interestingly, the problem is a lot easier if you have very specific 
requirements on the parametrization, because that means you don't have 
to optimize for it. Determining optimal control points given a set of 
samples with explicit "timestamps" can be efficiently solved as a linear 
least squares system. But if the "timestamps" aren't fixed, the problem 
is nonlinear and quite difficult to solve.

For a relatively simple solution, just fit cubic splines. Assign the 
timestamps based on geometric distance between your sample points (not 
necessarily ideal, but probably not bad, either). Decide on which spline 
type you want to fit. For this type of problem, I'd try a cubic hermite 
curve first, with one segment per pair of "exact" control points. For 
smoothness, require that the derivatives between adjacent spline 
segments match; that gives you C^1 continuity (you can't do better in 
the general case with cubic curves as long as you require the curve to 
interpolate certain points).

Your constraints fix the start and end points of each segment and 
requires derivatives to match; that leaves one derivative per spline 
segment (plus one extra at the end) as unknowns. Given target 
"timestamps" for each of the sample points you want the curve to pass 
closely, you can solve for them using linear least squares, as mentioned 
above.

That's one way to do it. If you need something different, state your 
problem more precisely :)

Kind regards,
-Fabian Giesen