Hacker News Reader

Comment by iTokio | Hacker News Reader

Is there a simple, elegant method to approximate a curve with a cubic spline?

I brute forced it with the least squares :(

*Edit: a cubic curve is also acceptable

It's a great question. No kidding. Of course, you can since you can build the first piece naturally, then get the second from a pair of points and a derivative of the first, and so on. But it would generally oscillate as hell. The trick is - if you're approximating a parametric curve, you don't want derivatives to actually match. You want the tangential continuity, which is a proportion of dx/dt and dy/dt derivatives and not the exact number. So if you just tame your derivatives a little, you would still keep the tangential continuity and not let the oscillations loose.

You want one cubic polynomial segment? Or you want to figure out where to put variable knots to approximate your curve with a particular number of cubic segments? Or ...

Try reading Raph Levien’s PhD thesis starting at page 135 http://www.levien.com/phd/thesis.pdf

That is about converting a specific type of curve to cubic segments, but can give you an idea of the considerations involved.

It’s a lossy compression issue:

How to approximate a curve within a given error threshold with the minimum number of control points.

Well the simplest one to code up is just bisection of segments until every one is under your error threshold. This is obviously far from ideal, but depending on your needs might be acceptable.

If you are trying to approximate a function where the domain of the function is important then it’s fairly straightforward. See De Boor’s book A Practical Guide to Splines, which IIRC has a chapter or two about this.

If instead you are using your spline to approximate the points of a curve without worrying about the parametrization, that gets trickier. Try doing a google scholar search (keywords along the lines of “spline variable knots cagd”), there are a pile of papers analyzing different approaches.

The simple bissection can over fit quite easily.

Thank you these are great resources!

Quadratic Bezier curves don't quite have enough independent degrees of freedom. With cubic curves, there's a simple method: you put the two endpoints at arbitrary nearby points on the curve, and then the other two control points are determined by the derivatives at those points.

See https://en.wikipedia.org/wiki/B%C3%A9zier_curve#Derivative

Exactly. You can even have your own formulae for 3rd order polynomial interpolating curve (no need to go through the "original" formulae)

Sorry I meant cubic, control points can just be points of the original curve with a catmull rom spline.

So an easy method is just to remove the point with the minimal error contribution and iterate until a given threshold.

But the cost is too high for large curves.

assuming any "kind" of spline before you have your data is jumping the gun; if you have 20 points, then anything under a 20th order polynomial is not guaranteed to actually fit your data, so: how lossy do you want the fit to be? You could use a poly-whatever, like a catmull-rom curve, or something based on B-spline

Reply on news.ycombinator.com