New Interpolated Map

Interpolated maps are values representing a piecewise function defined by interpolation between a sequence of breakpoints.

They have been initally defined as piecewise linear functions which have been superseded by NIM (an acronym for New Interpolated Map). NIM extends the idea of interpolation between breakpoints to vectors and to a superset of the interpolation types available in the curve construct.

A NIM is an aggregate data structure that records the breakpoints of the piecewise interpolation and the interpolation type (as in a curve). A NIM is considered an extensional function like a map. It can be applied to a numerical value to return the corresponding image.

NIMs can be used as an argument of the curve construct which allows the breakpoints to be dynamically built, "playing" the function later in time. See section Curve Playing a NIM.

Continuous and Discontinuous NIM

NIMs can represent continuous or discontinuous functions.

Continuous NIM are defined by an expression of the form:

         NIM { x₀ y₀, d₁ y₁  "cubic" 
                    , d₂ y₂ "linear"     
                    , d₃ y₃ "bounce"
                    , ...
                    , dᵢ yᵢ "tᵢ"
                    , ...
             }      

which specifies a piecewise function f: between \mathtt{x}_i and \mathtt{x}_{i+1} = \mathtt{x}_i + \mathtt{d}_{i+1}, function f is an interpolation of type \mathtt{t}_{i+1} from y_i to y_{i+1}. See the following illustration:

continuous ni

The previous definition specifies a continuous function because the value of f at the beginning of [\mathtt{x}_i, \mathtt{x}_{i+1}] is also the value of f at the end of the previous interval.

A second syntax allows one to define a discontinuous function by specifying a different value for the end of an interval and the beginning of the next one:

         NIM { x₀, y₀ d₀ Y₀  "cubic"
                 , y₁ d₁ Y₁  "linear"             
                 , y₂ d₂ Y₂  "bounce"
                 , ...
             }      

The definition is similar to the previous form except that on the interval [\mathtt{x}_i, \mathtt{x}_{i+1}] the function is an interpolation between \mathtt{y}_i and \mathtt{Y}_i. See illustration:

discontinuous nim

The NIM keyword is case-unsensitive and introduces an expression. The parameters \mathtt{x}_i, \mathtt{y}_i, \mathtt{d}_i, \mathtt{Y}_i, \mathtt{t}_i are expressions.

Definition of the NIM outside the breakpoints

The function f is extended outside [\mathtt{x}_0, \mathtt{x}_n] such that

\begin{eqnarray} f(x) &=& \mathtt{y}_0 \qquad \text{for } x \leq \mathtt{x}_0 \\ f(x) &=& \mathtt{y}_n \qquad \text{for } x \geq \mathtt{x}_n = \mathtt{x}_0 +\sum_{i = 0}^n \mathtt{d}_i \end{eqnarray}

However, the functions @min_key and @max_key return \mathtt{x}_0 and \mathtt{x}_n respectively (these functions also perform similarly on maps: maps are functions on a discrete range while NIMs are functions on a continuous range).

Interpolation type

The type of the interpolation is either a constant string or an expression. In the latter case, however, the expression must be enclosed in parentheses. The names of the allowed interpolation types are the same as those of a curve (see curve interpolation methods), and the interpolation types are illustrated on these figures. Other experimental interpolation methods are currently under development.

The specification of an interpolation type is optional. When not defined, the interpolation type is assumed to be linear.

Vectorial NIM

The NIM construct accepts tabs as arguments: in this case, the result is a vectorial function. For example:

      NIM{ [-1, 0] [0, 10], [2, 3] [1, 20] ["cubic", "linear"] }

defines a vectorial of two variables: $$ \vec{f} \binom{x_1}{x_2} = \binom{\,f_1(x_1)\,}{\,f_2(x_2)\,} $$ where f_1 is a cubic interpolation between 0 and 1 for x_1 going from -1 to -1 + 2 = 1 and f_2 is a linear interpolation between 10 and 20 for x_2 going from 0 to 0 + 3 = 3.

