This page was generated from doc/euclidean/end-conditions-natural.ipynb. Interactive online version: Binder badge.

Natural End Conditions#

For the first and last segment, we assume that the inner tangent is known. To find the outer tangent according to natural end conditions, the second derivative is set to \(0\) at the beginning and end of the curve.

We are looking only at the non-uniform case here, it’s easy to get to the uniform case by setting \(\Delta_i = 1\).

Natural end conditions are naturally a good fit for natural splines. And in case you were wondering, natural end conditions are sometimes also called “relaxed” end conditions.

[1]:
import sympy as sp
sp.init_printing(order='grevlex')

As usual, we are getting some help from utility.py:

[2]:
from utility import NamedExpression
[3]:
t = sp.symbols('t')

Begin#

We are starting with the first polynomial segment \(\boldsymbol{p}_0(t)\), with \(t_0 \le t \le t_1\).

[4]:
t0, t1 = sp.symbols('t:2')

The coefficients …

[5]:
a0, b0, c0, d0 = sp.symbols('a:dbm0')

… multiplied with the monomial basis give us the uniform polynomial …

[6]:
d0 * t**3 + c0 * t**2 + b0 * t + a0
[6]:
$\displaystyle \boldsymbol{d}_{0} t^{3} + \boldsymbol{c}_{0} t^{2} + \boldsymbol{b}_{0} t + \boldsymbol{a}_{0}$

… which we re-scale to the desired parameter range:

[7]:
p0 = NamedExpression('pbm0', _.subs(t, (t - t0) / (t1 - t0)))
p0
[7]:
$\displaystyle \boldsymbol{p}_{0} = \frac{\boldsymbol{d}_{0} \left(t - t_{0}\right)^{3}}{\left(- t_{0} + t_{1}\right)^{3}} + \frac{\boldsymbol{c}_{0} \left(t - t_{0}\right)^{2}}{\left(- t_{0} + t_{1}\right)^{2}} + \frac{\boldsymbol{b}_{0} \left(t - t_{0}\right)}{- t_{0} + t_{1}} + \boldsymbol{a}_{0}$

We need the first derivative (a.k.a. velocity, a.k.a. tangent vector):

[8]:
pd0 = p0.diff(t)
pd0
[8]:
$\displaystyle \frac{d}{d t} \boldsymbol{p}_{0} = \frac{3 \boldsymbol{d}_{0} \left(t - t_{0}\right)^{2}}{\left(- t_{0} + t_{1}\right)^{3}} + \frac{\boldsymbol{c}_{0} \cdot \left(2 t - 2 t_{0}\right)}{\left(- t_{0} + t_{1}\right)^{2}} + \frac{\boldsymbol{b}_{0}}{- t_{0} + t_{1}}$

Similar to the notebook about non-uniform Hermite splines, we are interested in the function values and first derivatives at the control points:

\begin{align*} \boldsymbol{x}_0 &= \boldsymbol{p}_0(t_0)\\ \boldsymbol{x}_1 &= \boldsymbol{p}_0(t_1)\\ \boldsymbol{\dot{x}}_0 &= \boldsymbol{p}_0'(t_0)\\ \boldsymbol{\dot{x}}_1 &= \boldsymbol{p}_0'(t_1) \end{align*}

[9]:
equations_begin = [
    p0.evaluated_at(t, t0).with_name('xbm0'),
    p0.evaluated_at(t, t1).with_name('xbm1'),
    pd0.evaluated_at(t, t0).with_name('xdotbm0'),
    pd0.evaluated_at(t, t1).with_name('xdotbm1'),
]

To get simpler equations, we are substituting \(\Delta_0 = t_1 - t_0\). Note that this is only for display purposes, the calculations are still done with \(t_i\).

[10]:
delta_begin = [
    (t0, 0),
    (t1, sp.Symbol('Delta0')),
]
[11]:
for e in equations_begin:
    display(e.subs(delta_begin))
