Hacker News new | past | comments | ask | show | jobs | submit login
On the Spline: A Brief History of the Computational Curve (alatown.com)
64 points by alnis on Oct 24, 2015 | hide | past | favorite | 3 comments



Folks interested in splines should check out Raph Levien’s Ph.D thesis, http://www.levien.com/phd/phd.html

He made splines out of piecewise “spiro” curves (aka clothoids, Cornu spirals or Euler spirals), for which curvature changes linearly with arclength. This makes much smoother-looking curves than naive use of e.g. Bézier-curve segments, which he found made it much easier to trace or create nice looking letter glyphs for font design.


There's a nice generalisation of splines to higher-dimensional spaces, in a non-ad-hoc way:

For the case of fitting a 2D surface to interpolate some control points {(x_i, y_i)}_i, x_i \in R^2, y_i in R, we can seek to find a surface f : R^2 --> R that attains the minimum

    min_f sum_i ( f(x_i) - y_i )^2 + \lambda || D f ||^2
where \lambda > 0 is some real constant parameter.

I.e., we seek to find a surface f that trades-off goodness of fit to the control points (in the least-squares sense) against smoothness (measured by the norm of the derivative).

In the 2D case these are called "thin-plate splines". They can be viewed as nice energy-mininising surfaces that interpolate between a few control points. The functions f live in Sobolev spaces - analysis of this stuff descends into a lot of PDE theory and approximation theory if you want to compute approximations to them in practice.

To get non-singular surfaces in higher dimensions than 2 you merely have to increase which derivative appears in the smoothing term, but the same idea basically works. (You also need to ensure you have enough control points to define the surface -- note that if your smoothing term is || D^k f ||^2 then a degree k-1 polynomial is invisible to it -- so the smoothing term does not control a degree k-1 polynomial component, so you have to ensure you have appropriate control points to define that part)

If you are curious to read more about this, there's Grace Wahba's book "spline models for observational data". e.g. http://bookstore.siam.org/CB59/


Clothoids are used for many railroad curve transitions, because they are constant-jerk curves. (Jerk is the derivative of acceleration.) They can provide a smoother look than B-splines, but are not as general.




Consider applying for YC's first-ever Fall batch! Applications are open till Aug 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: