Point Sequence Interpolation

Question

Given an arbitrary sequence of points in space, how would you produce a smooth continuous interpolation between them?

2D and 3D solutions are welcome. Solutions that produce a list of points at arbitrary granularity and solutions that produce control points for bezier curves are also appreciated.

Also, it would be cool to see an iterative solution that could approximate early sections of the curve as it received the points, so you could draw with it.

Answer 1

Have you looked at the Unix spline command? Can that be coerced into doing what you want?

Answer 2

One way is Lagrange polynominal, which is a method for producing a polynominal which will go through all given data points.

During my first year at university, I wrote a little tool to do this in 2D, and you can find it on this page, it is called Lagrange solver. Wikipedia's page also has a sample implementation.

How it works is thus: you have a n-order polynominal, p(x), where n is the number of points you have. It has the form a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, where _ is subscript, ^ is power. You then turn this into a set of simultaneous equations:

p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n

You convert the above into a augmented matrix, and solve for the coefficients a_0 ... a_n. Then you have a polynomial which goes through all the points, and you can now interpolate between the points.

Note however, this may not suit your purpose as it offers no way to adjust the curvature etc - you are stuck with a single solution that can not be changed.

Answer 3

Unfortunately the Lagrange or other forms of polynomial interpolation will not work on an arbitrary set of points. They only work on a set where in one dimension e.g. x

x_i < x_i+1

For an arbitary set of points, e.g. an aeroplane flight path, where each point is a (longitude, latitude) pair, you will be better off simply modelling the aeroplane's journey with current longitude & latitude and velocity. By adjusting the rate at which the aeroplane can turn (its angular velocity) depending on how close it is to the next waypoint, you can achieve a smooth curve.

The resulting curve would not be mathematically significant nor give you bezier control points. However the algorithm would be computationally simple regardless of the number of waypoints and could produce an interpolated list of points at arbitrary granularity. It would also not require you provide the complete set of points up front, you could simply add waypoints to the end of the set as required.

Answer 4

There are several algorithms for interpolating (and exrapolating) between an aribtrary (but final) set of points. You should check out numerical recipes, they also include C++ implementations of those algorithms.

Answer 5

Google "orthogonal regression".

Whereas least-squares techniques try to minimize vertical distance between the fit line and each f(x), orthogonal regression minimizes the perpendicular distances.

Addendum

In the presence of noisy data, the venerable RANSAC algorithm is worth checking out too.

Answer 6

In the 3D graphics world, NURBS are popular. Further info is easily googled.

Answer 7

The Catmull-Rom spline is guaranteed to pass through all the control points. I find this to be handier than trying to adjust intermediate control points for other types of splines.

This PDF by Christopher Twigg has a nice brief introduction to the mathematics of the spline. The best summary sentence is:

Catmull-Rom splines have C1 continuity, local control, and interpolation, but do not lie within the convex hull of their control points.

Said another way, if the points indicate a sharp bend to the right, the spline will bank left before turning to the right (there's an example picture in that document). The tightness of those turns in controllable, in this case using his tau parameter in the example matrix.

Here is another example with some downloadable DirectX code.

Answer 8

You should take a look at B-splines. Their advantage over Bezier curves is that each part is only dependent on local points. So moving a point has no effect on parts of the curve that are far away, where "far away" is determined by a parameter of the spline.

The problem with the Langrange polynomial is that adding a point can have extreme effects on seemingly arbitrary parts of the curve; there's no "localness" like described above.