Curve fitting a series of line segments

问题:

There are a lot of curve fitting questions on SO but I can't seem to find one that addresses what I'm looking for.

The scenario is simple: I capture X/Y points on a tablet screen. I'd like to draw the resulting line segments as a smooth curve instead of a series of line segments. Many apps do this, for example: Penultimate (sketching demo at 0:36) or Autodesk Sketchbook.

Bezier curve algorithms take a fixed number of points to draw a curve and don't seem to work well with numerous multiple points. Can anyone point to an algorithm which does this well?

回答1:

Fit-Curve is a Spline and not a Bezier Curve in fact. However, you can make a Bezier Curve to look like your Spline (Splines have no control points). I've searched a lot on this problem and introduced/implemented a lot of too-complex algorithms to myself, and finally I found that the task is much easier than I supposed (I do felt it must to, I swear :) )

Here is the best description on that, I'll take an excerpt from this article:

In most implementations, Bezier Curve drawing function takes two control points and a point itself (for a segment) as an arguments, so everything you need is just iteratively finding the control points for new segments (I think it is best to update last segment and draw a new one in the end of curve for every new point):

Here comes the JavaScript code (t for a simplest case is a constant smoothness of your curve):

function getControlPoints(x0,y0,x1,y1,x2,y2,t){
    var d01=Math.sqrt(Math.pow(x1-x0,2)+Math.pow(y1-y0,2));
    var d12=Math.sqrt(Math.pow(x2-x1,2)+Math.pow(y2-y1,2));
    var fa=t*d01/(d01+d12);
    var fb=t*d12/(d01+d12);
    var p1x=x1-fa*(x2-x0);
    var p1y=y1-fa*(y2-y0);
    var p2x=x1+fb*(x2-x0);
    var p2y=y1+fb*(y2-y0);  
    return [p1x,p1y,p2x,p2y];
}

Please be sure to read and understand the article, I think it is a best, shortest and clearest one.

回答2:

Check out splines. They basically take a set of control points as input and output a set of cubic curve where each curve is tangent to the previous one giving a smooth outline.

See this: http://en.wikipedia.org/wiki/Cubic_Hermite_spline