<jupyter_start><jupyter_text>This notebook is part of https://github.com/AudioSceneDescriptionFormat/splines, see also https://splines.readthedocs.io/.[back to overview](catmull-rom.ipynb)  Properties of Catmull--Rom SplinesCatmull and Rom (1974)presents a whole class of splines with a whole range of properties.Here we only consider one member of this class which isa cubic polynomial interpolating spline with $C^1$ continuity and local support.Nowadays, this specific case is typically simply referred to as*Catmull--Rom spline*.This type of splines is very popular because they are very easy to use.Only a sequence of control points has to be specified, the tangents are calculated automatically from the given points.Using those tangents, the spline can be implemented usingcubic [Hermite splines](hermite.ipynb).Alternatively, spline values can be directly calculatedwith the [Barry--Goldman algorithm](catmull-rom-barry-goldman.ipynb).To calculate the spline values between two control points,the preceding and the following control points are needed as well.The tangent vector at any given control pointcan be calculated from this control point,its predecessor and its successor.Since Catmull--Rom splines are $C^1$ continuous,incoming and outgoing tangent vectors are equal. The following examples use the Python class[splines.CatmullRom](../python-module/splines.rstsplines.CatmullRom)to create both uniform and non-uniform splines.Only closed splines are shown,other [end conditions](end-conditions.ipynb)can also be used, but they are not specific to this type of spline.<jupyter_code>import matplotlib.pyplot as plt
import numpy as np
np.set_printoptions(precision=4)<jupyter_output><empty_output><jupyter_text>Apart from the [splines](../python-module/splines.rst) module ...<jupyter_code>import splines<jupyter_output><empty_output><jupyter_text>... we also import a few helper functions from [helper.py](helper.py):<jupyter_code>from helper import plot_spline_2d, plot_tangent_2d<jupyter_output><empty_output><jupyter_text>Let's choose a few points for an example:<jupyter_code>points1 = [
    (-1, -0.5),
    (0, 2.3),
    (1, 1),
    (4, 1.3),
    (3.8, -0.2),
    (2.5, 0.1),
]<jupyter_output><empty_output><jupyter_text>Without specifying any time values,we get a uniform spline:<jupyter_code>s1 = splines.CatmullRom(points1, endconditions='closed')
fig, ax = plt.subplots()
plot_spline_2d(s1, ax=ax)<jupyter_output><empty_output><jupyter_text>Tangent VectorsIn the uniform case,the tangent vectors at any given control pointare parallel to the line connecting the preceding point and the following point.The tangent vector has the same orientation as that linebut only half its length.In other (more mathematical) words:\begin{equation*}\boldsymbol{\dot{x}}_i = \frac{\boldsymbol{x}_{i+1} - \boldsymbol{x}_{i-1}}{2}\end{equation*}This is illustrated for two control points in the following plot:<jupyter_code>for idx, color in zip([2, 5], ['purple', 'hotpink']):
    plot_tangent_2d(
        s1.evaluate(s1.grid[idx], 1),
        s1.evaluate(s1.grid[idx]), color=color, ax=ax)
    ax.plot(
        *s1.evaluate([s1.grid[idx - 1], s1.grid[idx + 1]]).T,
        '--', color=color, linewidth=2)
fig<jupyter_output><empty_output><jupyter_text>We can see here that each tangent vector is parallel toand has half the length ofthe line connecting the preceding and the following vertex,just as promised.However, this will not be true anymoreif we are using non-uniform time instances:<jupyter_code>times2 = 0, 1, 2.2, 3, 4, 4.5, 6
s2 = splines.CatmullRom(points1, grid=times2, endconditions='closed')
plot_spline_2d(s2, ax=ax)
for idx, color in zip([2, 5], ['green', 'crimson']):
    plot_tangent_2d(
        s2.evaluate(s2.grid[idx], 1),
        s2.evaluate(s2.grid[idx]), color=color, ax=ax)
