Smoothest possible path interpolation given 2-D positions and directions?

Question

Assume I have a set of $n$ points $\{x_1,...,x_n \} \in \mathbb{R^2}$ and a set of corresponding directions (or angles) $\{d_1,...,d_n \}$. It is my goal to find the smoothest, continuous path (edit: I define smoothness as the smallest overall curvature) which passes through all $n$ points while honoring all $n$ directions. The solution may be provided in increments, for example through splines between a pairs of successive points.

I have illustrated what I mean below. Do you have any suggestions on how to tackle this issue?

Answer 1

Using a B-spline curve is the best method for smoothly interpolating a set of point and tangent vector pairs. A B-spline curve can have arbitrarily high order of continuity ($\mathcal{C}^n$ for any positive integer $n$). The NURBS Book (by Piegl and Tiller) describes a simple method of interpolating a set of $N$ point and tangent vector pairs with a B-spline curve. With this method, you solve a linear system of $2N$ equations with $2N$ unknown basis function coefficients for each of the three coordinates of the curve. You can find an implementation of this method in SISL, the SINTEF spline library. This is a library of B-spline curve and surface functions that is free for non-commercial use.

The NURBS Book's method does not always yield the most desirable shape for the curve. A slightly more sophisticated method minimizes the integral of the squared third derivative of the B-spline curve function subject to the point and tangent vector interpolation constraints. This is a quadratic minimization problem subject to linear constraints, which can be transformed into a linear system of equations using Lagrange multipliers.

The equation of the B-spline curve is $$ x_j(t) = \sum_{i=0}^{N_b-1} c^j_i B_i(t) $$ where $j$ is the coordinate index, $N_b$ is the number of basis functions, and $B_i$ is the $i$th basis function. The NURBS Book's method of tangent vector interpolation requires choosing a length for the tangent vector. The second method described here does not require choosing a length for the tangent vector at the cost of merging the three systems of linear equations into a single system. A tangent vector constraint at the $t$ value $t_k$ is written $$ x_j'(t) = \sum_{i=0}^{N_b-1} c^j_i B_i'(t_k) = r_k T^j_k $$ where $r_k$ is an new unknown and $T^j_k$ is the $j$th coordinate of the unit tangent vector to be interpolated at $t_k$. The variables of the Lagrange multiplier system of equations are the $3N_b$ basis function coefficients, the $N$ new $r_k$ variables, and the $6N$ Lagrange multipliers.

Both of the following curves are $\mathcal{C}^3$ B-spline curves interpolating the same six point and tangent vector pairs. The first uses The NURBS Book's method. The second uses the more sophisticated method; its shape is clearly "better".

The curvature plots of these two curves show why the second curve looks "better". The second curve has fewer unnecessary undulations in its curvature plot than the first one. This is the reason for minimizing the integral of the squared third derivative: to eliminate unnecessary change in the curvature, which is a function of the second derivative.

Answer 2

Smallest overall curvature does not make sense, because any curve interpolating your points and tangents will have the same total curvature (by the Whitney-Graustein theorem)!

You can ask for the interpolating curve of minimum total squared curvature, $$E(\gamma) = \int_{\gamma} \kappa^2\,ds,$$

and interestingly, the original drafting splines, made of flexible strips of wood, did minimize exactly this functional, since it measure the elastic energy of a flexed beam. The solution will not be a cubic (mathematical) spline, but rather, a Minimum Energy Curve (MEC). For discussion of such curves, and a derivation of the solution using the Calculus of Variations, see for instance Horn 1983, "The Curve of Least Energy."