Allow to simplify massive data to make charts more readable

3 files changed, 188 insertions, 0 deletions

diff --git a/tipboard/settings.py b/tipboard/settings.py
index 83d344d..cedd034 100644
--- a/tipboard/settings.py
+++ b/tipboard/settings.py
@@ -104,6 +104,7 @@ TIPBOARD_CSS_STYLES = [
 ]
 TIPBOARD_JAVASCRIPTS = [
     'js/lib/jquery.js',
+    'js/lib/simplify.js',
     'js/lib/jquery.fullscreen.js',
     'js/lib/jqplot/jquery.jqplot.js',
     'js/lib/jqplot/plugins/jqplot.trendline.js',
diff --git a/tipboard/static/js/lib/simplify.js b/tipboard/static/js/lib/simplify.js
new file mode 100644
index 0000000..63a5ddb
--- /dev/null
+++ b/tipboard/static/js/lib/simplify.js
@@ -0,0 +1,121 @@
+/*
+ (c) 2013, Vladimir Agafonkin
+ Simplify.js, a high-performance JS polyline simplification library
+ mourner.github.io/simplify-js
+*/
+
+(function () { 'use strict';
+
+// to suit your point format, run search/replace for '.x' and '.y';
+// for 3D version, see 3d branch (configurability would draw significant performance overhead)
+
+// square distance between 2 points
+function getSqDist(p1, p2) {
+
+    var dx = p1.x - p2.x,
+        dy = p1.y - p2.y;
+
+    return dx * dx + dy * dy;
+}
+
+// square distance from a point to a segment
+function getSqSegDist(p, p1, p2) {
+
+    var x = p1.x,
+        y = p1.y,
+        dx = p2.x - x,
+        dy = p2.y - y;
+
+    if (dx !== 0 || dy !== 0) {
+
+        var t = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy);
+
+        if (t > 1) {
+            x = p2.x;
+            y = p2.y;
+
+        } else if (t > 0) {
+            x += dx * t;
+            y += dy * t;
+        }
+    }
+
+    dx = p.x - x;
+    dy = p.y - y;
+
+    return dx * dx + dy * dy;
+}
+// rest of the code doesn't care about point format
+
+// basic distance-based simplification
+function simplifyRadialDist(points, sqTolerance) {
+
+    var prevPoint = points[0],
+        newPoints = [prevPoint],
+        point;
+
+    for (var i = 1, len = points.length; i < len; i++) {
+        point = points[i];
+
+        if (getSqDist(point, prevPoint) > sqTolerance) {
+            newPoints.push(point);
+            prevPoint = point;
+        }
+    }
+
+    if (prevPoint !== point) newPoints.push(point);
+
+    return newPoints;
+}
+
+function simplifyDPStep(points, first, last, sqTolerance, simplified) {
+    var maxSqDist = 0,
+        index;
+
+    for (var i = first + 1; i < last; i++) {
+        var sqDist = getSqSegDist(points[i], points[first], points[last]);
+
+        if (sqDist > maxSqDist) {
+            index = i;
+            maxSqDist = sqDist;
+        }
+    }
+
+    if (maxSqDist > sqTolerance) {
+        if (index - first > 1) simplifyDPStep(points, first, index, sqTolerance, simplified);
+        simplified.push(points[index]);
+        if (last - index > 1) simplifyDPStep(points, index, last, sqTolerance, simplified);
+    }
+}
+
+// simplification using Ramer-Douglas-Peucker algorithm
+function simplifyDouglasPeucker(points, sqTolerance) {
+    var last = points.length - 1;
+
+    var simplified = [points[0]];
+    simplifyDPStep(points, 0, last, sqTolerance, simplified);
+    simplified.push(points[last]);
+
+    return simplified;
+}
+
+// both algorithms combined for awesome performance
+function simplify(points, tolerance, highestQuality) {
+
+    if (points.length <= 2) return points;
+
+    var sqTolerance = tolerance !== undefined ? tolerance * tolerance : 1;
+
+    points = highestQuality ? points : simplifyRadialDist(points, sqTolerance);
+    points = simplifyDouglasPeucker(points, sqTolerance);
+
+    return points;
+}
+
+// export as AMD module / Node module / browser or worker variable
+if (typeof define === 'function' && define.amd) define(function() { return simplify; });
+else if (typeof module !== 'undefined') module.exports = simplify;
+else if (typeof self !== 'undefined') self.simplify = simplify;
+else window.simplify = simplify;
+
+})();
diff --git a/tipboard/tiles/line_chart.js b/tipboard/tiles/line_chart.js
index 0d91fbe..b4a023c 100644
--- a/tipboard/tiles/line_chart.js
+++ b/tipboard/tiles/line_chart.js
@@ -1,6 +1,69 @@
 /*jslint browser: true, devel: true*/
 /*global WebSocket: false, Tipboard: false*/
 
+function simplifyLineData(series_data, user_config) {
+    var config = {
+        tolerancy: 10,
+        data_points_limit: 50, // we will TRY to achieve lower number of data points than this
+        max_simplifying_steps: 5,
+        simplify_step_multiplicator: 1.5
+        };
+
+    $.extend(config, user_config);
+    
+    var simplify_data = new Array();
+    var return_data = new Array();
+
+    for(var series = 0; series < series_data.length; series++) {
+        simplify_data[series] = new Array();
+        return_data[series] = new Array();
+
+        // converting data to format acceptable by simplify.js library
+        if(typeof series_data[series][0] === typeof []) {
+            for(var tick = 0; tick < series_data[series].length; tick++) {
+                simplify_data[series].push({
+                    x: tick,
+                    y: series_data[series][tick][1],
+                    key: series_data[series][tick][0]
+                });
+            }
+        } else {
+            for(var tick = 0; tick < series_data[series].length; tick++) {
+                simplify_data[series].push({
+                    x: tick,
+                    y: series_data[series][tick],
+                    key: null
+                });
+            }
+        }
+
+        var current_tolerance = config.tolerancy;
+        for(var i = 0; i < config.max_simplifying_steps; i++) {
+            simplify_data[series] = simplify(simplify_data[series], current_tolerance);
+            if(simplify_data[series].length < config.data_points_limit) break;
+            current_tolerance = Math.floor(current_tolerance * config.simplify_step_multiplicator);
+        }
+
+        // prepare in data format understandable by jqplot
+        for(var tick = 0; tick < simplify_data[series].length; tick++) {
+            if(simplify_data[series][tick].key != null)
+                return_data[series][tick] = [
+                    simplify_data[series][tick].key,
+                    simplify_data[series][tick].y
+                ];
+            else
+                return_data[series][simplify_data[series][tick].x] = simplify_data[series][tick].y;
+        }
+
+        // fill all created gaps with null for jqplot
+	for(var i = 0; i < return_data[series].length; i++) {
+            if(!return_data[series][i])
+                return_data[series][i] = null;
+        }
+    }
+
+    return return_data;
+}
 
 function updateTileLine(tileId, data, meta, tipboard) {
     var tile = Tipboard.Dashboard.id2node(tileId);
@@ -21,6 +84,9 @@ function updateTileLine(tileId, data, meta, tipboard) {
     // TODO use Tipboard.Dashboard.buildChart
     Tipboard.DisplayUtils.expandLastChild(tile);
     Tipboard.DisplayUtils.expandLastChild($(tile).find('.tile-content')[0]);
+
+    if(config.simplify) data.series_list = simplifyLineData(data.series_list, config.simplify);
+
     Tipboard.Dashboard.chartsIds[tileId] = $.jqplot(
         tileId + '-chart', data.series_list, config
     );