Implement Steffen-style monotone curves

[ghost]

This set of changes implements monotone curves based on src/curve/natural.js and the following paper: Steffen, M. 1990. A Simple Method for Monotonic Interpolation in One Dimension. Astronomy and Astrophysics, Vol. 239, NO. NOV(II), P. 443, 1990. The paper is readable at http://adsabs.harvard.edu/full/1990A%26A...239..443S.

The implementation makes a couple of choices aiming to streamline the code. First, the slope at the boundary points is set to zero, which generally looks ok when plotting line graphs. The paper also offers other good suggestions, such as using the slope of the line going through the boundary point and the point next to it.

Second, the slope is just set to zero on certain cases when the x_i values are not strictly monotonic, such as when (x_i - x_i-1) = 0 or when (x_i - x_i-1) + (x_i+1 - x_i) = 0.

This also modifies index.js to expose the implementation as monotone.

I hope this is useful, but should this not be suitable for d3-shape I can make it a plugin or something like that.

[ghost]

Oh, right, and here's a small bl.ocks.org demo comparison: http://bl.ocks.org/jviide/801889be3954d8f0bfe3

[mbostock]

Fixes #10.

[mbostock]

This looks very promising. Thank you! It’ll take me a little time to review the math.

My main technical comment at this point is that you are buffering all the input points before starting to generate the spline; this shouldn’t be necessary because the spline behavior is local and only a single pass over the data is needed. (This is in contrast to natural cubic splines which do require a global calculation.)

It makes the implementation a little more complicated since you need to “look ahead” one or two points, but it’s more performant to reduce the amount of buffering. You can see the other curve implementations such as cardinal and Catmull–Rom for examples.

A design question is whether there should be two variants of this curve: one to preserve monotonicity in y and another for x. But, it doesn’t seem essential to provide both implementations, since you could always just swap the two values yourself and then apply a transform to the result. And it’s nice to just say monotone instead of monotoneY.

[mbostock]

Also, would you be willing to sign the contributor license agreement?

[ghost]

I updated the pull request based on your comments - now only the last two points (x_i-1, y_i-1) and (x_i, y_i) and the slope t_i-1 for the earlier of them need to be buffered.

I'll read through the contributor license agreement tomorrow with fresher eyes :)

[mbostock]

The new implementation looks great.

Let me know if you have any questions about the CLA. It’s intended to verify (1) that you are the author of the code in this pull request and (2) that you give me permission to distribute your code under D3’s open-source license. I assume both of those things are true—since you created this pull request—but it’s safer for me to verify those things explicitly.

Thanks.

[ghost]

Sorry for the delay.

Personally having just one monotone implementation sounds good. If it appears to be an issue at some point then providing a small example referenced in the API docs might help.

[mbostock]

Thanks. I’ve merged this into the monotone branch, #38. I’ll implement some tests and then merge to master.