Interpolating Lagrange curve

Interpolating curves are designed to run through all given points. The Bezier curve, for instance, goes through its endpoints only, because at the parameter values corresponding to the endpoints (t =0, t = 1) all the basis functions are zero except the first and last, which are one. Thus P(0) = P0 and P(1) = Pn are exactly the control points.

In order to get Lagrange interpolating curve
    P(t) = ∑i=0,n Lin(t) Pi      (*)
the i-th basis function at some parameter ti must be one, and all others must be zero. This particular value of the parameter t is associated with each interpolating point Pi and is called knot. Lagrange polynomials will give the interpolation property for all points:
    Lin(t) = (t - t0)(t - t1)... (t - ti-1)(t - ti+1)...(t - tn) / (ti - t0)(ti - t1)... (ti - ti-1)(ti - ti+1)... (ti - tn)
    Lin(ti ) = 1,     Lin(tk ) = 0

Quadratic Lagrange curve

Interactive Lagrange applet.
Drag the mouse to move the nearest Lagrange control point (a small blue square in the left window) or knot (a small black square in the right window). In the right applet window you see basis Lagrange polynomials. Move a knot to see how it influences on spline shape and basis functions. As since 0 <= t <= 1 you will get an extrapolating curves if t0 > 0 or tn < 1.

Cubic Lagrange curve

Note that Lagrange curves are not contained in the convex hull of its control points.

Aitken algorithm

The analogue of the de Casteljau algorithm in the case of Lagrange curves is the Aitken algorithm
    Pij = Pij-1 (ti+j - t) / (ti+j - ti) + Pi+1j-1 (t - ti) / (ti+j - ti) ,     j = 1, n     i = 0, n-j .
However formula (*) and stored array of basis functions are used in These polynomials were calculated earlier for the right window as

   for (i = 0; i < N; i++){
     P = 1;
     for (j = 0; j < N; j++)
       if (j != i) P = P*(t-ti[j])/(ti[i] - ti[j]);

Oscillations of Lagrange curves

As Lagrange polynomials oscillate between its roots (knots), therefore they can take negative values. Unfortunately these oscillations grow quickly with n increasing. You see below these oscillations in an interpolating curve of n = 7 degree. Compare Lagrange and Bezier (lower picture) curves too.

Therefore Lagrange interpolation is useless for complex curves with large n values. But further we will compose an interpolating spline of cubic Bezier segments joined smoothly.

Contents   Previous: More Bezier splines Math   Next: Interpolating Cardinal splines
updated 24 June 2001