Re: [Algorithms] Curve fitting problem

[Jon W. <jw...@gm...>]

Ivan Vorobeychyk wrote:
> 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.
>   

A "default" cubic spline will fit through all of the points, smoothly 
(C0 and C1 AFAICR). You treat each sub-segment of 4 points as one 
segment to interpolate -- 0,1,2,3 generates data for the 1-2 segment; 
1,2,3,4 generates data for the 2-3 segment etc.

If that's not good enough, you can start with that spline, and then 
adjust the points that are adjustable in a direction that makes the 
spline "better" (whatever that means), while making sure they are still 
"close" (whatever that means).

If you can come up with an algorithmic definition of "better" and 
"close," then you can just throw a regular LP optimization solver at the 
problem. Because the system is semi-local (a change affects neithbors at 
most two segments away) it might also be amenable to greedy optimization 
and/or recursive subdivision optimization.

Sincerely,

jw



-- 

  Revenge is the most pointless and damaging of human desires.