polygon filtering algorithm

plotly · alexcjohnson · Jan 6, 2016 · Dec 27, 2015 · Dec 27, 2015 · Dec 28, 2015
commit f0e6cfb68e6c4f1122a6998ad9146200f657ad0a
diff --git a/src/lib/polygon.js b/src/lib/polygon.js
@@ -8,6 +8,7 @@
 
 
 'use strict';
+var dot = require('./matrix').dot;
 
 /**
  * Turn an array of [x, y] pairs into a polygon object
@@ -118,4 +119,80 @@ polygon.tester = function tester(ptsIn) {
     };
 };
 
+/**
+ * Test if a segment of a points array is bent or straight
+ *
+ * @param pts Array of [x, y] pairs
+ * @param start the index of the proposed start of the straight section
+ * @param end the index of the proposed end point
+ * @param tolerance the max distance off the line connecting start and end
+ *      before the line counts as bent
+ * @returns boolean: true means this segment is bent, false means straight
+ */
+var isBent = polygon.isSegmentBent = function isBent(pts, start, end, tolerance) {
+    var startPt = pts[start],
+        segment = [pts[end][0] - startPt[0], pts[end][1] - startPt[1]],
+        segmentSquared = dot(segment, segment),
+        segmentLen = Math.sqrt(segmentSquared),
+        unitPerp = [-segment[1] / segmentLen, segment[0] / segmentLen],
+        i,
+        part,
+        partParallel;
+
+    for(i = start + 1; i < end; i++) {
+        part = [pts[i][0] - startPt[0], pts[i][1] - startPt[1]];
+        partParallel = dot(part, segment);
+
+        if(partParallel < 0 || partParallel > segmentSquared ||
+            Math.abs(dot(part, unitPerp)) > tolerance) return true;
+    }
+    return false;
+};
+
+/**
+ * Make a filtering polygon, to minimize the number of segments
+ *
+ * @param pts Array of [x, y] pairs (must start with at least 1 pair)
+ * @param tolerance the maximum deviation from straight allowed for
+ *      removing points to simplify the polygon
+ *
+ * @returns Object {addPt, raw, filtered}
+ *      addPt is a function(pt: [x, y] pair) to add a raw point and
+ *          continue filtering
+ *      raw is all the input points
+ *      filtered is the resulting filtered Array of [x, y] pairs
+ */
+polygon.filter = function filter(pts, tolerance) {
+    var ptsFiltered = [pts[0]],
+        doneRawIndex = 0,
+        doneFilteredIndex = 0;
+
+    function addPt(pt) {
+        pts.push(pt);
+        var prevFilterLen = ptsFiltered.length,
+            iLast = doneRawIndex;
+        ptsFiltered.splice(doneFilteredIndex + 1);
+
+        for(var i = iLast + 1; i < pts.length; i++) {
+            if(i === pts.length - 1 || isBent(pts, iLast, i + 1, tolerance)) {
+                ptsFiltered.push(pts[i]);
+                if(ptsFiltered.length < prevFilterLen - 2) {
+                    doneRawIndex = i;
+                    doneFilteredIndex = ptsFiltered.length - 1;
+                }
+                iLast = i;
+            }
+        }
+    }
 
+    if(pts.length > 1) {
+        var lastPt = pts.pop();
+        addPt(lastPt);
+    }
+
+    return {
+        addPt: addPt,
+        raw: pts,
+        filtered: ptsFiltered
+    };
+};
diff --git a/src/plots/cartesian/select.js b/src/plots/cartesian/select.js
@@ -8,9 +8,11 @@
 
 
 'use strict';
+var polygon = require('../../lib/polygon');
+var filteredPolygon = polygon.filter;
+var BENDPX = 1.5; // max pixels off straight before a line counts as bent
 
 module.exports = function prepSelect(e, startX, startY, dragOptions, mode) {
-    console.log('select start', e, startX, startY, dragOptions, mode);
     var plot = dragOptions.plotinfo.plot,
         dragBBox = dragOptions.element.getBoundingClientRect(),
         x0 = startX - dragBBox.left,
@@ -19,35 +21,34 @@ module.exports = function prepSelect(e, startX, startY, dragOptions, mode) {
         y1 = y0,
         path0 = 'M' + x0 + ',' + y0,
         pw = dragOptions.xaxes[0]._length,
-        ph = dragOptions.yaxes[0]._length,
-        pts = [[x0, y0]],
-        outlines = plot.selectAll('path.select-outline').data([1,2]);
+        ph = dragOptions.yaxes[0]._length;
+    if(mode === 'lasso') {
+        var pts = filteredPolygon([[x0, y0]], BENDPX);
+    }
 
-    // TODO initial dimming of selectable points
+    var outlines = plot.selectAll('path.select-outline').data([1,2]);
 
     outlines.enter()
         .append('path')
         .attr('class', function(d) { return 'select-outline select-outline-' + d; })
         .attr('d', path0 + 'Z');
 
     dragOptions.moveFn = function(dx0, dy0) {
-        console.log('select move', dx0, dy0);
         x1 = Math.max(0, Math.min(pw, dx0 + x0));
         y1 = Math.max(0, Math.min(ph, dy0 + y0));
 
         if(mode === 'select') {
             outlines.attr('d', path0 + 'H' + x1 + 'V' + y1 + 'H' + x0 + 'Z');
         }
-        else {
-            pts.push([x1, y1]); // TODO: filter this down to something reasonable
-            outlines.attr('d', 'M' + pts.join('L'));
+        else if(mode === 'lasso') {
+            pts.addPt([x1, y1]);
+            outlines.attr('d', 'M' + pts.filtered.join('L'));
         }
 
         // TODO - actual selection and dimming!
     };
 
     dragOptions.doneFn = function(dragged, numclicks) {
-        console
52B4
.log('select done', dragged, numclicks);
         if(!dragged && numclicks === 2) dragOptions.doubleclick();
         else {
             // TODO - select event
@@ -56,3 +57,4 @@ module.exports = function prepSelect(e, startX, startY, dragOptions, mode) {
         // TODO - remove dimming
     };
 };
+