CSCE 441 Lecture 29

« previous | Monday, March 31, 2014 | next »

No class Wednesday

Smooth Curves

Represented as polynomials: $p(t)=\left(x(t),y(t)\right)$

Power Basis

${\begin{cases}x(t)&=a+b\,t+c\,t^{2}+d\,t^{3}+\dots \\y(t)&=e+f\,t+g\,t^{2}+h\,t^{3}+\dots \end{cases}}$

We can mess with coefficients, but it's hard to predict what the shape will look like just by modifiying coefficients.

Not intuitive.

Interpolation

Find a polynomial that passes through the specified values

$y(t)=a+b\,t+c\,t^{2}+d\,t^{3}$

${\begin{aligned}y(0)&=a=3\\y(1)&=a+b+c+d=1\\y(2)&=\ldots \end{aligned}}$

Interpolate for each component $x$ and $y$ .

Lagrange Interpolation

Identical to matrix method, but uses a (recursive) geometric construction

Start with line from $y_{0}$ to $y_{1}$ : $f(t)=(1-t)\,y_{0}+t\,y_{1}$

Add line from $y_{1}$ to $y_{2}$ : $g(t)=(2-t)\,y_{1}+(t-1)\,y_{2}$

What about quadratic?

Find linear interpolation between two points: given points $t_{0}$ and $t_{1}$ with values $y_{0}$ and $y_{1}$ , respectively, the linear interpolation of $y$ over $t$ is given by

$y(t)={\frac {(t_{1}-t)\,y_{0}+(t-t_{0})\,y_{1}}{t_{1}-t_{0}}}$

In our example, $h(t)={\frac {(2-t)\,f(t)-t\,g(t)}{2}}$

What about cubic through 4 points?

find quadratic of first 3 points
find quadratic of last 3 points
find linear interpolation of both functions

Basis: linear interpolation between two points

Induction:

Assume we have points $y_{i},\ldots ,y_{n+1+i}$
Build polynomial interpolating polynomials $f(t)$ , $g(t)$ of degree $n$ for $y_{i},\ldots ,y_{n+1}$ and $y_{i+1},\ldots ,y_{n+1+i}$
$h(t)={\frac {(n+1+i-t)\,f(t)+(t-i)\,g(t)}{n+1}}$