hull.js - npm Package Compare versions

Comparing version 0.2.7 to 0.2.8

bower.json

 {
     "name": "hull-js",
-    "version": "0.2.7",
+    "version": "0.2.8",
     "description": "JavaScript library that builds concave hulls (shapes) by set of points",
@@ -5,0 +5,0 @@ "homepage": "https://github.com/AndriiHeonia/hull",

debug/perf.js

@@ -8,6 +8,9 @@ var horse13k = require('./data/horse13k.js'),
     owl58k = require('./data/owl58k.js'),
-    owl102k = require('./data/owl102k.js');
+    owl102k = require('./data/owl102k.js'),
+    geoNorvay600k = require('./data/geoNorvay600k.js');
 
 var hull = require('../src/hull');
 
+// concavity = 20
+
 console.time('hull(horse13k, 20)');
@@ -47,4 +50,51 @@ hull(horse13k, 20);
 
+console.log('\n');
 
-// master:
+// concavity = 10
+
+console.time('hull(horse13k, 10)');
+hull(horse13k, 10);
+console.timeEnd('hull(horse13k, 10)');
+
+console.time('hull(horse26k, 10)');
+hull(horse26k, 10);
+console.timeEnd('hull(horse26k, 10)');
+
+console.time('hull(horse52k, 10)');
+hull(horse52k, 10);
+console.timeEnd('hull(horse52k, 10)');
+
+console.time('hull(horse131k, 10)');
+hull(horse131k, 10);
+console.timeEnd('hull(horse131k, 10)');
+
+console.log('\n');
+
+console.time('hull(owl15k, 10)');
+hull(owl15k, 10);
+console.timeEnd('hull(owl15k, 10)');
+
+console.time('hull(owl30k, 10)');
+hull(owl30k, 10);
+console.timeEnd('hull(owl30k, 10)');
+
+console.time('hull(owl58k, 10)');
+hull(owl58k, 10);
+console.timeEnd('hull(owl58k, 10)');
+
+console.time('hull(owl102k, 10)');
+hull(owl102k, 10);
+console.timeEnd('hull(owl102k, 10)');
+
+console.log('\n');
+
+// geoNorvay600k, concavity = 0.2
+
+console.time('hull(geoNorvay600k, 0.5)');
+hull(geoNorvay600k, 0.5);
+console.timeEnd('hull(geoNorvay600k, 0.5)');
+
+
+// version 0.1.0:
+
 // hull(horse13k, 20): 1613ms
@@ -62,18 +112,52 @@ // hull(horse26k, 20): 2318ms
 
-// speedup:
-// hull(horse13k, 20): 188ms
-// hull(horse26k, 20): 189ms
-// hull(horse52k, 20): 306ms
-// hull(horse131k, 20): 653ms
+// version 0.2.0:
 
-// hull(owl15k, 20): 43ms
-// hull(owl30k, 20): 112ms
-// hull(owl58k, 20): 153ms
-// hull(owl102k, 20): 219ms
+// hull(horse13k, 20): 187ms
+// hull(horse26k, 20): 191ms
+// hull(horse52k, 20): 305ms
+// hull(horse131k, 20): 657ms
+//
+// hull(owl15k, 20): 39ms
+// hull(owl30k, 20): 68ms
+// hull(owl58k, 20): 120ms
+// hull(owl102k, 20): 201ms
+//
+// hull(horse13k, 10): 90634ms
+// hull(horse26k, 10): 22178ms
+// hull(horse52k, 10): 560ms
+// hull(horse131k, 10): 1077ms
+//
+// hull(owl15k, 10): 61973ms
+// hull(owl30k, 10): 7250ms
+// hull(owl58k, 10): 181ms
+// hull(owl102k, 10): 315ms
 
-// ------------------------------
-
 // Horse: 8.6x, 12.3x, 18.3x, 30.2x
 // Owl: 12x, 7.4x, 13.3x, 19.7x
+// Hull.js 0.2. Now it's ~20x faster (on 100K points) than previous triangulation based version.
 
-// Hull.js 0.2. Now it's ~20x faster (on 100K points) than previous triangulation based version.
+// ------------------------------
+
+// version 0.2.8:
+
+// hull(horse13k, 20): 234ms
+// hull(horse26k, 20): 237ms
+// hull(horse52k, 20): 329ms
+// hull(horse131k, 20): 953ms
+
+// hull(owl15k, 20): 48ms
+// hull(owl30k, 20): 66ms
+// hull(owl58k, 20): 120ms
+// hull(owl102k, 20): 209ms
+
+// hull(horse13k, 10): 1176ms
+// hull(horse26k, 10): 690ms
+// hull(horse52k, 10): 899ms
+// hull(horse131k, 10): 1341ms
+
+// hull(owl15k, 10): 448ms
+// hull(owl30k, 10): 228ms
+// hull(owl58k, 10): 211ms
+// hull(owl102k, 10): 309ms
+
+// hull(geoNorvay600k, 0.5): 116772ms

dist/hull.js

 !function(e){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=e();else if("function"==typeof define&&define.amd)define([],e);else{var f;"undefined"!=typeof window?f=window:"undefined"!=typeof global?f=global:"undefined"!=typeof self&&(f=self),f.hull=e()}}(function(){var define,module,exports;return (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
-function Grid(points) {
-    var _cells = [];
+function _cross(o, a, b) {
+    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
+}
 
+function _upperTangent(pointset) {
+    var lower = [];
+    for (var l = 0; l < pointset.length; l++) {
+        while (lower.length >= 2 && (_cross(lower[lower.length - 2], lower[lower.length - 1], pointset[l]) <= 0)) {
+            lower.pop();
+        }
+        lower.push(pointset[l]);
+    }
+    lower.pop();
+    return lower;
+}
+
+function _lowerTangent(pointset) {
+    var reversed = pointset.reverse(),
+        upper = [];
+    for (var u = 0; u < reversed.length; u++) {
+        while (upper.length >= 2 && (_cross(upper[upper.length - 2], upper[upper.length - 1], reversed[u]) <= 0)) {
+            upper.pop();
+        }
+        upper.push(reversed[u]);
+    }
+    upper.pop();
+    return upper;
+}
+
+// pointset has to be sorted by X
+function convex(pointset) {
+    var convex;
+    upper = _upperTangent(pointset);
+    lower = _lowerTangent(pointset);
+    convex = lower.concat(upper);
+    convex.push(pointset[0]);  
+    return convex;  
+}
+
+module.exports = convex;
+},{}],2:[function(require,module,exports){
+module.exports = {
+
+    toXy: function(pointset, format) {
+        if (format === undefined) {
+            return pointset;
+        }
+        return pointset.map(function(pt) {
+            /*jslint evil: true */
+            var _getXY = new Function('pt', 'return [pt' + format[0] + ',' + 'pt' + format[1] + '];');
+            return _getXY(pt);
+        });
+    },
+
+    fromXy: function(pointset, format) {
+        if (format === undefined) {
+            return pointset;
+        }
+        return pointset.map(function(pt) {
+            /*jslint evil: true */
+            var _getObj = new Function('pt', 'var o = {}; o' + format[0] + '= pt[0]; o' + format[1] + '= pt[1]; return o;');
+            return _getObj(pt);
+        });
+    }
+
+}
+},{}],3:[function(require,module,exports){
+function Grid(points, cellSize) {
+    this._cells = [];
+    this._cellSize = cellSize;
+
     points.forEach(function(point) {
@@ -9,18 +77,34 @@ var cellXY = this.point2CellXY(point),
             y = cellXY[1];
-        if (_cells[x] === undefined) {
-            _cells[x] = [];
+        if (this._cells[x] === undefined) {
+            this._cells[x] = [];
         }
-        if (_cells[x][y] === undefined) {
-            _cells[x][y] = [];
+        if (this._cells[x][y] === undefined) {
+            this._cells[x][y] = [];
         }
-        _cells[x][y].push(point);
+        this._cells[x][y].push(point);
     }, this);
+}
 
-    this.cellPoints = function(x, y) { // (Number, Number) -> Array
-        return (_cells[x] !== undefined && _cells[x][y] !== undefined) ? _cells[x][y] : [];
-    };
+Grid.prototype = {
+    cellPoints: function(x, y) { // (Number, Number) -> Array
+        return (this._cells[x] !== undefined && this._cells[x][y] !== undefined) ? this._cells[x][y] : [];
+    },
 
-    this.removePoint = function(point) { // (Array) -> Array
+    rangePoints: function(bbox) { // (Array) -> Array
+        var tlCellXY = this.point2CellXY([bbox[0], bbox[1]]),
+            brCellXY = this.point2CellXY([bbox[2], bbox[3]]),
+            points = [];
+
+        for (var x = tlCellXY[0]; x <= brCellXY[0]; x++) {
+            for (var y = tlCellXY[1]; y <= brCellXY[1]; y++) {
+                points = points.concat(this.cellPoints(x, y));
+            }
+        }
+
+        return points;
+    },
+
+    removePoint: function(point) { // (Array) -> Array
         var cellXY = this.point2CellXY(point),
-            cell = _cells[cellXY[0]][cellXY[1]],
+            cell = this._cells[cellXY[0]][cellXY[1]],
             pointIdxInCell;
@@ -38,32 +122,16 @@
         return cell;
-    };
-}
+    },
 
-Grid.prototype = {
     point2CellXY: function(point) { // (Array) -> Array
-        var x = parseInt(point[0] / Grid.CELL_SIZE),
-            y = parseInt(point[1] / Grid.CELL_SIZE);
+        var x = parseInt(point[0] / this._cellSize),
+            y = parseInt(point[1] / this._cellSize);
         return [x, y];
     },
 
-    rangePoints: function(bbox) { // (Array) -> Array
-        var tlCellXY = this.point2CellXY([bbox[0], bbox[1]]),
-            brCellXY = this.point2CellXY([bbox[2], bbox[3]]),
-            points = [];
-
-        for (var x = tlCellXY[0]; x <= brCellXY[0]; x++) {
-            for (var y = tlCellXY[1]; y <= brCellXY[1]; y++) {
-                points = points.concat(this.cellPoints(x, y));
-            }
-        }
-
-        return points;
-    },
-
-    addBorder2Bbox: function(bbox, border) { // (Array, Number) -> Array
+    extendBbox: function(bbox, scaleFactor) { // (Array, Number) -> Array
         return [
-            bbox[0] - (border * Grid.CELL_SIZE),
-            bbox[1] - (border * Grid.CELL_SIZE),
-            bbox[2] + (border * Grid.CELL_SIZE),
-            bbox[3] + (border * Grid.CELL_SIZE)
+            bbox[0] - (scaleFactor * this._cellSize),
+            bbox[1] - (scaleFactor * this._cellSize),
+            bbox[2] + (scaleFactor * this._cellSize),
+            bbox[3] + (scaleFactor * this._cellSize)
         ];
@@ -73,12 +141,10 @@ }
 
-function grid(points) {
-    return new Grid(points);
+function grid(points, cellSize) {
+    return new Grid(points, cellSize);
 }
 
-Grid.CELL_SIZE = 10;
-
 module.exports = grid;
-},{}],2:[function(require,module,exports){
+},{}],4:[function(require,module,exports){
 /*
- (c) 2014-2015, Andrii Heonia
+ (c) 2014-2016, Andrii Heonia
  Hull.js, a JavaScript library for concave hull generation by set of points.
@@ -92,31 +158,11 @@ https://github.com/AndriiHeonia/hull
 var grid = require('./grid.js');
+var formatUtil = require('./format.js');
+var convexHull = require('./convex.js');
 
-function _formatToXy(pointset, format) {
-    if (format === undefined) {
-        return pointset;
-    }
-    return pointset.map(function(pt) {
-        /*jslint evil: true */
-        var _getXY = new Function('pt', 'return [pt' + format[0] + ',' + 'pt' + format[1] + '];');
-        return _getXY(pt);
-    });
-}
-
-function _xyToFormat(pointset, format) {
-    if (format === undefined) {
-        return pointset;
-    }
-    return pointset.map(function(pt) {
-        /*jslint evil: true */
-        var _getObj = new Function('pt', 'var o = {}; o' + format[0] + '= pt[0]; o' + format[1] + '= pt[1]; return o;');
-        return _getObj(pt);
-    });
-}
-
 function _sortByX(pointset) {
     return pointset.sort(function(a, b) {
         if (a[0] == b[0]) {
-            return a[1] - b[1];                           
-        } else {                                                    
-            return a[0] - b[0];                                                           
+            return a[1] - b[1];
+        } else {
+            return a[0] - b[0];
         }
@@ -126,41 +172,2 @@ });
 
-function _getMaxY(pointset) {
-    var maxY = -Infinity;
-    for (var i = pointset.length - 1; i >= 0; i--) {
-        if (pointset[i][1] > maxY) {
-            maxY = pointset[i][1];
-        }
-    }
-    return maxY;
-}
-
-function _upperTangent(pointset) {
-    var lower = [];
-    for (var l = 0; l < pointset.length; l++) {
-        while (lower.length >= 2 && (_cross(lower[lower.length - 2], lower[lower.length - 1], pointset[l]) <= 0)) {
-            lower.pop();
-        }
-        lower.push(pointset[l]);
-    }
-    lower.pop();
-    return lower;
-}
-
-function _lowerTangent(pointset) {
-    var reversed = pointset.reverse(),
-        upper = [];
-    for (var u = 0; u < reversed.length; u++) {
-        while (upper.length >= 2 && (_cross(upper[upper.length - 2], upper[upper.length - 1], reversed[u]) <= 0)) {
-            upper.pop();
-        }
-        upper.push(reversed[u]);
-    }
-    upper.pop();
-    return upper;
-}
-
-function _cross(o, a, b) {
-    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]); 
-}
-
 function _sqLength(a, b) {
@@ -194,24 +201,35 @@ return Math.pow(b[0] - a[0], 2) + Math.pow(b[1] - a[1], 2);
 
-function _bBoxAround(edge, boxSize) {
-    var minX, maxX, minY, maxY;
+function _occupiedArea(pointset) {
+    var minX = Infinity,
+        minY = Infinity,
+        maxX = -Infinity,
+        maxY = -Infinity;
 
-    if (edge[0][0] < edge[1][0]) {
-        minX = edge[0][0] - boxSize;
-        maxX = edge[1][0] + boxSize;
-    } else {
-        minX = edge[1][0] - boxSize;
-        maxX = edge[0][0] + boxSize;
+    for (var i = pointset.length - 1; i >= 0; i--) {
+        if (pointset[i][0] < minX) {
+            minX = pointset[i][0];
+        }
+        if (pointset[i][1] < minY) {
+            minY = pointset[i][1];
+        }
+        if (pointset[i][0] > maxX) {
+            maxX = pointset[i][0];
+        }
+        if (pointset[i][1] > maxY) {
+            maxY = pointset[i][1];
+        }
     }
 
-    if (edge[0][1] < edge[1][1]) {
-        minY = edge[0][1] - boxSize;
-        maxY = edge[1][1] + boxSize;
-    } else {
-        minY = edge[1][1] - boxSize;
-        maxY = edge[0][1] + boxSize;
-    }
+    return [
+        maxX - minX, // width
+        maxY - minY  // height
+    ];
+}
 
+function _bBoxAround(edge) {
     return [
-        minX, minY, // tl
-        maxX, maxY  // br
+        Math.min(edge[0][0], edge[1][0]), // left
+        Math.min(edge[0][1], edge[1][1]), // top
+        Math.max(edge[0][0], edge[1][0]), // right
+        Math.max(edge[0][1], edge[1][1])  // bottom
     ];
@@ -243,8 +261,10 @@ }
 
-function _concave(convex, maxSqEdgeLen, maxSearchBBoxSize, grid) {
+function _concave(convex, maxSqEdgeLen, maxSearchArea, grid, edgeSkipList) {
     var edge,
-        border,
-        bBoxSize,
+        keyInSkipList,
+        scaleFactor,
         midPoint,
-        bBoxAround,    
+        bBoxAround,
+        bBoxWidth,
+        bBoxHeight,
         midPointInserted = false;
@@ -254,15 +274,22 @@
         edge = [convex[i], convex[i + 1]];
+        keyInSkipList = edge[0].join() + ',' + edge[1].join();
 
-        if (_sqLength(edge[0], edge[1]) < maxSqEdgeLen) { continue; }
+        if (_sqLength(edge[0], edge[1]) < maxSqEdgeLen ||
+            edgeSkipList[keyInSkipList] === true) { continue; }
 
-        border = 0;
-        bBoxSize = MIN_SEARCH_BBOX_SIZE;
-        bBoxAround = _bBoxAround(edge, bBoxSize);
+        scaleFactor = 0;
+        bBoxAround = _bBoxAround(edge);
         do {
-            bBoxAround = grid.addBorder2Bbox(bBoxAround, border);
-            bBoxSize = bBoxAround[2] - bBoxAround[0];
+            bBoxAround = grid.extendBbox(bBoxAround, scaleFactor);
+            bBoxWidth = bBoxAround[2] - bBoxAround[0];
+            bBoxHeight = bBoxAround[3] - bBoxAround[1];
+
             midPoint = _midPoint(edge, grid.rangePoints(bBoxAround), convex);            
-            border++;
-        }  while (midPoint === null && maxSearchBBoxSize > bBoxSize);
+            scaleFactor++;
+        }  while (midPoint === null && (maxSearchArea[0] > bBoxWidth || maxSearchArea[1] > bBoxHeight));
 
+        if (bBoxWidth >= maxSearchArea[0] && bBoxHeight >= maxSearchArea[1]) {
+            edgeSkipList[keyInSkipList] = true;
+        }
+
         if (midPoint !== null) {
@@ -276,3 +303,3 @@ convex.splice(i + 1, 0, midPoint);
     if (midPointInserted) {
-        return _concave(convex, maxSqEdgeLen, maxSearchBBoxSize, grid);
+        return _concave(convex, maxSqEdgeLen, maxSearchArea, grid, edgeSkipList);
     }
@@ -284,5 +311,8 @@
 function hull(pointset, concavity, format) {
-    var lower, upper, convex,
+    var convex,
+        concave,
         innerPoints,
-        maxSearchBBoxSize,
+        occupiedArea,
+        maxSearchArea,
+        cellSize,
         maxEdgeLen = concavity || 20;
@@ -294,22 +324,28 @@
 
-    pointset = _sortByX(_formatToXy(pointset, format));
-    upper = _upperTangent(pointset);
-    lower = _lowerTangent(pointset);
-    convex = lower.concat(upper);
-    convex.push(pointset[0]);
+    pointset = _sortByX(formatUtil.toXy(pointset, format));
+    occupiedArea = _occupiedArea(pointset);
+    maxSearchArea = [
+        occupiedArea[0] * MAX_SEARCH_BBOX_SIZE_PERCENT,
+        occupiedArea[1] * MAX_SEARCH_BBOX_SIZE_PERCENT
+    ];
 
-    maxSearchBBoxSize = Math.max(pointset[pointset.length - 1][0], _getMaxY(convex)) * MAX_SEARCH_BBOX_SIZE_PERCENT;
+    convex = convexHull(pointset);
     innerPoints = pointset.filter(function(pt) {
         return convex.indexOf(pt) < 0;
     });
+
+    cellSize = Math.ceil(1 / (pointset.length / (occupiedArea[0] * occupiedArea[1])));
+
+    concave = _concave(
+        convex, Math.pow(maxEdgeLen, 2),
+        maxSearchArea, grid(innerPoints, cellSize), {});
  
-    return _xyToFormat(_concave(convex, Math.pow(maxEdgeLen, 2), maxSearchBBoxSize, grid(innerPoints)), format);
+    return formatUtil.fromXy(concave, format);
 }
 
 var MAX_CONCAVE_ANGLE_COS = Math.cos(90 / (180 / Math.PI)); // angle = 90 deg
-var MIN_SEARCH_BBOX_SIZE = 5;
-var MAX_SEARCH_BBOX_SIZE_PERCENT = 0.8;
+var MAX_SEARCH_BBOX_SIZE_PERCENT = 0.6;
 
 module.exports = hull;
-},{"./grid.js":1,"./intersect.js":3}],3:[function(require,module,exports){
+},{"./convex.js":1,"./format.js":2,"./grid.js":3,"./intersect.js":5}],5:[function(require,module,exports){
 function ccw(x1, y1, x2, y2, x3, y3) {           
@@ -325,2 +361,3 @@ var cw = ((y3 - y1) * (x2 - x1)) - ((y2 - y1) * (x3 - x1));
       x4 = seg2[1][0], y4 = seg2[1][1];
+
     return ccw(x1, y1, x3, y3, x4, y4) !== ccw(x2, y2, x3, y3, x4, y4) && ccw(x1, y1, x2, y2, x3, y3) !== ccw(x1, y1, x2, y2, x4, y4);
@@ -330,3 +367,3 @@ }
 module.exports = intersect;
-},{}]},{},[2])(2)
+},{}]},{},[4])(4)
 });

package.json

 {
     "name": "hull.js",
-    "version": "0.2.7",
+    "version": "0.2.8",
     "description": "JavaScript library that builds concave hulls (shapes) by set of points",
@@ -20,2 +20,3 @@ "homepage": "https://github.com/AndriiHeonia/hull",
     "devDependencies": {
+        "nodemon": "~1.9.0",
         "mocha": "~1.18.2",
@@ -26,2 +27,3 @@ "jshint": "~2.5.0",
     "scripts": {
+        "watch": "./node_modules/nodemon/bin/nodemon.js --watch src --exec \"./node_modules/browserify/bin/cmd.js ./src/hull.js --standalone hull > ./dist/hull.js\"",
         "test": "./node_modules/jshint/bin/jshint src/intersect.js && ./node_modules/jshint/bin/jshint src/grid.js && ./node_modules/jshint/bin/jshint src/hull.js && ./node_modules/.bin/mocha -R spec && ./node_modules/browserify/bin/cmd.js ./src/hull.js --standalone hull > ./dist/hull.js"
@@ -34,2 +36,2 @@ },
     "license": "BSD"
-}
+}

README.md

@@ -33,8 +33,8 @@ Hull.js - JavaScript library that builds concave hull by set of points.
     <li>
-        <div>After that, the edges flex inward (according to `concavity` param). For example:</div>
+        <div>After that, the edges flex inward (according to the `concavity` param). For example:</div>
         <div>
             <img src="https://raw.githubusercontent.com/AndriiHeonia/hull/master/readme-imgs/2_1.png" />
-            `concavity = 80`
+            `concavity = 80`<br/>
             <img src="https://raw.githubusercontent.com/AndriiHeonia/hull/master/readme-imgs/2_2.png" />
-            `concavity = 40`
+            `concavity = 40`<br/>
             <img src="https://raw.githubusercontent.com/AndriiHeonia/hull/master/readme-imgs/2_3.png" />
@@ -47,4 +47,5 @@ `concavity = 20`
 ## Development
-	npm install # install dependencies
-	npm test	# build dist file and run tests
+	npm install             # install dependencies
+	npm test	            # build dist file and run tests
+	npm run-script watch    # watch ./src dir and rebuild dist file
 
@@ -57,3 +58,3 @@ ## Contribute
 
-* think about parallelisation of the calculations (on GPU or CPU);
+* think about parallelisation (on GPU or CPU);
 * think about holes;
@@ -66,2 +67,3 @@ * think about automatic `concavity` adjustment based on density.
 * <a target="_blank" href="http://www.cs.jhu.edu/~misha/Fall05/09.13.05.pdf">Computational Geometry: Convex Hulls</a>;
+* <a target="_blank" href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">Andrew's monotone chain convex hull algorithm</a>;
 * <a target="_blank" href="http://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/">Line Segment Intersection Algorithm</a>;
@@ -74,8 +76,10 @@ * <a target="_blank" href="http://allenchou.net/2013/07/cross-product-of-2d-vectors/">Game Math: "Cross Product" of 2D Vectors</a>;
 
+### 0.2.8 — 01.04.2016
+Added edgeSkipList to increase performance of the highly accurate shapes (with the small `concavity` number) + refactoring.
 ### 0.2.7 — 01.05.2015
-Fix bower.json
+Fixed bower.json
 ### 0.2.6 — 01.05.2015
-Fix bower.json
+Fixed bower.json
 ### 0.2.5 — 01.05.2015
-Add Bower support
+Bower support
 ### 0.2.4 — 23.03.2015
@@ -82,0 +86,0 @@ Minor fixes (copyrights)

src/grid.js

@@ -1,3 +0,4 @@
-function Grid(points) {
-    var _cells = [];
+function Grid(points, cellSize) {
+    this._cells = [];
+    this._cellSize = cellSize;
 
@@ -8,18 +9,34 @@ points.forEach(function(point) {
             y = cellXY[1];
-        if (_cells[x] === undefined) {
-            _cells[x] = [];
+        if (this._cells[x] === undefined) {
+            this._cells[x] = [];
         }
-        if (_cells[x][y] === undefined) {
-            _cells[x][y] = [];
+        if (this._cells[x][y] === undefined) {
+            this._cells[x][y] = [];
         }
-        _cells[x][y].push(point);
+        this._cells[x][y].push(point);
     }, this);
+}
 
-    this.cellPoints = function(x, y) { // (Number, Number) -> Array
-        return (_cells[x] !== undefined && _cells[x][y] !== undefined) ? _cells[x][y] : [];
-    };
+Grid.prototype = {
+    cellPoints: function(x, y) { // (Number, Number) -> Array
+        return (this._cells[x] !== undefined && this._cells[x][y] !== undefined) ? this._cells[x][y] : [];
+    },
 
-    this.removePoint = function(point) { // (Array) -> Array
+    rangePoints: function(bbox) { // (Array) -> Array
+        var tlCellXY = this.point2CellXY([bbox[0], bbox[1]]),
+            brCellXY = this.point2CellXY([bbox[2], bbox[3]]),
+            points = [];
+
+        for (var x = tlCellXY[0]; x <= brCellXY[0]; x++) {
+            for (var y = tlCellXY[1]; y <= brCellXY[1]; y++) {
+                points = points.concat(this.cellPoints(x, y));
+            }
+        }
+
+        return points;
+    },
+
+    removePoint: function(point) { // (Array) -> Array
         var cellXY = this.point2CellXY(point),
-            cell = _cells[cellXY[0]][cellXY[1]],
+            cell = this._cells[cellXY[0]][cellXY[1]],
             pointIdxInCell;
@@ -37,32 +54,16 @@
         return cell;
-    };
-}
+    },
 
-Grid.prototype = {
     point2CellXY: function(point) { // (Array) -> Array
-        var x = parseInt(point[0] / Grid.CELL_SIZE),
-            y = parseInt(point[1] / Grid.CELL_SIZE);
+        var x = parseInt(point[0] / this._cellSize),
+            y = parseInt(point[1] / this._cellSize);
         return [x, y];
     },
 
-    rangePoints: function(bbox) { // (Array) -> Array
-        var tlCellXY = this.point2CellXY([bbox[0], bbox[1]]),
-            brCellXY = this.point2CellXY([bbox[2], bbox[3]]),
-            points = [];
-
-        for (var x = tlCellXY[0]; x <= brCellXY[0]; x++) {
-            for (var y = tlCellXY[1]; y <= brCellXY[1]; y++) {
-                points = points.concat(this.cellPoints(x, y));
-            }
-        }
-
-        return points;
-    },
-
-    addBorder2Bbox: function(bbox, border) { // (Array, Number) -> Array
+    extendBbox: function(bbox, scaleFactor) { // (Array, Number) -> Array
         return [
-            bbox[0] - (border * Grid.CELL_SIZE),
-            bbox[1] - (border * Grid.CELL_SIZE),
-            bbox[2] + (border * Grid.CELL_SIZE),
-            bbox[3] + (border * Grid.CELL_SIZE)
+            bbox[0] - (scaleFactor * this._cellSize),
+            bbox[1] - (scaleFactor * this._cellSize),
+            bbox[2] + (scaleFactor * this._cellSize),
+            bbox[3] + (scaleFactor * this._cellSize)
         ];
@@ -72,8 +73,6 @@ }
 
-function grid(points) {
-    return new Grid(points);
+function grid(points, cellSize) {
+    return new Grid(points, cellSize);
 }
 
-Grid.CELL_SIZE = 10;
-
 module.exports = grid;

src/hull.js

 /*
- (c) 2014-2015, Andrii Heonia
+ (c) 2014-2016, Andrii Heonia
  Hull.js, a JavaScript library for concave hull generation by set of points.
@@ -11,31 +11,11 @@ https://github.com/AndriiHeonia/hull
 var grid = require('./grid.js');
+var formatUtil = require('./format.js');
+var convexHull = require('./convex.js');
 
-function _formatToXy(pointset, format) {
-    if (format === undefined) {
-        return pointset;
-    }
-    return pointset.map(function(pt) {
-        /*jslint evil: true */
-        var _getXY = new Function('pt', 'return [pt' + format[0] + ',' + 'pt' + format[1] + '];');
-        return _getXY(pt);
-    });
-}
-
-function _xyToFormat(pointset, format) {
-    if (format === undefined) {
-        return pointset;
-    }
-    return pointset.map(function(pt) {
-        /*jslint evil: true */
-        var _getObj = new Function('pt', 'var o = {}; o' + format[0] + '= pt[0]; o' + format[1] + '= pt[1]; return o;');
-        return _getObj(pt);
-    });
-}
-
 function _sortByX(pointset) {
     return pointset.sort(function(a, b) {
         if (a[0] == b[0]) {
-            return a[1] - b[1];                           
-        } else {                                                    
-            return a[0] - b[0];                                                           
+            return a[1] - b[1];
+        } else {
+            return a[0] - b[0];
         }
@@ -45,41 +25,2 @@ });
 
-function _getMaxY(pointset) {
-    var maxY = -Infinity;
-    for (var i = pointset.length - 1; i >= 0; i--) {
-        if (pointset[i][1] > maxY) {
-            maxY = pointset[i][1];
-        }
-    }
-    return maxY;
-}
-
-function _upperTangent(pointset) {
-    var lower = [];
-    for (var l = 0; l < pointset.length; l++) {
-        while (lower.length >= 2 && (_cross(lower[lower.length - 2], lower[lower.length - 1], pointset[l]) <= 0)) {
-            lower.pop();
-        }
-        lower.push(pointset[l]);
-    }
-    lower.pop();
-    return lower;
-}
-
-function _lowerTangent(pointset) {
-    var reversed = pointset.reverse(),
-        upper = [];
-    for (var u = 0; u < reversed.length; u++) {
-        while (upper.length >= 2 && (_cross(upper[upper.length - 2], upper[upper.length - 1], reversed[u]) <= 0)) {
-            upper.pop();
-        }
-        upper.push(reversed[u]);
-    }
-    upper.pop();
-    return upper;
-}
-
-function _cross(o, a, b) {
-    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]); 
-}
-
 function _sqLength(a, b) {
@@ -113,24 +54,35 @@ return Math.pow(b[0] - a[0], 2) + Math.pow(b[1] - a[1], 2);
 
-function _bBoxAround(edge, boxSize) {
-    var minX, maxX, minY, maxY;
+function _occupiedArea(pointset) {
+    var minX = Infinity,
+        minY = Infinity,
+        maxX = -Infinity,
+        maxY = -Infinity;
 
-    if (edge[0][0] < edge[1][0]) {
-        minX = edge[0][0] - boxSize;
-        maxX = edge[1][0] + boxSize;
-    } else {
-        minX = edge[1][0] - boxSize;
-        maxX = edge[0][0] + boxSize;
+    for (var i = pointset.length - 1; i >= 0; i--) {
+        if (pointset[i][0] < minX) {
+            minX = pointset[i][0];
+        }
+        if (pointset[i][1] < minY) {
+            minY = pointset[i][1];
+        }
+        if (pointset[i][0] > maxX) {
+            maxX = pointset[i][0];
+        }
+        if (pointset[i][1] > maxY) {
+            maxY = pointset[i][1];
+        }
     }
 
-    if (edge[0][1] < edge[1][1]) {
-        minY = edge[0][1] - boxSize;
-        maxY = edge[1][1] + boxSize;
-    } else {
-        minY = edge[1][1] - boxSize;
-        maxY = edge[0][1] + boxSize;
-    }
+    return [
+        maxX - minX, // width
+        maxY - minY  // height
+    ];
+}
 
+function _bBoxAround(edge) {
     return [
-        minX, minY, // tl
-        maxX, maxY  // br
+        Math.min(edge[0][0], edge[1][0]), // left
+        Math.min(edge[0][1], edge[1][1]), // top
+        Math.max(edge[0][0], edge[1][0]), // right
+        Math.max(edge[0][1], edge[1][1])  // bottom
     ];
@@ -162,8 +114,10 @@ }
 
-function _concave(convex, maxSqEdgeLen, maxSearchBBoxSize, grid) {
+function _concave(convex, maxSqEdgeLen, maxSearchArea, grid, edgeSkipList) {
     var edge,
-        border,
-        bBoxSize,
+        keyInSkipList,
+        scaleFactor,
         midPoint,
-        bBoxAround,    
+        bBoxAround,
+        bBoxWidth,
+        bBoxHeight,
         midPointInserted = false;
@@ -173,15 +127,22 @@
         edge = [convex[i], convex[i + 1]];
+        keyInSkipList = edge[0].join() + ',' + edge[1].join();
 
-        if (_sqLength(edge[0], edge[1]) < maxSqEdgeLen) { continue; }
+        if (_sqLength(edge[0], edge[1]) < maxSqEdgeLen ||
+            edgeSkipList[keyInSkipList] === true) { continue; }
 
-        border = 0;
-        bBoxSize = MIN_SEARCH_BBOX_SIZE;
-        bBoxAround = _bBoxAround(edge, bBoxSize);
+        scaleFactor = 0;
+        bBoxAround = _bBoxAround(edge);
         do {
-            bBoxAround = grid.addBorder2Bbox(bBoxAround, border);
-            bBoxSize = bBoxAround[2] - bBoxAround[0];
+            bBoxAround = grid.extendBbox(bBoxAround, scaleFactor);
+            bBoxWidth = bBoxAround[2] - bBoxAround[0];
+            bBoxHeight = bBoxAround[3] - bBoxAround[1];
+
             midPoint = _midPoint(edge, grid.rangePoints(bBoxAround), convex);            
-            border++;
-        }  while (midPoint === null && maxSearchBBoxSize > bBoxSize);
+            scaleFactor++;
+        }  while (midPoint === null && (maxSearchArea[0] > bBoxWidth || maxSearchArea[1] > bBoxHeight));
 
+        if (bBoxWidth >= maxSearchArea[0] && bBoxHeight >= maxSearchArea[1]) {
+            edgeSkipList[keyInSkipList] = true;
+        }
+
         if (midPoint !== null) {
@@ -195,3 +156,3 @@ convex.splice(i + 1, 0, midPoint);
     if (midPointInserted) {
-        return _concave(convex, maxSqEdgeLen, maxSearchBBoxSize, grid);
+        return _concave(convex, maxSqEdgeLen, maxSearchArea, grid, edgeSkipList);
     }
@@ -203,5 +164,8 @@
 function hull(pointset, concavity, format) {
-    var lower, upper, convex,
+    var convex,
+        concave,
         innerPoints,
-        maxSearchBBoxSize,
+        occupiedArea,
+        maxSearchArea,
+        cellSize,
         maxEdgeLen = concavity || 20;
@@ -213,20 +177,26 @@
 
-    pointset = _sortByX(_formatToXy(pointset, format));
-    upper = _upperTangent(pointset);
-    lower = _lowerTangent(pointset);
-    convex = lower.concat(upper);
-    convex.push(pointset[0]);
+    pointset = _sortByX(formatUtil.toXy(pointset, format));
+    occupiedArea = _occupiedArea(pointset);
+    maxSearchArea = [
+        occupiedArea[0] * MAX_SEARCH_BBOX_SIZE_PERCENT,
+        occupiedArea[1] * MAX_SEARCH_BBOX_SIZE_PERCENT
+    ];
 
-    maxSearchBBoxSize = Math.max(pointset[pointset.length - 1][0], _getMaxY(convex)) * MAX_SEARCH_BBOX_SIZE_PERCENT;
+    convex = convexHull(pointset);
     innerPoints = pointset.filter(function(pt) {
         return convex.indexOf(pt) < 0;
     });
+
+    cellSize = Math.ceil(1 / (pointset.length / (occupiedArea[0] * occupiedArea[1])));
+
+    concave = _concave(
+        convex, Math.pow(maxEdgeLen, 2),
+        maxSearchArea, grid(innerPoints, cellSize), {});
  
-    return _xyToFormat(_concave(convex, Math.pow(maxEdgeLen, 2), maxSearchBBoxSize, grid(innerPoints)), format);
+    return formatUtil.fromXy(concave, format);
 }
 
 var MAX_CONCAVE_ANGLE_COS = Math.cos(90 / (180 / Math.PI)); // angle = 90 deg
-var MIN_SEARCH_BBOX_SIZE = 5;
-var MAX_SEARCH_BBOX_SIZE_PERCENT = 0.8;
+var MAX_SEARCH_BBOX_SIZE_PERCENT = 0.6;
 
 module.exports = hull;

src/intersect.js

@@ -11,2 +11,3 @@ function ccw(x1, y1, x2, y2, x3, y3) {
       x4 = seg2[1][0], y4 = seg2[1][1];
+
     return ccw(x1, y1, x3, y3, x4, y4) !== ccw(x2, y2, x3, y3, x4, y4) && ccw(x1, y1, x2, y2, x3, y3) !== ccw(x1, y1, x2, y2, x4, y4);
@@ -13,0 +14,0 @@ }

test/grid.js

@@ -20,3 +20,3 @@ var assert = require("assert"),
 ];
-var g = grid(points);
+var g = grid(points, 10);
 
@@ -66,8 +66,8 @@ module.exports = function() {
 
-    describe('addBorder2Bbox', function() {
+    describe('extendBbox', function() {
         it('should increase bBox to 1 cell', function() {
-            assert.deepEqual(g.addBorder2Bbox([0, 0, 11, 11], 1), [-10, -10, 21, 21]);
+            assert.deepEqual(g.extendBbox([0, 0, 11, 11], 1), [-10, -10, 21, 21]);
         });
         it('should increase bBox to 2 cells', function() {
-            assert.deepEqual(g.addBorder2Bbox([0, 0, 11, 11], 2), [-20, -20, 31, 31]);
+            assert.deepEqual(g.extendBbox([0, 0, 11, 11], 2), [-20, -20, 31, 31]);
         });
@@ -74,0 +74,0 @@ });

test/hull.js

@@ -6,18 +6,18 @@ var assert = require("assert"),
     it('should return correct hull of the "?" symbol', function() {
-        var vertices = [[162, 332], [182, 299], [141, 292], [158, 264], [141, 408], [160, 400], [177, 430], [151, 442], [155, 425], [134, 430], [126, 447], [139, 466], [160, 471], [167, 447], [182, 466], [192, 442], [187, 413], [173, 403], [168, 425], [153, 413], [179, 275], [163, 292], [134, 270], [143, 315], [177, 320], [163, 311], [162, 281], [182, 255], [141, 226], [156, 235], [173, 207], [187, 230], [204, 194], [165, 189], [145, 201], [158, 167], [190, 165], [206, 145], [179, 153], [204, 114], [221, 138], [243, 112], [248, 139], [177, 122], [179, 99], [196, 82], [219, 90], [240, 75], [218, 61], [228, 53], [211, 34], [197, 51], [179, 65], [155, 70], [165, 85], [134, 80], [124, 58], [153, 44], [173, 34], [192, 27], [156, 19], [119, 32], [128, 17], [138, 36], [100, 58], [112, 73], [100, 92], [78, 100], [83, 78], [61, 63], [80, 44], [100, 26], [60, 39], [43, 71], [34, 54], [32, 90], [53, 104], [60, 82], [66, 99], [247, 94], [187, 180], [221, 168]];
-        var expected = [[248,139], [221,168], [204,194], [187,230], [182,255], [182,299], [177,320], [162,332], [160,400], [173,403], [187,413], [192,442], [182,466], [160,471], [139,466], [126,447], [134,430], [141,408], [143,315], [141,292], [134,270], [141,226], [145,201], [158,167], [177,122], [179,99], [165,85], [134,80], [100,92], [78,100], [53,104], [32,90], [34,54], [60,39], [100,26], [128,17], [156,19], [192,27], [211,34], [228,53], [240,75], [247,94], [248,139]];
-        assert.deepEqual(hull(vertices, 50), expected);
+        var points = [[162, 332], [182, 299], [141, 292], [158, 264], [141, 408], [160, 400], [177, 430], [151, 442], [155, 425], [134, 430], [126, 447], [139, 466], [160, 471], [167, 447], [182, 466], [192, 442], [187, 413], [173, 403], [168, 425], [153, 413], [179, 275], [163, 292], [134, 270], [143, 315], [177, 320], [163, 311], [162, 281], [182, 255], [141, 226], [156, 235], [173, 207], [187, 230], [204, 194], [165, 189], [145, 201], [158, 167], [190, 165], [206, 145], [179, 153], [204, 114], [221, 138], [243, 112], [248, 139], [177, 122], [179, 99], [196, 82], [219, 90], [240, 75], [218, 61], [228, 53], [211, 34], [197, 51], [179, 65], [155, 70], [165, 85], [134, 80], [124, 58], [153, 44], [173, 34], [192, 27], [156, 19], [119, 32], [128, 17], [138, 36], [100, 58], [112, 73], [100, 92], [78, 100], [83, 78], [61, 63], [80, 44], [100, 26], [60, 39], [43, 71], [34, 54], [32, 90], [53, 104], [60, 82], [66, 99], [247, 94], [187, 180], [221, 168]];
+        var expected = [[248,139], [221,168], [204,194], [187,230], [182,255], [182,299], [177,320], [160,400], [173,403], [187,413], [192,442], [182,466], [160,471], [139,466], [126,447], [141,408], [162,332], [143,315], [141,292], [134,270], [141,226], [145,201], [158,167], [177,122], [179,99], [165,85], [134,80], [100,92], [78,100], [53,104], [32,90], [34,54], [60,39], [100,26], [128,17], [156,19], [192,27], [211,34], [228,53], [240,75], [247,94], [248,139]];
+        assert.deepEqual(hull(points, 50), expected);
     });
 
     it('should return only outer hull of the polygon with hole', function() {
-        var vertices = [[141, 408], [160, 400], [177, 430], [151, 442], [155, 425], [134, 430], [126, 447], [139, 466], [160, 471], [167, 447], [182, 466], [192, 442], [187, 413], [173, 403], [165, 430], [171, 430], [177, 437], [175, 443], [172, 444], [163, 448], [156, 447], [153, 438], [154, 431], [160, 428]];
+        var points = [[141, 408], [160, 400], [177, 430], [151, 442], [155, 425], [134, 430], [126, 447], [139, 466], [160, 471], [167, 447], [182, 466], [192, 442], [187, 413], [173, 403], [165, 430], [171, 430], [177, 437], [175, 443], [172, 444], [163, 448], [156, 447], [153, 438], [154, 431], [160, 428]];
         var expected = [[192,442], [182,466], [160,471], [139,466], [126,447], [141,408], [160,400], [173,403], [187,413], [192,442]];
-        assert.deepEqual(hull(vertices, 50), expected);
+        assert.deepEqual(hull(points, 50), expected);
     });
 
     it('should return concave hull with lngs and lats', function() {
-        var vertices = [{lng:-0.206792373176235, lat:51.4911165465815 }, {lng:-0.207062672933557, lat:51.4915703125214 }, {lng:-0.207465840096923, lat:51.4912077781219 }, {lng:-0.210193421020222, lat:51.4918159814458 }, {lng:-0.214944392455692, lat:51.4929945001276 }, {lng:-0.208133371509344, lat:51.4910830915252 }, {lng:-0.214162055384851, lat:51.4905275966855 }, {lng:-0.208161917730384, lat:51.4903551232517 }, {lng:-0.209680931181673, lat:51.4901894811742 }, {lng:-0.212571431609104, lat:51.4903145141462 }, {lng:-0.216849005460861, lat:51.4921781720221 } ];
-        var expected = [{lng: -0.206792373176235, lat: 51.4911165465815 }, {lng: -0.207062672933557, lat: 51.4915703125214 }, {lng: -0.207465840096923, lat: 51.4912077781219 }, {lng: -0.210193421020222, lat: 51.4918159814458 }, {lng: -0.214944392455692, lat: 51.4929945001276 }, {lng: -0.216849005460861, lat: 51.4921781720221 }, {lng: -0.214162055384851, lat: 51.4905275966855 }, {lng: -0.212571431609104, lat: 51.4903145141462 }, {lng: -0.209680931181673, lat: 51.4901894811742 }, {lng: -0.208161917730384, lat: 51.4903551232517 }, {lng: -0.208133371509344, lat: 51.4910830915252 }, {lng: -0.206792373176235, lat: 51.4911165465815 }];
-        assert.deepEqual(hull(vertices, 0.0011, ['.lng', '.lat']), expected);
+        var points = [{lng:-0.206792373176235, lat:51.4911165465815 }, {lng:-0.207062672933557, lat:51.4915703125214 }, {lng:-0.207465840096923, lat:51.4912077781219 }, {lng:-0.210193421020222, lat:51.4918159814458 }, {lng:-0.214944392455692, lat:51.4929945001276 }, {lng:-0.208133371509344, lat:51.4910830915252 }, {lng:-0.214162055384851, lat:51.4905275966855 }, {lng:-0.208161917730384, lat:51.4903551232517 }, {lng:-0.209680931181673, lat:51.4901894811742 }, {lng:-0.212571431609104, lat:51.4903145141462 }, {lng:-0.216849005460861, lat:51.4921781720221}];
+        var expected = [{lng: -0.206792373176235, lat: 51.4911165465815 }, {lng: -0.207062672933557, lat: 51.4915703125214 }, {lng: -0.207465840096923, lat: 51.4912077781219 }, {lng: -0.210193421020222, lat: 51.4918159814458 }, {lng: -0.214944392455692, lat: 51.4929945001276 }, {lng: -0.216849005460861, lat: 51.4921781720221 }, {lng: -0.214162055384851, lat: 51.4905275966855 }, {lng: -0.212571431609104, lat: 51.4903145141462 }, {lng: -0.209680931181673, lat: 51.4901894811742 }, {lng: -0.208161917730384, lat: 51.4903551232517 }, {lng: -0.208133371509344, lat: 51.4910830915252 }, {lng: -0.206792373176235, lat: 51.4911165465815}];
+        assert.deepEqual(hull(points, 0.0011, ['.lng', '.lat']), expected);
     });
 }

New alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

16999914

increased by250.8%

Number of package files

36

increased by12.5%

Lines of code

433763

increased by0.26%

Number of lines in readme file

92

increased by4.55%

Number of medium supply chain risk alerts

3

decreased by-25%

Worsened metrics

Dev dependency count

4

increased by33.33%

No dependency changes