[ Line Chart ] Monotone cubic interpolation

[MatthieuRivaud]

First, thanks for all the good work.

I just started using Charts.js (have tinkered a bit with line charts so far), and it seems the cubic interpolation used does not preserves monotonicity of the provided data (which makes sense, because said algorithm is very generic, probably because Charts.js has to interpolate for a lot of different data representations).

I think however that monotone cubic interpolation [1] has several advantages over the classic cubic interpolation :

• It preserves monotonicity of a data set (i.e. does not add local extremums due to interpolation “artifacts”)
• It preserves local extremums in the original data (again, the monotonic cubic interpolation tries really hard not to add artificial extremums between discrete data points)

I hacked the current Chart.js interpolation in my repository to switch to monotone cubic interpolation if wanted, and it seems to work quite well (I already did the math for a personal charting project in SVG, so it was quite easy to replicate in Charts.js due to the use of Bezier curves for its existing cubic interpolation).

Are you interested in uplifting my changes to the official Charts.js repository ?

Regards,

[1] https://en.wikipedia.org/wiki/Monotone_cubic_interpolation

Notes :

• I do not use Git nor GitHub (only SVN till now), so I may have to ask for help a bit.
• For the time being, I hacked the |Chart.controllers.line.updateBezierControlPoints| function and tried to preserve as much as I can the control points calculated in |helpers.splineCurve|, but it might be better (and faster) to implement a new helper function (|splineCurveMonotone| or something).

[etimberg]

@MatthieuRivaud these would be great to have. Perhaps we could have an option in the line element config to enable this. I agree that a new splineCurveMonotone would probably be better. It'd probably be simpler to test too.

What are your thoughts on something like this as a config option?

options: {
  elements: {
    line: {
      cubicInterpolationMode: 'monotone' 
    }
  }
}

[MatthieuRivaud]

I used a config option very similar to this (options.elements.line.monotoneInterpolation, boolean). Your proposition seems better to me (more generic).

I'll try to implement splineCurveMonotone. I may have to work on the whole dataset at once, though (instead of keeping the same firstPoint, middlePoint, afterPoint parameters). We'll see.

Questions :

• Can Chart.js display line charts in a vertical mode (i.e. linear x-axis and category y-axis) ? If that's the case, I would have to add a parameter to splineCurveMonotone in order to switch between x-axis and y-axis monotonicity.
• Do I need to handle the line scatter chart (i.e. detect and disable monotone cubic interpolation in this case) ? This mode does not seem to call updateBezierControlPoints, AFAICT.
• Do you have any coding style guide I should adhere to ? I try to style my code according to the surrounding code, but it may be better to know the exact rules.

[etimberg]

I think I can answer your questions

• This should be possible but I've never seen a chart like that,
• updateBezierControlPoints should run for a scatter chart (unless there is no line or the tension is 0)
• Styling to the surrounding code is good. We don't have a formal style guideline other than what JSHint creates warnings for. You can test it out with gulp jshint

[MatthieuRivaud]

I'm having a hard time implementing splineCurveMonotone with the same signature as splineCurve : the monotone cubic interpolation works in part on segments, adjusting tangents (and thus control points) two vertexes at a time. Any thoughts ?

I also think I will have to clamp the strength of the control points (the norm of the resulting vector) : I believe the monotone cubic interpolation algorithm cannot guarantee the monotonicity if the control point is further than 1/3rd of the distance between data points (not really sure about that, my math is a bit fuzzy). I could also ignore the tension parameter, and use the 1/3 ratio (which I believe is the exact ratio to use for cubic interpolation, according to the last paragraph in https://en.wikipedia.org/wiki/Cubic_interpolation#Representations, but I may be mistaken).

[MatthieuRivaud]

Mmm, Ok, I had a bug in my hacked scatter.html sample file. I can now activate monotone cubic interpolation on a scatter graph, and can confirm the result is absolute bonkers ... ^^

There must be a mean to adapt the algorithm to keep local extremums in 2d (if it has any sense at all), but this is another work for another day. (I also don't think monotonicity has a sense in this case, but my math is much too rusty to give a definite answer).

What test would you recommend in order to detect the scatter case ? Both x-axis and y-axis in linear mode for the dataset to interpolate ?

[etimberg]

I wouldn't constrain yourself to having the same signature as splineCurve if it doesn't make sense.

Since this is new, I think it is fine to ignore the tension and instead use 1/3. We will just need to make sure the docs are clear on this.

What if your algorithm worked on monotonic subsets of the data? The normal case would only have 1 monotonic section but scatter plots would not necessarily be. The worst case would be monotonic subsets that change with every point. If this strategy works, you won't need a specific test for the scatter chart.

[MatthieuRivaud]

The algorithm already handles minute changes in monotony. What it does not handle is datasets where the x distribution of data points isn't monotonic (i.e. when the dataset isn't of the form y = f(x)).

The scatter chart displays a function of t (i.e. (x, y) = f(t)), where t is the index of the data point. There is no definition of monotonicity that I know of in this case (it would probably be based on the notion of ordering between vectors/couples [1], but it seems quite sketchy).

There probably is a way to preserve local "extremums" (ensure the interpolated curve does not go "further" than the nearest data points), but I do not know the math, and it seems much more work than necessary for a graph that does not really need a better interpolation than the one we have now.

[1] like this one : http://mathworld.wolfram.com/VectorOrdering.html

[MatthieuRivaud]

OK, I finished coding splineCurveMonotone and updated updateBezierControlPoints accordingly :

• I chose to use the 1/3 ratio and ignore tension for now, but it is quite trivial to implement.
• I did not write any special case for the scatter line case. Monotone cubic interpolation can still be activated in this case, and can give suboptimal results (to say the least), but does not crash (lines are still drawn, just with somewhat inadequate control points). It should not be difficult to test the axes and auto-deactivate this interpolation mode.
• I am working on a test for splineCurveMonotone. I will also take a look on the line chart doc.
• There is no test for updateBezierControlPoints yet. Do you have some ideas on how to implement that, or do you think this kind of test is unnecessary (or too much work for the gain, in particular because updateBezierControlPoints is not a pure function [1], which generally makes automated testing a pain [2]) ?

How do we proceed ?

• I ran gulp lint on the update source, but linting returns quite a lot of unrelated errors (incorrect "use strict" declaration and undefined identifiers like module, require, console). Is there some additional config I have to do ? (I did not see any error that could be related to my updates, but the linter may abort early due to those errors in the beginning of the files)
• Do I need to provide a patch ? If so, is a SVN generated patch/unified diff OK, or do I need to provide a Git specific thing ? Or do I need to clone the repository and issue a pull request ? I never used GitHub nor Git yet.

[1] https://en.wikipedia.org/wiki/Pure_function
[2] http://alistapart.com/article/making-your-javascript-pure

[etimberg]

@MatthieuRivaud awesome!

The updateBezierControlPoints is tested via some of the line tests (we ensure that bezier points are correct given the data) so don't worry about writing a specific test for it.

I generally use gulp jshint and that's what our CI runs as well so there should be no outstanding issues.

I would recommend cloning the repository then creating a new branch for your changes. Push your changes up to the branch and then create a pull request. :)