The NIM construction is ‟smart”: the parameters of a vectorized NIM may mix scalar s and tabs. In this case, the scalar is extended implicitly into a vector of the correct size whose elements are all equal to s. This is the case even for the specification of the interpolation type. For example:

          NIM{ 0, 0, [1, 2] 10 }

defines the function \vec{f} = \binom{f_1}{f_2} where

\begin{eqnarray} f_1(x) &=& 0 \text{ if } x < 0 \\ &=& 10 \text{ if } x > 1 \\ &=& 10 x \text{ elsewhere} \end{eqnarray}

and

\begin{eqnarray} f_2(x) &=& 0 \text{ if } x < 0 \\ &=& 10 \text{ if } x > 2 \\ &=& 5 x \text{ elsewhere} \end{eqnarray}

A vectorized NIM is listable: it can be applied to a scalar argument. In this case, the scalar argument x is implicitly extended to a vector of the correct dimension: $$ \newcommand{\MYatop}[2]{\genfrac{}{}{0pt}{}{#1}{#2}} \vec{f}(x) = \vec{f}\binom{x}{\MYatop{\displaystyle{x}}{\displaystyle\dots}} $$

The function @dim returns the dimension of the image of a NIM, that is, 1 for a scalar NIM and n \not= 1 for a vectorized NIM, where n is the number of elements of the tab returned by the application of the NIM.

The function @size returns the number of breakpoints of the NIM (which is not equal to the dimension of the NIM). Note that a nim with zero breakpoints is the result of a bad definition.

Heterogeneous breakpoints in vectorial NIM

A vectorial NIM can be seen as the aggregation of several scalar NIMs.

The functions @projection and @aggregate can be used to respectively extract a scalar nim from a vectorial nim and to aggregate several (scalar or vectorial) nims of dimension d_1, \dots, d_p into a nim of dimension d_1 + \dots + d_p.

          let $nim1 := NIM{ 0 0, 1 10, 1 0 "sine_in_out" }
          let $nim2 := NIM{ -1 10, 4 0 "sine_in_out" }
          let $nim3 := @aggregate($nim1, $nim2)

This process can be used to build vectorial NIMs whose breakpoints are different, as in the specification of vectorial curves. There is no syntax to directly specify such NIMs and the function @aggregate must be used to build such NIM values that are said to have heterogeneous breakpoints. When printing such a NIM, the function @aggregate is used to list its many components:

aggreagte nim

 
 
 

@aggregate( NIM{0 0, 1 10 "linear",
                     1 0  "sine_in_out"}, 
            NIM{-1 10, 3 0 "sine_in_out"} )


The function @projection can be used to extract a component from a vectorial NIM:

          @projection($nim3, 1) ==  $nim2     true

Extending a NIM

The function @push_back can be used to add a new breakpoints to an existing NIM. They are several variations:

          @push_back(nim, d, y1)
          @push_back(nim, d, y1, type)
          @push_back(nim, y0, d, y1)
          @push_back(nim, y0, d, y1, type)
          @push_back(nim₁, nim₂)

The four first forms modify the NIM ‟in-place”. The last form builds a new NIM:

Note that @push_back is an overloaded function: it can also be used to add (in place) an element at the end of a tab.

NIM Transformation and Smoothing

NIMs can be managed through Nim Related Functions @aggregate,    @align_breakpoints,    @dim,    @filter_max_t,    @filter_median_t,    @filter_min_t,    @integrate,    @linearize,    @max_key,    @max_val,    @min,    @min_key,    @min_val,    @projection,    @push_back,    @push_front,    @sample,    @simplify_lang_v,    @simplify_radial_distance_t,    @simplify_radial_distance_v,    @window_filter_t   

See their descriptions in the library. Here, we describe the notions that appear when a NIM is restructured.

Sampling, homogeneization and linearization

It is possible to convert a NIM with an arbitrary interpolation type to a NIM with a linear interpolation type.

The function @sample takes a NIM nim and a number n and returns a NIM with n breakpoints and linear interpolation type that approximates nim. The process is illustrated in the following diagram: the NIM $nim4 in input

sampling a nim

 

@sample($nim3, 5)     
@aggregate( nim{0 0, 0.333333 3.33333, 
                     0.333333 6.66667, 
                     0.333333 10, 
                     0.333333 7.5, 
                     0.333333 2.5, 
                     0.333333 0}, 
            nim{-1 10, 0.5 9.33013, 
                       0.5 7.5, 
                       0.5 5,
                       0.5 2.5, 
                       0.5 0.669873, 
                       0.5 0}  )

As can be seen, in the case of a vectorial NIM with heterogeneous components, the approximation is done component by component and the result has heterogeneous breakpoints.

The function @align_breakpoints can be used on a NIM with linear interpolation type to obtain an equivalent NIM with homogeneous breakpoints:

          let $nim4 :=  @sample($nim3, 5)

will compute a NIM with a heterogeneous breakpoint printed as

align breakpoints

 
 

@align_breakpoints($nim4)   
NIM { [-1, -1],
      [0, 10] [0.5, 0.5] [0, 10] 
      [0, 9.33013] [0.5, 0.5] [0, 9.33013] 
       ; ...
      [0, 0] [0.333333, 0.333333] [0, 0] }

The function @sample samples its NIM argument homogeneously (component by component). This is not always satisfactory because the variation of the NIM can differ greatly between two intervals. The function @linearize(nim, tol) uses an adaptive sampling step to linearize nim, to align the breakpoints and to achieve an approximation within a given tolerance tol.

linearize nim

 
 
 

@linearize($nim3)   
NIM { [-1, -1], 
      [0, 10] [0.609946, 0.609946] [0, 9.01426],
      [0, 9.01426] [0.270743, 0.270743] [0, 8.02012],
      ; ...
      [0.563462, 0.0636838] [0.152573, 0.152573] [0, 0] }

The application of the @linearize function can be time consuming and care must be taken so as not to perturb the real-time computations, e.g., by precomputing a linearization (see @eval_when_load clause and function @loadvalue).

NIM simplification

NIMs can be used to record a temporal series of data arriving (through time) from the environment, using setvar or OSC messages. It is then often useful to simplify the NIM, in order to have a more compact representation. The underlying idea is that the NIM approximates a curve known by a series of points, the breakpoints of the NIM, and that this curve can be approximated by fewer points. The simplified NIM consists of a subset of the breakpoints that defined the original.

Several functions can be used to achieve a reduction of the number of breakpoints of a NIM with linear interpolation.

All the simplification functions apply to scalar as well as vectorial NIMs, but consider only the ”x-coordinate” given by the breakpoints of the first component2. In case of a vectorial NIM with heterogeneous breakpoints, this can be a drawback. In this case, an equivalent NIM with homogeneous breakpoints can be first built using the @align_breakpoints function.

The three following functions are inspired from polyline simplification functions developed in computer graphics1:

The effect of these simplification functions on a nim can be observed using the function @size which returns, for a nim, its number of breakpoints.

Smoothing and Transformation

The functions described here work independently on each component of a nim. They see each component as a sequence of points y (the image of the nim) that are smoothed in various way. The resulting points are used to build a new nim with linear interpolation type. The number of breakpoints is preserved, as well as their x-coordinate. Only the y-part of the breakpoint (the image) is affected.



  1. The following references gives technical details on polyline simplification. Description and evaluation of several algorithms in a cartographic context are given in this paper. The Ramer–Douglas–Peucker algorithm follows an idea similar to the Lang algorithm used by @simplify_lang_v but the shrinking of the current interval is dichotomous. This project provides an implementation of the main algorithms is in C++. 

  2. If the recorded value is a time series, then the x-coordinate corresponds to time and the NIM will be homogeneous as it is incrementally built using the function @push_back. The only way to build a non-homogeneous nim is to use the function @aggregate