Add further interpolation types

[msteinbeck]

TinySpline provides natural spline interpolation only. We should add closed, periodic, and knot-a-knot interpolation in order to provide a more convenient interface.

[msteinbeck]

https://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/CURVE-INT-global.html provides code describing the interpolation of B-Splines with given degree.

https://people.sc.fsu.edu/~jburkardt/c_src/superlu/superlu.html provides a linear solver implemented in ANSI C

[Mortal]

Any plans to implement interpolation of a closed curve, i.e. "splinegon interpolation"? I would like to extend Ipe (feature request) with a drawing tool to draw the natural splinegon through given points since I could benefit a lot from this in my technical drawings of blobs nested inside blobs. Currently I tweak the control points to get the splinegons where I want them in my drawings, but this is imprecise and inefficient.

Alternatively, do you have references on how to implement closed interpolation? Would this be achieved by, say, changing the Thomas algorithm? (I am not at all familiar with spline interpolation algorithms, but I could probably implement some pseudocode in C if it exists.)

[msteinbeck]

Hi @Mortal. I never heard of "splinegons"---nice to know.

Interpolation of closed splines is something I really would like to address. So, yes, I do have plans to implement it. However, I didn't find the time to do it yet ( there are many different things to do on this library :) ). Implementing closed spline interpolation shouldn't be to hard though.

Alternatively, do you have references on how to implement closed interpolation? Would this be achieved by, say, changing the Thomas algorithm?

The Thomas algorithm most probably must not be changed. What this algorithm basically does is solving a special kind of matrix in linear instead of cubic time. If you want to interpolate a closed instead of a natural spline, all you need to do is to "modify" the base matrix that is used as input for the Thomas algorithm. You can find some information about this matrix at http://www.math.ucla.edu/%7Ebaker/149.1.02w/handouts/dd_splines.pdf page DD 9 (B1 to B4 are the intermediate points of the spline to interpolate). By changing, for instance, the upper left and bottom right entry of the input matrix, you could (more or less) easily interpolate closed (alias clamped) splines. You can find more about this approach at page DD 15: Other possible end conditions.

The Thomas algorithm uses a forward and backward sweep approach to solve a matrix. You can find TinySpline's implementation at https://github.com/msteinbeck/tinyspline/blob/master/library/tinyspline.c#L524 with m being the base matrix. This implementation is based on: http://mirror.hmc.edu/ctan/graphics/pstricks/contrib/pst-bspline/pst-bspline-doc.pdf page 12. An approach showing how to interpolate a closed spline is given on page 13.

If you want to, feel free to implement this approach and create a PR :). Note: closed/clamped spline interpolation is a specials case of periodic spline interpolation. That is, the end points are equals when interpolating a closed/clamped spline. If they differ, it is a periodic spline interpolation.

[msteinbeck]

It looks like using the Thomas algorithm will not be applicable for closed spline interpolation.Though having a tridiagonal matrix given in dd_splines.pdf, page DD 16, I can't find a way to put it into the existing code. Consequently, I suggest to implement the pseudo code given in pst-bspline-doc.pdf, page 14 which is using the Gaussian elimination to solve the matrix.

[msteinbeck]

Currently implemented are:

• cubic natural
• catmull rom

Missing:

• cubic clamped (given out and in vectors)
• cubic periodic as proposed by @Mortal (requires gauß elimination with partial pivoting, see http://web.mit.edu/10.001/Web/Course_Notes/Gauss_Pivoting.c)
• cubic knot-a-not? (not sure how matrix looks like)
• monotonic (http://articles.adsabs.harvard.edu//full/1990A%26A...239..443S/0000443.000.html)
• Maybe cardinal splines.