Draw good-looking Bezier Curve through random points

Question

I'm using javascript with RaphaelJS to draw a smooth line through random points with output to SVG. The line goes strictly horizontally, without returning back in axis X. Currently, I'm using cubic Bezier curves to draw the line from one point to another.

Problem is, the line doesn't look good enough. Two curves have an unsightly join at a point, where one curve ends and another curve starts, with quite random angle in the joint. How do I get the previous curve to transform into next one smoothly, while still keeping the line passing through given point?

Answer 1

Catmull-Rom curves work well for going through points. http://schepers.cc/getting-to-the-point

Answer 2

Cubic splines

If you want to draw lines through points, then you want interpolation. Beziers are cubic curves with off-curve control nodes, but a cubic spline is a set of cubic curves through n points, with smooth changes from each to the next. See the Wikipedia article for more detail on the maths.

To construct a cubic spline through a set of points, you unfortunately have to perform an iterative procedure; you are essentially making n-1 cubic curves and matching their parameters together, which gives you n+1 simultaneous equations to solve. Once you have done that once, as you move the points you can use your previous solution as a starting point.

To do this in Raphael you'll need to generate the cubic spline, then calculate the equivalent Bezier control values for each segment.

There are pieces of javascript out there to calculate cubic splines for you, for example Cubic splines in JavaScript (via CoffeeScript).

Piecewise polynomial

An alternative to cubic splines is to fit a cubic (or higher) polynomial to each set of a few points; e.g. cubic to each 4 points, including overlaps. So points 10-13 make the cubic for the line from 11 to 12. It will not be as smooth as a cubic spline, but it should be much closer. This is pretty similar to cubic spline, but without equation solve for the curve parameters to make everything smooth.

The problem with piecewise polynomial is that it uses higher order polynomials, which are unstable, and you can get large kinks and wiggles when the points don't lie on polynomial lines or when the points are close together.

To draw this in Raphael you are probably best just sampling the line more frequently and using straight lines to draw it.

Line shape

One big consideration is what kind of line you want to draw. If you just want a smooth line, do cubic spline. But if you are drawing statistics or some other specific kind of line you may be better off looking into gaussian decomposition or other things: Cubic splines are cubic polynomials (ax³ + bx² + cx + d = 0), so you cannot approximate sine curves very well (audio/signals), or Gaussians (signals/statistics), or exponentials (decay curves, long tail statistics).