$\displaystyle \boldsymbol{x}_{0} = \boldsymbol{a}_{0}$
$\displaystyle \boldsymbol{x}_{1} = \boldsymbol{a}_{0} + \boldsymbol{b}_{0} + \boldsymbol{c}_{0} + \boldsymbol{d}_{0}$
$\displaystyle \boldsymbol{\dot{x}}_{0} = \frac{\boldsymbol{b}_{0}}{\Delta_{0}}$
$\displaystyle \boldsymbol{\dot{x}}_{1} = \frac{\boldsymbol{b}_{0}}{\Delta_{0}} + \frac{2 \boldsymbol{c}_{0}}{\Delta_{0}} + \frac{3 \boldsymbol{d}_{0}}{\Delta_{0}}$
[12]:
coefficients_begin = sp.solve(equations_begin, [a0, b0, c0, d0])
[13]:
for c, e in coefficients_begin.items():
    display(NamedExpression(c, e.subs(delta_begin)))
$\displaystyle \boldsymbol{a}_{0} = \boldsymbol{x}_{0}$
$\displaystyle \boldsymbol{b}_{0} = \Delta_{0} \boldsymbol{\dot{x}}_{0}$
$\displaystyle \boldsymbol{c}_{0} = - 2 \Delta_{0} \boldsymbol{\dot{x}}_{0} - \Delta_{0} \boldsymbol{\dot{x}}_{1} - 3 \boldsymbol{x}_{0} + 3 \boldsymbol{x}_{1}$
$\displaystyle \boldsymbol{d}_{0} = \Delta_{0} \boldsymbol{\dot{x}}_{0} + \Delta_{0} \boldsymbol{\dot{x}}_{1} + 2 \boldsymbol{x}_{0} - 2 \boldsymbol{x}_{1}$

The second derivative (a.k.a. acceleration) …

[14]:
pdd0 = pd0.diff(t)
pdd0
[14]:
$\displaystyle \frac{d^{2}}{d t^{2}} \boldsymbol{p}_{0} = \frac{3 \boldsymbol{d}_{0} \cdot \left(2 t - 2 t_{0}\right)}{\left(- t_{0} + t_{1}\right)^{3}} + \frac{2 \boldsymbol{c}_{0}}{\left(- t_{0} + t_{1}\right)^{2}}$

… at the beginning of the curve (\(t = t_0\)) …

[15]:
pdd0.evaluated_at(t, t0)
[15]:
$\displaystyle \left.{\frac{d^{2}}{d t^{2}} \boldsymbol{p}_{0}}\right\rvert_{t=t_{0}} = \frac{2 \boldsymbol{c}_{0}}{\left(- t_{0} + t_{1}\right)^{2}}$

… is set to zero …

[16]:
sp.Eq(_.expr, 0).subs(coefficients_begin)
[16]:
$\displaystyle \frac{2 \cdot \left(2 t_{0} \boldsymbol{\dot{x}}_{0} - 2 t_{1} \boldsymbol{\dot{x}}_{0} + t_{0} \boldsymbol{\dot{x}}_{1} - t_{1} \boldsymbol{\dot{x}}_{1} - 3 \boldsymbol{x}_{0} + 3 \boldsymbol{x}_{1}\right)}{\left(- t_{0} + t_{1}\right)^{2}} = 0$

… leading to an expression for the initial tangent vector:

[17]:
xd0 = NamedExpression.solve(_, 'xdotbm0')
xd0.subs(delta_begin)
[17]:
$\displaystyle \boldsymbol{\dot{x}}_{0} = - \frac{\Delta_{0} \boldsymbol{\dot{x}}_{1} + 3 \boldsymbol{x}_{0} - 3 \boldsymbol{x}_{1}}{2 \Delta_{0}}$

This can also be written as

\begin{equation*} \boldsymbol{\dot{x}}_0 = \frac{3 \left(\boldsymbol{x}_1 - \boldsymbol{x}_0\right)}{2 \Delta_0} - \frac{\boldsymbol{\dot{x}}_1}{2}. \end{equation*}

End#