fig<jupyter_output><empty_output><jupyter_text>In the non-uniform case,the equation for the tangent vector gets quite a bit more complicated:\begin{equation*}\boldsymbol{\dot{x}}_i =\frac{(t_{i+1} - t_i)^2 (\boldsymbol{x}_i - \boldsymbol{x}_{i-1}) +(t_i - t_{i-1})^2 (\boldsymbol{x}_{i+1} - \boldsymbol{x}_i)}{(t_{i+1} - t_i)(t_i - t_{i-1})(t_{i+1} - t_{i-1})}\end{equation*} Equivalently, this can be written as:\begin{equation*}\boldsymbol{\dot{x}}_i =\frac{(t_{i+1} - t_i) (\boldsymbol{x}_i - \boldsymbol{x}_{i-1})}{(t_i - t_{i-1})(t_{i+1} - t_{i-1})}+\frac{(t_i - t_{i-1}) (\boldsymbol{x}_{i+1} - \boldsymbol{x}_i)}{(t_{i+1} - t_i)(t_{i+1} - t_{i-1})}\end{equation*} The derivation of this equation is shown in[a separate notebook](catmull-rom-non-uniform.ipynbTangent-Vectors). Some sources provide a simpler equationwhich is different from the tangent vector of a Catmull--Rom spline(except in the uniform case):\begin{equation*}\boldsymbol{\dot{x}}_i \overset{?}{=} \frac{1}{2} \left(\frac{\boldsymbol{x}_i - \boldsymbol{x}_{i-1}}{t_i - t_{i-1}} +\frac{\boldsymbol{x}_{i + 1} - \boldsymbol{x}_i}{t_{i + 1} - t_i}\right)\end{equation*} There are even sources(e.g. [Wikipedia](https://en.wikipedia.org/wiki/Cubic_Hermite_splineCatmull%E2%80%93Rom_spline))which show yet a simpler equation,which has even less to do with Catmull--Rom splines(except in the uniform case):\begin{equation*}\boldsymbol{\dot{x}}_i \overset{?}{=} \frac{\boldsymbol{x}_{i + 1} - \boldsymbol{x}_{i - 1}}{t_{i + 1} - t_{i - 1}}\end{equation*}  Cusps and Self-IntersectionsUniform parametrization typically works very wellif the (Euclidean) distances between consecutive vertices are all similar.However, if the distances are very different,the shape of the spline often turns out to be unexpected.Most notably,in extreme cases there might be even cusps or self-intersectionswithin a spline segment.<jupyter_code>def plot_catmull_rom(*args, **kwargs):
    plot_spline_2d(splines.CatmullRom(*args, endconditions='closed', **kwargs))
points3 = [
    (0, 0),
    (0, 0.5),
    (1.5, 1.5),
    (1.6, 1.5),
    (3, 0.2),
    (3, 0),
]
plot_catmull_rom(points3)<jupyter_output><empty_output><jupyter_text>We can try to compensate thisby manually selecting some non-uniform time instances:<jupyter_code>times3 = 0, 0.2, 0.9, 1, 3, 3.3, 4.5
plot_catmull_rom(points3, times3)<jupyter_output><empty_output><jupyter_text>Time values can be chosen by trial and error,but there are also ways to choose the time values automatically,as shown in the following sections.  Chordal ParameterizationOne way to go about this is to measure the (Euclidean) distancesbetween consecutive vertices (i.e. the "chordal lengths")and simply use those distances as time intervals:<jupyter_code>distances = np.linalg.norm(np.diff(points3 + points3[:1], axis=0), axis=1)
distances
times4 = np.concatenate([[0], np.cumsum(distances)])
times4
plot_catmull_rom(points3, times4)<jupyter_output><empty_output><jupyter_text>This makes the speed along the spline nearly constant,but the distance between the curve and its longer chordscan become quite huge.  Centripetal ParameterizationAs a variation of the previous method,the square roots of the chordal lengthscan be used to define the time intervals.<jupyter_code>times5 = np.concatenate([[0], np.cumsum(np.sqrt(distances))])
times5
plot_catmull_rom(points3, times5)<jupyter_output><empty_output><jupyter_text>The curve takes its course much closer to the chords,but its speed is obviously far from constant.Centripetal parameterization has the very nice property thatit guarantees no cusps and no self-intersections,as shown by Yuksel et al. (2011).The curve is also guaranteed to never "move away" from the successive vertex: > When centripetal parameterization is used with Catmull--Rom splines todefine a path curve, the direction of motion for the object following this pathwill always be towards the next key-frame position.>> ---Yuksel et al. (2011), Section 7.2: "Path Curves"  Parameterized ParameterizationIt turns out that the previous two parameterization schemesare just two special cases of a more general schemefor obtaining time intervals between control points:\begin{equation*}t_{i+1} = t_i + |\boldsymbol{x}_{i+1} - \boldsymbol{x}_i|^\alpha,\text{ with } 0 \le \alpha \le 1.\end{equation*}In the Python class[splines.CatmullRom](../python-module/splines.rstsplines.CatmullRom),the parameter `alpha` can be specified.<jupyter_code>def plot_alpha(alpha, label):
    s = splines.CatmullRom(points3, alpha=alpha, endconditions='closed')
    plot_spline_2d(s, label=label)
plot_alpha(0, r'$\alpha = 0$ (uniform)')
plot_alpha(0.5, r'$\alpha = 0.5$ (centripetal)')
plot_alpha(0.75, r'$\alpha = 0.75$')
plot_alpha(1, r'$\alpha = 1$ (chordal)')
plt.legend(loc='center', numpoints=3);<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12450730350104336, 'fraction_numerical': 0.021910503130071875, 'mean_word_length': 5.64637904468413, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 52, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '79378', 'license': 'MIT', 'n_tokens_mistral': 2923, 'n_tokens_neox': 2796, 'n_words': 841, 'path': 'doc/euclidean/catmull-rom-properties.ipynb', 'repo_name': 'AudioSceneDescriptionFormat/splines', 'size': '8626'}