Back to November Calendar            ←Previous Entry                             Next Entry→

November 20, 2005

Spline Representations XII

 

Augmenting an irregular spline to show it’s inconstant...and the derivation of the Hildebrand parameterization formulas.

 

Yesterday, we constructed a natural spline on irregularly spaced points ABCD.

 

What if we add point E to the mix?  We’d need to add a new function

                                  

The condition that  will be replaced by the condition that  and we’ll have three new conditions: ,  and .

                  

In MatLab, I enter the 11x12 augmented coefficient matrix like so:

 

>> A=[216 6 0 0 0 0 0 0 0 0 0 7; 0 0 1728 144 12 0 0 0 0 0 0 -9; 0 0 0 0 0 8 4 2 0 0 0 11; 108 1 0 0 -1 0 0 0 0 0 0 0; 0 0 432 24 1 0 0 -1 0 0 0 0; 36 0 0 -2 0 0 0 0 0 0 0 0; 0 0 72 2 0 0 -2 0 0 0 0 0;0 0 0 0 0 48 2 0 0 -2 0 0; 0 0 0 0 0 0 0 0 64 16 4 -3;0 0 0 0 0 12 4 1 0 0 -1 0; 0 0 0 0 0 0 0 0 24 2 0 0];

 

Solve the system like so:

>> B = rref(A);

>> c12=B(:,12)

c12 =

   -0.0248

    2.0599

    0.0363

   -0.4466

   -0.6198

   -0.1426

    0.8607

    4.3490

    0.2135

   -2.5615

    6.0806

 

>> bin_1=[1 6];

>> bin_3=[1 -12];

>> bin_4=[1 -14];

>> bi_square_1 = conv(bin_1,bin_1);

>> bi_square_3 = conv(bin_3,bin_3);

>> bi_square_4 = conv(bin_4,bin_4);

>> bi_cube_1 = conv(bin_1,bi_square_1);

>> bi_cube_3 = conv(bin_3,bi_square_3);

>> bi_cube_4 = conv(bin_4,bi_square_4);

 

Pad out the vectors to be compatible:

>> bin_1=[0 0 bin_1];

>> bin_3=[0 0 bin_3];

>> bin_4=[0 0 bin_4];

>> bi_square_1 = [0 bi_square_1];

>> bi_square_3 = [0 bi_square_3];

>> bi_square_4 = [0 bi_square_4];

 

and build the standard coefficient array for each cubic spline:

>> spline1=c12(1)*bi_cube_1+c12(2)*bin_1+[0 0 0 -7]

spline1 =

   -0.0248   -0.4463   -0.6178    0.0041

>> spline2 = [c12(3) c12(4) c12(5) 0]

spline2 =

    0.0363   -0.4466   -0.6198         0

>> spline3=c12(6)*bi_cube_3+c12(7)*bi_square_3+c12(8)*bin_3+[0 0 0 -9]

spline3 =

   -0.1426    5.9939  -77.9052  309.1405

>> spline4=c12(9)*bi_cube_4+c12(10)*bi_square_4+c12(11)*bin_4+[0 0 0 2]

spline4 =

  1.0e+003 *

    0.0002   -0.0115    0.2033   -1.1710

 

And then plot:

>> x1=-6:.1:0;

>> x2=0:.1:12;

>> x3=12:.1:14;

>> x4=14:.1:18;

>> figure

>> plot(x1,polyval(spline1,x1),
        x2,polyval(spline2,x2),
        x3,polyval(spline3,x3),
        x4,polyval(spline4,x4),'LineWidth',2)

>> hold on

>> plot([-6 0 12 14 18],[-7 0 -9 2 -1],'o')

To compare these, we superimpose the first graph on this:

Do you see the difference in the BC splines grinning out at you?

 

To see how the Hildebrand parameterization doesn’t suffer this vicissitude, let’s take up his outline of the algorithm for generating a smooth curve through the points Pk and Pk+1.

  1. fit one quadratic curve, , through points Pk-1, Pk and Pk+1 ;
  2. fit another quadratic curve, , through points Pk, Pk+1 and Pk+2 ;
  3. form a weighted combination of these curves to get the parametric equations for curve Ck.

 

Let’s flesh this out a bit.

 

In order to carry out the first two steps, we seek a parameteriations

(1.1)                   

 

and

(1.2)                    

 

These are the conditions we need to meet

(1.3)                             

Combining equations 1.1, 1.2 and 1.3, we get

(1.4)                                          

These are pretty easy to solve for the x coefficients:

(1.5)                             

and by symmetry, the y coefficients have exactly the same form

(1.6)                            

So given a set of four (x, y) coordinate pairs, we can plug them into the above formulas to get the quadratic parameterizations and then weight these on  to get cubic parameterizations like so

(1.7)                                         

These can simplified by doing a little expansion/collection like so

(1.8)                             

This is still on the interval for t in [0, 1].

 

It remains to figure out what to do about the first and last intervals.

 

If the curve is not closed, don’t bother computing a new curve, just use  for the first leg and and  for the last leg: they meet the conditions and they’re as smooth as a baby goat’s bottom. 

 

If the curve is closed, find the parameterization through P1 and P2  by using k = 1 equations 1.8 with  and, similarly, use k = n1 in 1.8 with   Pn2  and Pn1.  Finally, again use 1.8 with k = n,  and .