Thread: [Algorithms] Curve fitting problem
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Ivan V. <iv...@gm...> - 2009-09-01 19:24:01
|
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. Any help much appreciated. Thanks, Ivan |
|
From: Jon W. <jw...@gm...> - 2009-09-01 20:05:24
|
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. |
|
From: Danny K. <dr...@we...> - 2009-09-01 20:30:45
|
> 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. What do you mean by 'close' and by 'certain points'? Do you have a picture? Danny |
|
From: Fabian G. <f.g...@49...> - 2009-09-01 20:32:18
|
> 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 |
|
From: Jarkko L. <al...@gm...> - 2009-09-01 21:02:43
|
Not exactly what you are looking for, but I have some code online which iteratively fits a spline constructed of cubic curves to a set of n-d points within given tolerance constraints (e.g. distance, velocity, etc.) It also assumes that the input keys are evenly distributed on a timeline. This is mainly meant for animation key frame compression (position & rotation), but might be a useful reference for you. It's the fit_spline() function of the following link: http://spinxengine.svn.sourceforge.net/viewvc/spinxengine/src/core/math/para metric.inl?view=markup ... and here is some unit test code for use cases (search for fit_spline): http://spinxengine.svn.sourceforge.net/viewvc/spinxengine/src/unittest/core/ math/parametric.cpp?view=markup Cheers, Jarkko -----Original Message----- From: Ivan Vorobeychyk [mailto:iv...@gm...] Sent: Tuesday, September 01, 2009 10:24 PM To: GDA...@li... Subject: [Algorithms] Curve fitting problem 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. Any help much appreciated. Thanks, Ivan ---------------------------------------------------------------------------- -- Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
|
From: Juan L. <re...@gm...> - 2009-09-01 21:31:54
|
My suggestion may feel hackish but i think it gets the closest to what you may need. Just use a cubic spline between the points you want to pass by for sure, and ignore the others. Use a second cubic spline that goes through ALL the points. Interpolate both to the measure you want, and you should have a curve that passes by some points and gets close to the others. On Tue, Sep 1, 2009 at 4:23 PM, Ivan Vorobeychyk <iv...@gm...> 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. > > Any help much appreciated. > Thanks, > Ivan > > > ------------------------------------------------------------------------------ > Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day > trial. Simplify your report design, integration and deployment - and focus > on > what you do best, core application coding. Discover what's new with > Crystal Reports now. http://p.sf.net/sfu/bobj-july > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
|
From: David B. <dbe...@na...> - 2009-09-01 22:47:00
|
That sounds like a great idea. It seems to me that the one tricky bit will be to break up the spline curve segments from the spline that goes through only some points into multiple segments to make the interpolation between curve segments work. For curves that pass through all the points I would recommend the Catmul-Rom algorithm, a special case of the Cubic Hermite spline given earlier (and listed on that wikipedia page -- http://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull.E2.80.93Rom_spline) David Bennett NAMCO BANDAI Games America Inc. ________________________________ From: Juan Linietsky [mailto:re...@gm...] Sent: Tuesday, September 01, 2009 2:32 PM To: Game Development Algorithms Subject: Re: [Algorithms] Curve fitting problem My suggestion may feel hackish but i think it gets the closest to what you may need. Just use a cubic spline between the points you want to pass by for sure, and ignore the others. Use a second cubic spline that goes through ALL the points. Interpolate both to the measure you want, and you should have a curve that passes by some points and gets close to the others. On Tue, Sep 1, 2009 at 4:23 PM, Ivan Vorobeychyk <iv...@gm...<mailto:iv...@gm...>> 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. Any help much appreciated. Thanks, Ivan ------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ GDAlgorithms-list mailing list GDA...@li...<mailto:GDA...@li...> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
Thanks for helping keep SourceForge clean.
X