Generating Bézier curves from discrete point sets

November 9, 2006 1:56 PM

What is a good algorithm for generating smooth curves from discrete points?

For example, I have a set of time series data. I can easily draw a jagged line by plotting each point and connecting with straight lines. However, I'd like to make a pretty graph with smooth, interpolated lines using cubic or quadratic Bézier curves.

I’ve looked over the Dojo Charting Engine, which does pretty much what I want, simply calculating the delta along the X-axis, and multiplying by a constant “tension” factor to determine the position of the control points.

Can you point me to any other, similar algorithms?

posted by ijoshua to science & nature (8 comments total)

You should read up on Splines.
posted by vacapinta at 2:05 PM on November 9, 2006

Take a look at CurveExpert. It's shareware with a 30 day evaluation period.
posted by Neiltupper at 2:11 PM on November 9, 2006

Do you have access to Mathematica? If so, you can use the Interpolation command. It works pretty well for what you want.
posted by dseaton at 3:27 PM on November 9, 2006

If you don't know the functional form of your data, a spline fit (see above) is often the "best" answer. Bézier "curves" are a form of splines. the trick to fitting splines is boundary conditions: if you don't get the derivatives right at the ends you sometimes end up with really weird curves (You didn't know you were doing calculus in Photoshop when you were tweaking nodes, now did you?)

If you know a bit more about how your data should behave (no inflection points, for example), you can use a better candidate function to fit your dataset. The simplest way to do this is the linearize you data in terms of the function, e.g., if fittiing an exponential, take the log of your data, then fitting a line, doing the back transform and finally plotting. This only works for farily simple functions though (like splines). Otherwise you're stuck with a non-linear fit.
posted by bonehead at 4:06 PM on November 9, 2006

On rethink: are you plotting data real-time, and/or don't really care about how the fit looks and just want a nice line? In that case, the cheap and nasty way to do it is a moving-average calculation, sort of the red-headed stepchild of a real spline fit. I've found that a five-point trailing average is enough to fake out most obersevers for real-time stuff. Computationally, a moving average is way cheaper than even a spline fit.

Technically, this isn't a fitting so much as a smoothing technique, but if that's what you need, it will serve much the same job.
posted by bonehead at 4:21 PM on November 9, 2006

Nailtupper and dseaton, thanks, but I’m not looking for software to do the job for me. I’m interested in the math behind the process because I’m generating dynamic charts, most likely targeting SVG.

My input data most likely doesn’t fit any particular functional form — it’s a time series of website statistics, e.g. number of active sessions per hour of a day. It isn’t a real-time plot, either.

I don’t think a moving average is what I want, either. I want the line to fit the data pretty accurately, because I’m only analyzing a few dozen samples (or “knots,” I guess) at once.
posted by ijoshua at 5:47 PM on November 9, 2006

A last comment: if you are concerned about understanding your data trends, you may want to consider using something other (or in addition to) splines. Splines will give you a pretty picture, because splines will fit just about anything given enough nodes and boundary condition freedom. They're also quite light-weight numerically. They are very hard to interpret, however. What does the trend line mean? Splines won't tell you.

If you're trying for a functional descritption of your data, you need to try other things and that typically means either tranforming your data, e.g. Fourier transforms to look for periodicity, or using non-linear functional fits. A reasonably practical starting place for both approaches are the "Numerical Recipies in C/C++/Fortran" books, if that's what you're after.
posted by bonehead at 11:16 AM on November 11, 2006

Check out these nice articles by Don Lancaster:
http://www.tinaja.com/cubic01.asp
posted by iconjack at 11:36 AM on November 29, 2006