Programmer's guide to polynomials and splines | Hacker News Reader

Programmer's guide to polynomials and splines

wordsandbuttons.online

219 pointsokaleniuk24 comments

I always hear in my head the voice from old Maxis games like SC2K that says, “reticulating splines”

Me too! I spent weeks of my life on that game and never thought to ask what it even meant when they said that.

This is also in the build process when you compile Firefox.

This only talks about natural cubic splines. I learned recently that there is a whole family of approaches to constructing cubic splines beyond natural splines; the difference is in the process used to choose the derivatives at the knots. One particularly interesting application is monotone interpolation, which avoids some of the overshooting and oscillation you can get with natural splines:

https://en.wikipedia.org/wiki/Monotone_cubic_interpolation

It seems the best algorithm for monotone cubic interpolation is the Fritsch-Butland algorithm - here's a nice interactive demonstration:

http://bl.ocks.org/niclasmattsson/7bceb05fba6c71c78d507adae3...

One of the more interesting courses I took in my undergrad was a course on CAD/CAM. The CAD portion of the course focused on the mathematics behind 3D CAD systems, and the different ways that 2D curves and 3D surfaces can be defines parametrically. Definitely something worth learning about if you do any 3D modeling.

Did the course have a text book? If so, which one/ones?

I didn't have a textbook for mine, just class notes. But I remember there was some topology, required for defining manifolds and their relations with one another so that it makes "sense". here's a book that your might find interesting: https://www.amazon.com/Geometry-Computer-Graphics-Undergradu...

On a side not, a lot of current research focuses on simplifying CAD models to use them as inputs to simulation programs (CFD, finite element analysis codes etc). Indeed, since your CAD model is highly precise, the models are hard to mesh (need very fine mesh to discretize the details), so you simplify them manually and it's very time consuming.

One of the methods that most struck me to automate this simplification was taking the CAD model, transforming it to the frequency domain where high frequencies represent small geometric details and large frequencies, larges underlying features in the model's geometry. So you can filter out the high frequencies, transform it back and end up with a simplified model. You've literally filtered away the smaller geometric features of the model. I remember the paper describing the method for 2D geometry only.

Here's a paper surveying the some of the state of the art methods to simplify CAD models and prepare them for simulation packages. https://www.sciencedirect.com/science/article/pii/S001044850...

> One of the methods that most struck me to automate this simplification was taking the CAD model, transforming it to the frequency domain where high frequencies represent small geometric details and large frequencies, larges underlying features in the model's geometry. So you can filter out the high frequencies, transform it back and end up with a simplified model. You've literally filtered away the smaller geometric features of the model.

That’s a very interesting idea. I guess the problem is though, how would you be able to make such a transformation?

I recommend the book Curves and Surfaces for CAGD by Gerald Farin (RIP). I have the 4th edition, which I have seen some people recommend in preference to the 5th, but I have never looked at the 5th edition.

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.

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

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!

If anyone feels like implementing splines after reading this, the svglover lua library is accepting pull requests ;) https://github.com/globalcitizen/svglover/issues/1

Great guide! Another reason to be familiar with this stuff is for data science: splines in particular are really useful for fitting a linear predictor where you suspect some of the marginal relationships are nonlinear, but you don’t have a strong prior on what the nonlinearity looks like.

Why everyone thinks that programmers are idiots and for teaching them math one needs a dumb down explanation with a shitty piece of python code example?

Not everyone thinks that about programmers. Only mathematicians and engineers. And programmers who think that about other programmers.

I started programming when I was nine, by myself. With game maker, which was (is?) a visual language to make games. I remember banging my head against the table trying to understand what a "real" number was. Even square roots were black magic back in the day.

Where I could learn the most was in code examples. They provided me new concepts I could poke, modify the values, and see the output, and hopefully after some time I would be able to understand how to use it.

There's a trend that everyone should understand how to code, and python is used as the língua franca for beginners, so providing a lot of examples helps people that do not intend to work as a developer understand new concepts. First you read about it, then you play with it for a while, and finally you'll get how to use it (and when to) in the future.

Reply on news.ycombinator.com