This is an automated email from the git hooks/post-receive script. sebastic pushed a commit to branch master in repository node-rbush.
commit 43137ede9962b4b274616e11d1696b98d6851d4a Author: Bas Couwenberg <[email protected]> Date: Thu Dec 17 04:08:09 2015 +0100 Imported Upstream version 1.4.2 --- README.md | 22 +++++++++++++--------- package.json | 44 +++++++++----------------------------------- rbush.js | 18 +++++++++++------- test/test.js | 5 +++-- 4 files changed, 36 insertions(+), 53 deletions(-) diff --git a/README.md b/README.md index e47944b..a856921 100644 --- a/README.md +++ b/README.md @@ -27,16 +27,16 @@ click to perform search under the cursor. The following sample performance test was done by generating random uniformly distributed rectangles of ~0.01% area and setting `maxEntries` to `16` (see `debug/perf.js` script). -Performed with Node.js v0.10.22 on a Retina Macbook Pro 15 (mid-2012). +Performed with Node.js v5.2.0 on a Retina Macbook Pro 15 (mid-2012). Test | RBush | [old RTree](https://github.com/imbcmdth/RTree) | Improvement ---------------------------- | ------ | ------ | ---- -insert 1M items one by one | 6.18s | 16.46s | 2.7x -1000 searches of 0.01% area | 0.07s | 2.52s | 35x -1000 searches of 1% area | 0.53s | 5.03s | 9.6x -1000 searches of 10% area | 2.45s | 16.76s | 6.8x -remove 1000 items one by one | 0.03s | 3.2s | 118x -bulk-insert 1M items | 1.99s | n/a | 8.3x +insert 1M items one by one | 4.7s | 9.26s | 2x +1000 searches of 0.01% area | 0.06s | 1.12s | 20x +1000 searches of 1% area | 0.43s | 2.73s | 6.3x +1000 searches of 10% area | 2.19s | 11.56s | 5.3x +remove 1000 items one by one | 0.02s | 1.44s | 65x +bulk-insert 1M items | 1.38s | n/a | 6.7x ## Usage @@ -134,7 +134,7 @@ Returns all items of the tree. var result = tree.collides([40, 20, 80, 70]); ``` -Returns `true` if there are any items in the given bounding box, otherwise `false`. +Returns `true` if there are any items intersecting the given bounding box, otherwise `false`. ### Export and Import @@ -157,7 +157,7 @@ check out [rbush-knn](https://github.com/mourner/rbush-knn). ## Algorithms Used -* single insertion: non-recursive R-tree insertion with overlap minimizing split routine from R*-tree (split is very effective in JS, while other R*-tree modifications like reinsertion on overflow and overlap minimizing subtree search are too slow and not worth it) +* single insertion: non-recursive R-tree insertion with overlap minimizing split routine from R\*-tree (split is very effective in JS, while other R\*-tree modifications like reinsertion on overflow and overlap minimizing subtree search are too slow and not worth it) * single deletion: non-recursive R-tree deletion using depth-first tree traversal with free-at-empty strategy (entries in underflowed nodes are not reinserted, instead underflowed nodes are kept in the tree and deleted only when empty, which is a good compromise of query vs removal performance) * bulk loading: OMT algorithm (Overlap Minimizing Top-down Bulk Loading) combined with Floyd–Rivest selection algorithm * bulk insertion: STLT algorithm (Small-Tree-Large-Tree) @@ -187,6 +187,10 @@ RBush should run on Node and all major browsers. The only caveat: IE 8 needs an ## Changelog +#### 1.4.2 — Dec 16, 2015 + +- 50% faster insertion. + #### 1.4.1 — Sep 16, 2015 - Fixed insertion in IE8. diff --git a/package.json b/package.json index 89c90f3..9ebe175 100644 --- a/package.json +++ b/package.json @@ -1,6 +1,6 @@ { "name": "rbush", - "version": "1.4.1", + "version": "1.4.2", "description": "High-performance 2D spatial index for rectangles (based on R*-tree with bulk loading and bulk insertion algorithms)", "homepage": "https://github.com/mourner/rbush";, "keywords": [ @@ -19,9 +19,10 @@ "main": "rbush.js", "devDependencies": { "benchmark": "^1.0.0", - "eslint": "^0.19.0", + "eslint": "^1.10.3", + "eslint-config-mourner": "^1.0.1", "faucet": "0.0.1", - "istanbul": "~0.3.13", + "istanbul": "~0.4.1", "rtree": "~1.4.2", "tape": "^4.0.0" }, @@ -31,41 +32,14 @@ "cov": "istanbul cover test/test.js -x test/test.js" }, "eslintConfig": { + "extends": "mourner", "rules": { - "no-use-before-define": [ - 2, - "nofunc" - ], - "camelcase": 2, - "space-after-function-name": 2, - "space-in-parens": 2, - "space-before-blocks": 2, - "space-after-keywords": 2, - "comma-style": 2, - "no-lonely-if": 2, - "no-else-return": 2, - "no-empty": 2, - "no-new": 2, - "key-spacing": 2, - "space-in-brackets": 2, - "quotes": [ - 2, - "single" - ], - "no-multi-spaces": 0, - "new-cap": 0, - "no-new-func": 0, - "curly": 0, - "no-underscore-dangle": 0, - "no-constant-condition": 0, - "no-shadow": 0 + "indent": 0, + "strict": 0, + "new-cap": 0 }, "env": { - "node": true, - "browser": true - }, - "globals": { - "define": false + "amd": true } } } diff --git a/rbush.js b/rbush.js index ca54327..f6975df 100644 --- a/rbush.js +++ b/rbush.js @@ -4,7 +4,8 @@ https://github.com/mourner/rbush */ -(function () { 'use strict'; +(function () { +'use strict'; function rbush(maxEntries, format) { @@ -233,12 +234,11 @@ rbush.prototype = { M = Math.ceil(N / Math.pow(M, height - 1)); } - // TODO eliminate recursion? - node = { children: [], height: height, - bbox: null + bbox: null, + leaf: false }; // split the items into M mostly square tiles @@ -344,7 +344,9 @@ rbush.prototype = { var newNode = { children: node.children.splice(splitIndex, node.children.length - splitIndex), - height: node.height + height: node.height, + bbox: null, + leaf: false }; if (node.leaf) newNode.leaf = true; @@ -360,7 +362,9 @@ rbush.prototype = { // split root node this.data = { children: [node, newNode], - height: node.height + 1 + height: node.height + 1, + bbox: null, + leaf: false }; calcBBox(this.data, this.toBBox); }, @@ -609,7 +613,7 @@ function swap(arr, i, j) { // export as AMD/CommonJS module or global variable -if (typeof define === 'function' && define.amd) define('rbush', function() { return rbush; }); +if (typeof define === 'function' && define.amd) define('rbush', function () { return rbush; }); else if (typeof module !== 'undefined') module.exports = rbush; else if (typeof self !== 'undefined') self.rbush = rbush; else window.rbush = rbush; diff --git a/test/test.js b/test/test.js index 9fc820b..ff016ff 100644 --- a/test/test.js +++ b/test/test.js @@ -218,7 +218,7 @@ t('#collides returns false if nothing found', function (t) { t.end(); }); -t('#all returns all points in the tree', function(t) { +t('#all returns all points in the tree', function (t) { var tree = rbush(4).load(data); var result = tree.all(); @@ -263,7 +263,8 @@ t('#insert adds an item to an existing tree correctly', function (t) { {'children':[[1,1,2,2],[2,2,2,2],[3,3,3,3]],'height':1,'leaf':true,'bbox':[1,1,3,3]} ], 'height':2, - 'bbox':[0,0,3,3] + 'bbox':[0,0,3,3], + 'leaf':false }); t.end(); }); -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/node-rbush.git _______________________________________________ Pkg-grass-devel mailing list [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-grass-devel