If a spline has \(N\) vertices, it has \(N-1\) polynomial segments and the last polynomial segment is \(\boldsymbol{p}_{N-2}(t)\), with \(t_{N-2} \le t \le t_{N-1}\). To simplify the notation a bit, let’s assume we have \(N = 10\) vertices, which makes \(\boldsymbol{p}_8\) the last polynomial segment. The following steps are very similar to the above derivation of the start conditions.

[18]:
a8, b8, c8, d8 = sp.symbols('a:dbm8')
[19]:
t8, t9 = sp.symbols('t8:10')
[20]:
d8 * t**3 + c8 * t**2 + b8 * t + a8
[20]:
$\displaystyle \boldsymbol{d}_{8} t^{3} + \boldsymbol{c}_{8} t^{2} + \boldsymbol{b}_{8} t + \boldsymbol{a}_{8}$
[21]:
p8 = NamedExpression('pbm8', _.subs(t, (t - t8) / (t9 - t8)))
p8
[21]:
$\displaystyle \boldsymbol{p}_{8} = \frac{\boldsymbol{d}_{8} \left(t - t_{8}\right)^{3}}{\left(- t_{8} + t_{9}\right)^{3}} + \frac{\boldsymbol{c}_{8} \left(t - t_{8}\right)^{2}}{\left(- t_{8} + t_{9}\right)^{2}} + \frac{\boldsymbol{b}_{8} \left(t - t_{8}\right)}{- t_{8} + t_{9}} + \boldsymbol{a}_{8}$
[22]:
pd8 = p8.diff(t)
pd8
[22]:
$\displaystyle \frac{d}{d t} \boldsymbol{p}_{8} = \frac{3 \boldsymbol{d}_{8} \left(t - t_{8}\right)^{2}}{\left(- t_{8} + t_{9}\right)^{3}} + \frac{\boldsymbol{c}_{8} \cdot \left(2 t - 2 t_{8}\right)}{\left(- t_{8} + t_{9}\right)^{2}} + \frac{\boldsymbol{b}_{8}}{- t_{8} + t_{9}}$

\begin{align*} \boldsymbol{x}_{N-2} &= \boldsymbol{p}_{N-2}(t_{N-2})\\ \boldsymbol{x}_{N-1} &= \boldsymbol{p}_{N-2}(t_{N-1})\\ \boldsymbol{\dot{x}}_{N-2} &= \boldsymbol{p}_{N-2}'(t_{N-2})\\ \boldsymbol{\dot{x}}_{N-1} &= \boldsymbol{p}_{N-2}'(t_{N-1}) \end{align*}

[23]:
equations_end = [
    p8.evaluated_at(t, t8).with_name('xbm8'),
    p8.evaluated_at(t, t9).with_name('xbm9'),
    pd8.evaluated_at(t, t8).with_name('xdotbm8'),
    pd8.evaluated_at(t, t9).with_name('xdotbm9'),
]

We define \(\Delta_8 = t_9 - t_8\):

[24]:
delta_end = [
    (t8, 0),
    (t9, sp.Symbol('Delta8')),
]
[25]:
for e in equations_end:
    display(e.subs(delta_end))
$\displaystyle \boldsymbol{x}_{8} = \boldsymbol{a}_{8}$
$\displaystyle \boldsymbol{x}_{9} = \boldsymbol{a}_{8} + \boldsymbol{b}_{8} + \boldsymbol{c}_{8} + \boldsymbol{d}_{8}$
$\displaystyle \boldsymbol{\dot{x}}_{8} = \frac{\boldsymbol{b}_{8}}{\Delta_{8}}$
$\displaystyle \boldsymbol{\dot{x}}_{9} = \frac{\boldsymbol{b}_{8}}{\Delta_{8}} + \frac{2 \boldsymbol{c}_{8}}{\Delta_{8}} + \frac{3 \boldsymbol{d}_{8}}{\Delta_{8}}$
[26]:
coefficients_end = sp.solve(equations_end, [a8, b8, c8, d8])
[27]:
for c, e in coefficients_end.items():
    display(NamedExpression(c, e.subs(delta_end)))
