# interpolation and splines

## problem dimensions and design tradeoffs
interpolation is not a single problem but a family of problems defined by constraints and goals. any interpolation scheme is implicitly a choice along several orthogonal axes.

### interpolation vs approximation
* interpolating curves pass exactly through specified data points (knots)
* approximating curves do not necessarily pass through knots, but minimize some error or energy functional
* hybrid approaches exist, where only selected knots are interpolated

### continuity requirements
continuity is typically expressed as ck continuity.
* c0: positional continuity only
* c1: continuous first derivative (tangent continuity)
* c2: continuous second derivative (curvature continuity)
* higher orders are possible but rarely justified outside numerical analysis
  higher continuity generally implies:
* wider support (each segment depends on more knots)
* reduced local control
* increased sensitivity to knot placement

### local vs global control
* local schemes change only nearby segments when a knot moves
* global schemes change the entire curve when a single knot moves
  global control simplifies optimization but complicates interactive design.

### bounding and overshoot
many interpolants overshoot.
* values between knots may exceed the convex hull or bounding box of the knots
* this is undesirable for monotonic data, physical constraints, or safety-critical systems
* avoiding overshoot often conflicts with high-order continuity
  bounding properties are therefore a primary selection criterion.

### parameterization
the curve parameter is rarely unique.
* uniform parameterization
* chord-length parameterization
* centripetal parameterization
  parameterization affects speed, curvature, and overshoot, even for the same basis functions.

## families of interpolation and spline techniques
the following grouping is by construction mechanism rather than historical naming.

### polynomial segment interpolation
piecewise low-degree polynomials with continuity constraints at knots.
* cubic hermite splines
  * c1 or c2 continuity depending on tangent choice
  * explicit tangent control
* catmull-rom splines
  * interpolating
  * typically c1
  * local control
  * prone to overshoot unless modified
* natural cubic splines
  * interpolating
  * c2 continuity
  * global solution
  * second derivative constrained to zero at endpoints

### bezier-based constructions
polynomial curves defined by control points rather than interpolation points.
* bezier curves
  * do not interpolate intermediate control points
  * strong convex hull and bounding box properties
  * degree grows with number of control points
* composite bezier splines
  * piecewise bezier with continuity constraints
  * manual continuity management

### basis spline families
splines defined by basis functions with compact support.
* b-splines
  * non-interpolating (except at ends, depending on knot vector)
  * ck continuity controllable via knot multiplicity
  * strong local control
* nurbs
  * rational generalization of b-splines
  * exact representation of conic sections
  * weights introduce additional degrees of freedom
  * same locality and continuity structure as b-splines

### geometric interpolation
curves constructed from geometric primitives rather than polynomials.
* circular arc interpolation
  * exact curvature control
  * c1 continuity at joins unless constrained
  * common in cnc and motion planning
* spherical linear interpolation (slerp)
  * interpolation on manifolds
  * preserves constant angular velocity
  * not polynomial

### exponential and nonlinear interpolation
interpolation performed in transformed spaces.
* exponential interpolation
  * useful for scale-like quantities
  * avoids negative values by construction
* log-space or power-law interpolation: preserves ratios rather than differences
  these methods trade linear intuition for constraint preservation.

### energy-minimizing and variational methods
curves defined as minimizers of a functional.
* thin-plate splines
* smoohing splines
* minimum curvature or minimum acceleration curves
  properties:
* typically global
* interpolating or approximating depending on constraints
* physically interpretable but computationally heavier

## summary observations
* no single interpolation method dominates across all criteria
* interpolating schemes tend to overshoot unless explicitly constrained
* higher continuity increases smoothness but reduces local control
* bounding properties are often more important than continuity order
* b-splines and nurbs provide the most flexible general framework, but sacrifice interpolation
* natural cubic splines maximize smoothness under interpolation constraints, but are global
* catmull-rom splines are often chosen for simplicity rather than guarantees
* energy-minimizing approaches unify many splines under a single optimization view

## subtopics
* [bezier curves](splines/bezier-curve.html)
* [catmull-rom splines](splines/catmull-rom-spline.html)

## links
* [curved paths](https://www.redblobgames.com/articles/curved-paths)
* [comparison of interpolation methods](http://paulbourke.net/miscellaneous/interpolation/)
* [interactive introduction to splines](https://www.ibiblio.org/e-notes/splines/intro.htm)
* [interpolation](http://danceswithcode.net/engineeringnotes/interpolation/interpolation.html)
* [slides comparing curve and spline functions](https://www.cs.cmu.edu/afs/cs/academic/class/15462-f11/www/lec_slides/lec06.pdf)
* [tinyspline](https://tinyspline.org/)
* [circular arc interpolation](https://observablehq.com/@jrus/circle-arc-interpolation)
* on wikipedia
* [cubic hermite spline](https://en.wikipedia.org/wiki/Cubic_Hermite_spline)
  * [interpolation](https://en.wikipedia.org/wiki/Interpolation)
  * [spline interpolation](https://en.wikipedia.org/wiki/Spline_interpolation)
* cubic splines
  * [article](https://timodenk.com/blog/cubic-spline-interpolation/) by timo denk, with an accompanying online [tool](https://tools.timodenk.com/cubic-spline-interpolation) and its javascript [code](https://github.com/Simsso/Online-Tools/blob/master/src/page/logic/cubic-spline-interpolation.js)
  * [cubic spline program](https://stackoverflow.com/questions/7642921/cubic-spline-program) on stackoverflow
  * [on wikiversity](https://en.wikiversity.org/wiki/Cubic_Spline_Interpolation)
  * [scipy](https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.CubicSpline.html) natural cubic splines with scipy
  * [smoothing with cubic splines](https://www.semanticscholar.org/paper/SMOOTHING-WITH-CUBIC-SPLINES/afbeeab7a657e3ab2181c7645626061be84fafe8) by d.s.g. pollock
  * [spherical linear interpolation / slerp](https://en.wikipedia.org/wiki/Slerp)