# Interpolation with specified end derivatives

Started by January 2, 2009
```Hi,

I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
as usual and also derivatives at both ends. I need it to be computed fast
and accurate. It should be an interpolation with minimal (or small)
curvature.

Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill
the interval 4..6 with a smooth curve joining both of them.

My first idea was to use Bezier curves. The problem is that such curve is
2D and thus based on a "t" parameter. It is useful for graphics, but here
I'd need to solve the equation for "x" which is my source parameter. It is
ugly but possible for quadratic bezier curves, but for cubic no way.
Unfortunately quadratic is not enough, consider this:
First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).

Any ideas? (Maybe it is obvious, just I don't see it)
Maybe some other interp. method...

Thanks!
dmnc
```
```On 2 Jan, 21:00, "jungledmnc" <jungled...@gmail.com> wrote:
> Hi,
>
> I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
> as usual and also derivatives at both ends. I need it to be computed fast
> and accurate. It should be an interpolation with minimal (or small)
> curvature.
>
> Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill
> the interval 4..6 with a smooth curve joining both of them.
>
> My first idea was to use Bezier curves. The problem is that such curve is
> 2D and thus based on a "t" parameter. It is useful for graphics, but here
> I'd need to solve the equation for "x" which is my source parameter. It is
> ugly but possible for quadratic bezier curves, but for cubic no way.
> Unfortunately quadratic is not enough, consider this:
> First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).
>
> Any ideas? (Maybe it is obvious, just I don't see it)
> Maybe some other interp. method...

Splines?

Rune
```
```On 2 Jan., 21:00, "jungledmnc" <jungled...@gmail.com> wrote:
> Hi,
>
> I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
> as usual and also derivatives at both ends. I need it to be computed fast
> and accurate. It should be an interpolation with minimal (or small)
> curvature.
>
> Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill
> the interval 4..6 with a smooth curve joining both of them.
>
> My first idea was to use Bezier curves. The problem is that such curve is
> 2D and thus based on a "t" parameter. It is useful for graphics, but here
> I'd need to solve the equation for "x" which is my source parameter. It is
> ugly but possible for quadratic bezier curves, but for cubic no way.
> Unfortunately quadratic is not enough, consider this:
> First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).

You didn't explicitely state it, but if you want your interpolation to
be a differentiable function, then you need at least four degrees of
the polynomial

-220+ 1715/12 x -355/12 x^2 + 95/48 x^3.

Regards,
Andor
```
```
jungledmnc wrote:

> Hi,
>
> I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
> as usual and also derivatives at both ends. I need it to be computed fast
> and accurate. It should be an interpolation with minimal (or small)
> curvature.

What is the physical meaning of this interpolation? Is it supposed to be
a waveform, or some process, or what?

> Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill
> the interval 4..6 with a smooth curve joining both of them.
>
> My first idea was to use Bezier curves.  The problem is that such curve is
> 2D and thus based on a "t" parameter. It is useful for graphics, but here
> I'd need to solve the equation for "x" which is my source parameter. It is
> ugly but possible for quadratic bezier curves, but for cubic no way.
> Unfortunately quadratic is not enough, consider this:
> First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).

You got to match two values and two derivatives -> the interpolation
should be the polynomial of the 3rd order.

> Any ideas? (Maybe it is obvious, just I don't see it)
> Maybe some other interp. method...

supposed to represent.

DSP and Mixed Signal Design Consultant
http://www.abvolt.com

```
```
jungledmnc wrote:
>
> Hi,
>
> I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
> as usual and also derivatives at both ends. I need it to be computed fast
> and accurate. It should be an interpolation with minimal (or small)
> curvature.
>
> Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill
> the interval 4..6 with a smooth curve joining both of them.
>
> My first idea was to use Bezier curves. The problem is that such curve is
> 2D and thus based on a "t" parameter. It is useful for graphics, but here
> I'd need to solve the equation for "x" which is my source parameter. It is
> ugly but possible for quadratic bezier curves, but for cubic no way.
> Unfortunately quadratic is not enough, consider this:
> First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).

Cubic beziers will do what you want quadratic won't work except in some
special cases. There are an infinite number of cubic curves that will
connect the 2 lines with tangent continuity. The bezier method is as good as
any to find the cubic you want.
As you said cubic beziers have the t parameter, but that isn't a problem
There are an infinite number of relationships between t and x creating an
infinite number of cubics that fit your criteria. But since beziers  are a
cascade of linear interpolations, if you set it up right there can be simple
relationship between x and t. To set it up right you just need to evenly
distribute the control points along x. (Look up Bernstien polynomials to see
why this is true)

This is the formula for cubic bezier.

(1-t)^3*P0+ 3*(1-t)^2*t*P1+ 3*(1-t)*t^2*P2+ t^3P3

P0-P3 are the control point locations in x and y. You can compute the x and
y location of any point on the curve for parameter t.

In your example you already have the points P0 and P3 (the start and end)
and since you want to make x evenly spaced the x values for P1 and P2 will
need to be 4.6666.. and 5.3333.. the y values can be calculated by
extrapolating the lines to the x values so in your example the y values for
P0-P3 will be [4  4.8  -.8  0]

You only need to plug the y values of your control points into the the
above formula to get the y value of the curve for any point on the curve at
t (where t is in the interval 0-1). You said the curve always goes from x=4
to x=6 so you can use this formula to calculate t from x  t=(x-4)/2.

-jim

>
> Any ideas? (Maybe it is obvious, just I don't see it)
> Maybe some other interp. method...
>
> Thanks!
> dmnc
```
```On Jan 2, 12:00&#2013266080;pm, "jungledmnc" <jungled...@gmail.com> wrote:
> Hi,
>
> I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
> as usual and also derivatives at both ends. I need it to be computed fast
> and accurate. It should be an interpolation with minimal (or small)
> curvature.
>
> Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill
> the interval 4..6 with a smooth curve joining both of them.

I would look at Numerical Recipes in C.  There is a chapter 3.3 on
cubic splines.
It is easy enough to compute a cubic curve between two points if you
the location and the derivative.  You have four equations and four
unknowns.  This can be easily solve.  The problem is what should the
derivative be at the interior points?  This is were the cubic spline
comes in handy.

Peter Nachtwey
```
```On Jan 2, 3:00&#2013266080;pm, "jungledmnc" <jungled...@gmail.com> wrote:
> Hi,
>
> I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
> as usual and also derivatives at both ends.
...
> Any ideas? (Maybe it is obvious, just I don't see it)
> Maybe some other interp. method...

i think it's called Hermite polynomial interpolation or something like
different polynomial interpolations (Lagrange vs. Hermite vs. B-
spline) for sampled audio but i can't find it.  i can't make head nor
tail out of the Wikipedia article
( http://en.wikipedia.org/wiki/Hermite_polynomials ),
but this online article appears to be what i was thinking about:

http://math.fullerton.edu/mathews/n2003/HermitePolyMod.html

r b-j

```
```>I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
>as usual and also derivatives at both ends. I need it to be computed
fast
>and accurate. It should be an interpolation with minimal (or small)
>curvature.

Hi,

Could you elaborate a little more...

1) how fast?  (real time / offline?)  define "fast".
2) how accurate?  could you specify a cost function?
3) what is "small curvature"?
is it a polynomial? is it random with a known pdf / power spectrum?... (the
more prior information, the "better" you can interpolate.)

The following quotation was displayed inside the physics lab at our high
school: "He who doesn't know what he's looking for can not understand what
he finds."  I'd hate to sound preachy, but I believe it applies here.

Emre

```
```Thanks a lot guys! I expected cubic polynomials, but I just did not know
how to satisfy my needs. I like the bezier and hermite interpolations.
Btw. the thing is there is a book about interpolation with end derivatives
so I thought it is quite complicated. So I tried to think about some weird
stuff like aligning a circle, nonlinear (sine) interpolation between two
lines defined by the derivatives and such :-))...

So thanks again! Finally something to study.

There were some questions about purpose - this should be very realtime and
there may be many purposes - audio envelopes, signal shapes...

dmnc
```
```
robert bristow-johnson wrote:
>
> On Jan 2, 3:00 pm, "jungledmnc" <jungled...@gmail.com> wrote:
> > Hi,
> >
> > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2
> > as usual and also derivatives at both ends.
> ...
> > Any ideas? (Maybe it is obvious, just I don't see it)
> > Maybe some other interp. method...
>
> i think it's called Hermite polynomial interpolation or something like
> different polynomial interpolations (Lagrange vs. Hermite vs. B-
> spline) for sampled audio but i can't find it.  i can't make head nor
> tail out of the Wikipedia article
>    ( http://en.wikipedia.org/wiki/Hermite_polynomials ),

Cubic Hermite spline is what you are looking for. This would be the
wikipedia entry:

http://en.wikipedia.org/wiki/Catmull-Rom_spline#Catmull.E2.80.93Rom_spline

The cubic hermite is identical to the cubic Bezier I gave in my previous
post. To get from the Bezier to Hermite you would simply need to substitute
control points and tangent vectors like this:

Hermite      Bezier
P0           P0
P1           P3
M0           3(P1-P0)
M1           3(p3-P2)

Plug those substitutions in and rearrange and simplify and the Bezier
becomes the Hermite.

To get from his x to the Hermite t parameter you would still need to convert
with the same formula t=(x-4)/2

-jim

> but this online article appears to be what i was thinking about:
>
>   http://math.fullerton.edu/mathews/n2003/HermitePolyMod.html

>
> r b-j
```