Plotly.js: Add monotone spline support (and maybe other spline modes)

[CohenBenco]

Hi :)
I've been trying to solve this issue:
https://jsfiddle.net/ro3c1gwx/

as you can see, when the line is 'spline', so it curves between equal values.
in this example, the line curves below the X axis for example.

I've found out that there's a new algorithm - called 'b-spline' or 'basis'.
http://bl.ocks.org/mbostock/4342190

With the example above i can use 'monotone', which exactly implements the line shape i'm looking for.

Thank you :)

[etpinard]

Yep, that would be nice.

Thanks for the suggestion!

[alexcjohnson]

From @Animus451 in #2085:

Whatever method is used to generate the spline often distorts the data set to which the curve is being fit. [Some graphs can show] false extrema as a result of the spline.
While this kind of spline may work for some situations, a more generally useful spline would be a monotonic polynomial regression. This specifically prevents distorted representations of extrema.

@rreusser's response:

A good suggestion! Current behavior is actually 2D catmull-rom splines. That means there's no favored independent variable or axis. Which in turn means, I guess, monotonic _with respect to what_? Which then means this would perhaps take the form of shape: 'spline' | 'monotonicx' | 'monotonicy'. Or shape: 'spline', monotonic: false | 'x' | 'y', though the latter makes the 'smoothing' parameter unused for that case, which is just a bit awkward.

Paths are computed for use here and step paths (perhaps most similar to this case) are computed here. It would then be a matter of computing a monotonic path (in screen coordinates, I believe). The math is here.

It certainly seems reasonable and perhaps not even that difficult, though I don't believe it's currently on the radar. A PR would be gladly accepted though. Glad to help think it through, otherwise those are my thoughts on what it would take.

I'd probably vote for all of these options to become different line.shape values, despite the fact that they're all splines so it's a little weird in retrospect to call only Catmull-Rom a spline.

I'll note that the monotone algorithm implemented by d3 is a bit funny - it can still give extrema that aren't quite data values (if it did, each local extreme data point would need to have the curve pass through it with exactly zero derivative), and has some strangely unstable behavior as points pass each other in y value. So we may want to revisit exactly how that should work before we blindly copy or use it.

[niclasmattsson]

I just posted this in a Julia package for interpolations, but you guys may be interested as well.

Some months ago I needed fast monotone cubic splines for a webapp and decided to look up the original papers that first published the algorithms and write my own implementation based on that. If you're interested I'm willing to release my code under MIT or any license you want. It's in Javascript of course, but you can easily port it to Julia. I have code for two different algorithms:

The Fritsch-Carlson algorithm (1980) is the one described on the Wikipedia page and implemented in the WIP by cc7768.

The Fritsch-Butland algorithm (1984) is faster because it only needs one pass over the data points instead of two. It produces very similar results but in practice looks a tiny bit more more linear than Fritsch-Carlson. Current spline literature appears to regard Fritsch-Butland as the "benchmark", but I am not a specialist.

Let me know if you want my implementation. If so, please tell me how I should release it. As you can tell from my profile I'm a complete Github newbie. I can also share PDFs of these papers if you want to have a look yourself.

Regarding the comment by @alexcjohnson:

I'll note that the monotone algorithm implemented by d3 is a bit funny - it can still give extrema that aren't quite data values (if it did, each local extreme data point would need to have the curve pass through it with exactly zero derivative), and has some strangely unstable behavior as points pass each other in y value.

Yeah, that is funny. I just tested my code by dragging breakpoints just like you did. Both algorithms are nice and stable.

[alexcjohnson]

@niclasmattsson thanks! Maybe the most useful way to share it is as a gist - and if a gist is formatted right with some example usage, it can be shared in action via blocks

Plotly staff are pretty swamped for the next few months, but if anyone is itching to get this into plotly.js soon we'd happily review a PR :)

[niclasmattsson]

Thanks for the tips @alexcjohnson, I didn't know it was so easy to get an interactive demo online using the gist/bl.ocks combo! I already had a working demo on my computer, so it was just a matter of writing a README and uploading it. Please have a look at my spline playground. While I was at it I also added a third algorithm for monotonic cubic splines (Steffen).

As for getting something into Plotly.js, I'm in no hurry. After all, I have my own code. :) But I do hope someone finds this useful enough to put into Plotly at some point!

[alexcjohnson]

@niclasmattsson thanks! Those indeed look like exactly what we would want for monotonic splines - they have small differences but all behave quite nicely.