$\displaystyle \boldsymbol{a}_{8} = \boldsymbol{x}_{8}$
$\displaystyle \boldsymbol{b}_{8} = \Delta_{8} \boldsymbol{\dot{x}}_{8}$
$\displaystyle \boldsymbol{c}_{8} = - 2 \Delta_{8} \boldsymbol{\dot{x}}_{8} - \Delta_{8} \boldsymbol{\dot{x}}_{9} - 3 \boldsymbol{x}_{8} + 3 \boldsymbol{x}_{9}$
$\displaystyle \boldsymbol{d}_{8} = \Delta_{8} \boldsymbol{\dot{x}}_{8} + \Delta_{8} \boldsymbol{\dot{x}}_{9} + 2 \boldsymbol{x}_{8} - 2 \boldsymbol{x}_{9}$

This time, the second derivative …

[28]:
pdd8 = pd8.diff(t)
pdd8
[28]:
$\displaystyle \frac{d^{2}}{d t^{2}} \boldsymbol{p}_{8} = \frac{3 \boldsymbol{d}_{8} \cdot \left(2 t - 2 t_{8}\right)}{\left(- t_{8} + t_{9}\right)^{3}} + \frac{2 \boldsymbol{c}_{8}}{\left(- t_{8} + t_{9}\right)^{2}}$

at the end of the last segment (\(t = t_9\)) …

[29]:
pdd8.evaluated_at(t, t9)
[29]:
$\displaystyle \left.{\frac{d^{2}}{d t^{2}} \boldsymbol{p}_{8}}\right\rvert_{t=t_{9}} = \frac{3 \boldsymbol{d}_{8} \left(- 2 t_{8} + 2 t_{9}\right)}{\left(- t_{8} + t_{9}\right)^{3}} + \frac{2 \boldsymbol{c}_{8}}{\left(- t_{8} + t_{9}\right)^{2}}$

… is set to zero …

[30]:
sp.Eq(_.expr, 0).subs(coefficients_end)
[30]:
$\displaystyle \frac{3 \left(- 2 t_{8} + 2 t_{9}\right) \left(- t_{8} \boldsymbol{\dot{x}}_{8} + t_{9} \boldsymbol{\dot{x}}_{8} - t_{8} \boldsymbol{\dot{x}}_{9} + t_{9} \boldsymbol{\dot{x}}_{9} + 2 \boldsymbol{x}_{8} - 2 \boldsymbol{x}_{9}\right)}{\left(- t_{8} + t_{9}\right)^{3}} + \frac{2 \cdot \left(2 t_{8} \boldsymbol{\dot{x}}_{8} - 2 t_{9} \boldsymbol{\dot{x}}_{8} + t_{8} \boldsymbol{\dot{x}}_{9} - t_{9} \boldsymbol{\dot{x}}_{9} - 3 \boldsymbol{x}_{8} + 3 \boldsymbol{x}_{9}\right)}{\left(- t_{8} + t_{9}\right)^{2}} = 0$

… leading to an expression for the final tangent vector:

[31]:
xd9 = NamedExpression.solve(_, 'xdotbm9')
xd9.subs(delta_end)
[31]:
$\displaystyle \boldsymbol{\dot{x}}_{9} = - \frac{\Delta_{8} \boldsymbol{\dot{x}}_{8} + 3 \boldsymbol{x}_{8} - 3 \boldsymbol{x}_{9}}{2 \Delta_{8}}$

Luckily, that’s symmetric to the result we got above.

The equation can be generalized to

\begin{equation*} \boldsymbol{\dot{x}}_{N-1} = \frac{3 \left(\boldsymbol{x}_{N-1} - \boldsymbol{x}_{N-2}\right)}{2 \Delta_{N-2}} - \frac{\boldsymbol{\dot{x}}_{N-2}}{2}. \end{equation*}

Example#

We are showing a one-dimensional example where 3 time/value pairs are given. The slope for the middle value is given, the begin and end slopes are calculated using the “natural” end conditions as calculated above.

[32]:
values = 2, 2, 1
times = 0, 4, 5
slope = 2

