30th January, 2011
Cubic spline interpolation
The following may make more sense when the latex-mathjax plugin is enabled. You’ll see the equations then, not the LaTeX source.
I’ve got a set of $(x,y)$ points. What I want to do is draw a reasonably smooth curve through all of them, rather than a set of straight lines connecting them. To do so, I need some higher order function such as a cubic. In particular the cubic Bezier function is a well known graphics primitive. Therefore, given a set of points and the definition of a cubic Bezier, I need to calculate the control points for each curve.
A cubic Bezier function interpolates between $K_0$ and $K_1$ using control points $C_{0,1}$ and $C_{0,2}$ in the following manner
$$
B(t)=(1-t)^3K_0+3t(1-t)^2C_{0,1}+3t^2(1-t)C_{0,2}+t^3K_1.
$$
We may extend the idea to a spline. The knots of the spline are $langle K_0, K_1,ldots,K_nrangle$. This leads to $n-1$ cubic functions $B_0, B_1, ldots, B_{n-1}$. Where $B_i$ interpolates between $K_i$ and $K_{i+1}$ with control points $C_{i,1}$ and $C_{i,2}$.
We want $C^2$ continuity so that our curve is nice and smooth. Therefore, for each $i$ we require
begin{eqnarray*}
B^prime_i(1)&=&B^prime_{i+1}(0)textrm{ and}\
B^{primeprime}_i(1)&=&B^{primeprime}_{i+1}(0).
end{eqnarray*}
Furthermore,
$$
B_i^prime(t)=3K_{i+1}t^2-3C_{i,2}t^2+6C_{i,2}left(1-tright)t-6C_{i,1}left(1-tright)t+3C_{i,1}left(1-tright)^2-3K_ileft(1-tright)^2
$$
and
$$
B_i^{primeprime}(t)=6 K_i (1 – t) + 6 C_{i,1} t – 12 C_{i,1} (1 – t) – 12 C_{i,2} t + 6 C_{i,2} (1 – t) + 6 K_{i+1} t.
$$
Evaluating $B^prime_i(1)$ gives
begin{eqnarray*}
B_i^prime(1)&=&3K_{i+1}1^2-3C_{i,2}1^2+6C_{i,2}left(1-1right)1-6C_{i,1}left(1-1right)1+3C_{i,1}left(1-1right)^2-3K_ileft(1-1right)^2\
&=&3K_{i+1}-3C_{i,2}+6C_{i,2}(0)1-6C_{i,1}(0)1+3C_{i,1}(0)^2-3K_i(0)^2\
&=&3K_{i+1}-3C_{i,2}.
end{eqnarray*}
and evaluating $B_{i+1}^prime(0)$ gives
begin{eqnarray*}
B_{i+1}^prime(0)&=&3K_{i+2}0^2-3C_{i+1,2}0^2+6C_{i+1,2}left(1-0right)0\
&=&-6C_{i+1,1}left(1-0right)0+3C_{i+1,1}left(1-0right)^2-3K_{i+1}left(1-0right)^2\
&=&3C_{i+1,1}-3K_{i+1}
end{eqnarray*}
Therefore, for each $i$
begin{eqnarray*}
B_i^prime(1)&=&B_{i+1}^prime(0)\
3K_{i+1}-3C_{i,2}&=&3C_{i+1,1}-3K_{i+1}\
6K_{i+1}&=&3C_{i,2}+3C_{i+1,1}\
K_{i+1}&=&0.5C_{i,2}+0.5C_{i+1,1}.
end{eqnarray*}
Evaluating $B_i^{primeprime}(1)$ gives
begin{eqnarray*}
B_i^{primeprime}(1)&=&6 K_i (1 – t) + 6 C_{i,1} t – 12 C_{i,1} (1 – t) – 12 C_{i,2} t + 6 C_{i,2} (1 – t) + 6 K_{i+1} t\
&=&6K_i(0)+6C_{i,1}-12C_{i,1}(0)-12C_{i,2}+6C_{i,2}(0)+6K_{i+1}\
&=&6C_{i,1}-12C_{i,2}+6K_{i+1}\
end{eqnarray*}
and evaluating $B_{i+1}^{primeprime}(0)$ gives
begin{eqnarray*}
B_{i+1}^{primeprime}(1)&=&6 K_{i+1} (1 – t) + 6 C_{i+1,1} t – 12 C_{i+1,1} (1 – t) – 12 C_{i+1,2} t + 6 C_{i+1,2} (1 – t) + 6 K_{i+2} t\
&=&6 K_{i+1} (1 – 0) + 6 C_{i+1,1} 0 – 12 C_{i+1,1} (1 – 0) – 12 C_{i+1,2} 0 + 6 C_{i+1,2} (1 – 0) + 6 K_{i+2} 0\
&=&6 K_{i+1} – 12 C_{i+1,1} + 6 C_{i+1,2}.
end{eqnarray*}
Therefore, for each $i$
begin{eqnarray*}
B_i^{primeprime}(1)&=&B_{i+1}^{primeprime}(0)\
6C_{i,1}-12C_{i,2}+6K_{i+1}&=&6 K_{i+1} – 12 C_{i+1,1} + 6 C_{i+1,2}\
0&=&-6C_{i,1}+12C_{i,2}-12 C_{i+1,1} + 6 C_{i+1,2}\
0&=&-C_{i,1}+2C_{i,2}-2 C_{i+1,1} + C_{i+1,2}\
end{eqnarray*}
We now have $(2times n-1)-2$ equations and $(2times n-1)$ unknown control points. We construct the linear system
$$
left(
begin{array}{ccccccc}
0&0.5&0.5&0&0&0&ldots\
-1&2&-2&1&0&0&ldots\
0&0&0&0.5&0.5&0&ldots\
0&0&-1&2&-2&1&ldots\
%0&0&0&0.5&0.5&0&ldots\
%0&0&1&-2&2&-1&ldots\
vdots&&&&&&
end{array}
right)
times
left(
begin{array}{c}
C_{0, 1}\
C_{0, 2}\
C_{1, 1}\
C_{1, 2}\
ldots
end{array}
right)
=
left(
begin{array}{c}
K_1\
0\
K_2\
0\
ldots
end{array}
right).
$$
We also have the natural boundary conditions that $B^{primeprime}_0(0)=0$ and $B_{n-1}^{primeprime}(1)=0$. The linear system then becomes
$$
left(
begin{array}{ccccccccc}
2&-1&0&0&0&0&ldots&0&0\
0&0.5&0.5&0&0&0&ldots&0&0\
-1&2&-2&1&0&0&ldots&0&0\
0&0&0&0.5&0.5&0&ldots&0&0\
0&0&-1&2&-2&1&ldots&0&0\
%0&0&0&0.5&0.5&0&ldots&0&0\
%0&0&1&-2&2&-1&ldots&0&0\
vdots&&&&&&&&\
0&0&0&0&0&0&ldots&-1&2
end{array}
right)
times
left(
begin{array}{c}
C_{0, 1}\
C_{0, 2}\
C_{1, 1}\
C_{1, 2}\
ldots
end{array}
right)
=
left(
begin{array}{c}
0\
K_1\
0\
K_2\
0\
ldots\
0
end{array}
right).
$$
Posted at 6:39 pm | Comments Off
7th January, 2011
More hills near Petra
What can I say? I like hills.
Posted at 12:00 pm | Comments Off
5th January, 2011
“The Treasury” III (Son of Treasury)
Yet another picture of the treasury.
Posted at 12:00 pm | Comments Off
3rd January, 2011
Tombs in Petra
There were so many tombs like this carved into the hillside in Petra that after a while you almost didn’t notice them and started to look instead for signs of the hidden alien spacecraft that brought the Nabataeans to our planet.
Posted at 12:00 pm | Comments Off