Thanks for implementing this :)

[MatthieuRivaud]

I tried the gulp jshint with the default gulpfile.js, but I had a dependency error (gupl-concat missing or something). I made my own gulpfile.js, as instructed in the gulp-jshint starting guide, and used gulp lint (I chose lint as the name of the gulp task).

One other thing : I began to write a unit test, and in doing so, I discovered a rather peculiar behavior when rendering a Bézier curve. The rendered curve just after the break (skipped point) in the attached screenshot does not seem to follow the given control points (at the leftmost data point, at least). Does that makes sense ? Is it time for me to leave the computer aside for a bit ? ^^

(note that I'm using a scatter line graph in order to set the exact (x, y) coordinates of the datapoints, and ensure I have the exact same input as my unit test)

[MatthieuRivaud]

I finally have my node installation (mostly) working. I had to manually install a lot of packages (which weren't auto-installed by npm install chart.js --save for some reason).

My code does pass gulp jshint, but I'm now having trouble running unit tests (gulp unittest). I encounter the following error :

[12:28:44] Starting 'jshint'...
[12:28:44] Starting 'validHTML'...
[12:28:44] Starting 'unittest'...
[12:28:45] Finished 'jshint' after 1.06 s
[12:28:45] Starting Karma server...
(node:9336) fs: re-evaluating native module sources is not supported. If you are using the graceful-fs module, please update it to a more recent version.
WARN [reporter]: Can not load "html", it is not registered!
  Perhaps you are missing some plugin?
[... boring stacktrace ...]
Error: No provider for "framework:browserify"! (Resolving: framework:browserify)
[... boring stacktrace ...]
[12:28:46] 'unittest' errored after 1.4 s
[12:28:46] Error in plugin 'gulp-karma'
karma exited with code 1
[12:28:47] Finished 'validHTML' after 2.75 s

(I successfully ran npm install browserify before that message)

Also : I assume the actual code and doc review will happen when processing the pull request. Correct ?

[etimberg]

I think that error comes from https://github.com/chartjs/Chart.js/blob/master/package.json#L42

The actual review will be on the pull request. The tests and linting will auto run there as well so we'll have confirmation that nothing broke.

[etimberg]

I'm not sure why you're seeing the issue with the bezier control points after the skipped line. They should definitely be used.

[MatthieuRivaud]

I found the issue with the control points : the spanGaps wasn't properly probed in updateBezierControlPoints (actually, not probed at all). It might be better to fix this in another issue, though.

I think I will proceed with the pull request very soon.

[MatthieuRivaud]

Ok, pull request is green. I will open a new issue for the spanGaps fix.

Thanks for the guidance.

[etimberg]

Great! thanks @MatthieuRivaud

[MatthieuRivaud]

I'm having second thoughts on the cubicInterpolationMode option : I think it might be better to consolidate all interpolation "toogles" into one interpolationMode option, with the following choices :

• noInterpolation : No line drawn between discrete datapoints
• steppedLine : Same behavior as steppedLine = true currently
• bezier : Default behavior (splineCurve). I would call this option bezier because it is not a real cubic interpolation if the "strength" of the control points is not carefully chosen (i.e. Bezier curves can be used to draw a cubic interpolated curve, but can do much more, even strange things if lineTension < 0)
• linear : special bezier mode with lineTension = 0 ?
• cubicMonotone : the new monotone cubic interpolation

This would give room to add other interpolation modes if need be.

This change may need a dedicated #issue and PR, though.

Thoughts ?

[etimberg]

@MatthieuRivaud that's a good change in the long run, but it'd require a major version bump since the API is changing, or at least, we would have to support all the old options even if the new option is the way going forward.. I think because of this is would have to be its own issue

[MatthieuRivaud]

Yep, I agree. Maybe for v3 ^^