We are using a few helper functions from helper.py for plotting:

[33]:
from helper import plot_sympy, grid_lines
[34]:
x0, x1 = sp.symbols('xbm0:2')
x8, x9 = sp.symbols('xbm8:10')
xd1 = sp.symbols('xdotbm1')
xd8 = sp.symbols('xdotbm8')
[35]:
begin = p0.subs(coefficients_begin).subs_symbols(xd0).subs({
    t0: times[0],
    t1: times[1],
    x0: values[0],
    x1: values[1],
    xd1: slope,
}).with_name(r'p_\text{begin}')
end = p8.subs(coefficients_end).subs_symbols(xd9).subs({
    t8: times[1],
    t9: times[2],
    x8: values[1],
    x9: values[2],
    xd8: slope,
}).with_name(r'p_\text{end}')
[36]:
plot_sympy(
    (begin.expr, (t, times[0], times[1])),
    (end.expr, (t, times[1], times[2])))
grid_lines(times, [1, 2])
../_images/euclidean_end-conditions-natural_63_0.svg
[37]:
begin.diff(t).evaluated_at(t, times[0])
[37]:
$\displaystyle \left.{\frac{d}{d t} p_\text{begin}}\right\rvert_{t=0} = -1$
[38]:
end.diff(t).evaluated_at(t, times[-1])
[38]:
$\displaystyle \left.{\frac{d}{d t} p_\text{end}}\right\rvert_{t=5} = - \frac{5}{2}$

Bézier Control Points#

Up to now we have assumed that we know one of the tangent vectors and want to find the other tangent vector in order to construct a Hermite spline. What if we want to construct a Bézier spline instead?

If the inner Bézier control points \(\boldsymbol{\tilde{x}}_1^{(-)}\) and \(\boldsymbol{\tilde{x}}_{N-2}^{(+)}\) are given, we can insert the equations for the tangent vectors from the notebook about non-uniform Bézier splines into our tangent vector equations from above and solve them for the outer control points \(\boldsymbol{\tilde{x}}_0^{(+)}\) and \(\boldsymbol{\tilde{x}}_{N-1}^{(-)}\), respectively.

[39]:
xtilde0, xtilde1 = sp.symbols('xtildebm0^(+) xtildebm1^(-)')
[40]:
NamedExpression.solve(xd0.subs({
    xd0.name: 3 * (xtilde0 - x0) / (t1 - t0),
    xd1: 3 * (x1 - xtilde1) / (t1 - t0),
}), xtilde0)
[40]:
$\displaystyle \boldsymbol{\tilde{x}}^{(+)}_{0} = \frac{\boldsymbol{x}_{0}}{2} + \frac{\boldsymbol{\tilde{x}}^{(-)}_{1}}{2}$
[41]:
xtilde8, xtilde9 = sp.symbols('xtildebm8^(+) xtildebm9^(-)')
[42]:
NamedExpression.solve(xd9.subs({
    xd8: 3 * (xtilde8 - x8) / (t9 - t8),
    xd9.name: 3 * (x9 - xtilde9) / (t9 - t8),
}), xtilde9)
[42]:
$\displaystyle \boldsymbol{\tilde{x}}^{(-)}_{9} = \frac{\boldsymbol{x}_{9}}{2} + \frac{\boldsymbol{\tilde{x}}^{(+)}_{8}}{2}$

Note that all \(\Delta_i\) cancel each other out (as well as the inner vertices \(\boldsymbol{x}_1\) and \(\boldsymbol{x}_{N-2}\)) and we get very simple equations for the “natural” end conditions:

\begin{align*} \boldsymbol{\tilde{x}}_0^{(+)} &= \frac{\boldsymbol{x}_0 + \boldsymbol{\tilde{x}}_1^{(-)}}{2} \\ \boldsymbol{\tilde{x}}_{N-1}^{(-)} &= \frac{\boldsymbol{x}_{N-1} + \boldsymbol{\tilde{x}}_{N-2}^{(+)}}{2} \end{align*}