This is an automated email from the git hooks/post-receive script. sebastic pushed a commit to branch master in repository node-rbush.
commit 99bb5c00346c5a1fe528b3644cca9fb4a5f9d8c5 Author: Bas Couwenberg <[email protected]> Date: Sat Apr 25 11:38:12 2015 +0200 Imported Upstream version 1.4.0 --- README.md | 13 +++++++++++++ package.json | 10 +++++----- rbush.js | 30 +++++++++++++++++++++++++++++- test/test.js | 17 +++++++++++++++++ 4 files changed, 64 insertions(+), 6 deletions(-) diff --git a/README.md b/README.md index 6022826..85b9874 100644 --- a/README.md +++ b/README.md @@ -128,6 +128,15 @@ var allItems = tree.all(); Returns all items of the tree. +### Collisions + +```js +var result = tree.collides([40, 20, 80, 70]); +``` + +Returns `true` if there are any items in the given bounding box, otherwise `false`. + + ### Export and Import ```js @@ -169,6 +178,10 @@ npm run cov # report test coverage (with more detailed report in coverage/lcov- ## Changelog +#### 1.4.0 — Apr 22, 2014 + +- Added `collides` method for fast collision detection. + #### 1.3.4 — Aug 31, 2014 - Improved bulk insertion performance for a large number of items (e.g. up to 100% for inserting a million items). diff --git a/package.json b/package.json index 41ed08a..e7d39ae 100644 --- a/package.json +++ b/package.json @@ -1,6 +1,6 @@ { "name": "rbush", - "version": "1.3.5", + "version": "1.4.0", "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,11 +19,11 @@ "main": "rbush.js", "devDependencies": { "benchmark": "^1.0.0", - "eslint": "^0.13.0", + "eslint": "^0.19.0", "faucet": "0.0.1", - "istanbul": "~0.3.2", + "istanbul": "~0.3.13", "rtree": "~1.4.2", - "tape": "^3.0.3" + "tape": "^4.0.0" }, "scripts": { "test": "eslint rbush.js test/test.js && node test/test.js | faucet", @@ -47,12 +47,12 @@ "no-empty": 2, "no-new": 2, "key-spacing": 2, - "no-multi-spaces": 2, "space-in-brackets": 2, "quotes": [ 2, "single" ], + "no-multi-spaces": 0, "new-cap": 0, "no-new-func": 0, "curly": 0, diff --git a/rbush.js b/rbush.js index 85513a0..915468e 100644 --- a/rbush.js +++ b/rbush.js @@ -57,6 +57,33 @@ rbush.prototype = { return result; }, + collides: function (bbox) { + + var node = this.data, + toBBox = this.toBBox; + + if (!intersects(bbox, node.bbox)) return false; + + var nodesToSearch = [], + i, len, child, childBBox; + + while (node) { + for (i = 0, len = node.children.length; i < len; i++) { + + child = node.children[i]; + childBBox = node.leaf ? toBBox(child) : child.bbox; + + if (intersects(bbox, childBBox)) { + if (node.leaf || contains(bbox, childBBox)) return true; + nodesToSearch.push(child); + } + } + node = nodesToSearch.pop(); + } + + return false; + }, + load: function (data) { if (!(data && data.length)) return this; @@ -529,7 +556,8 @@ function multiSelect(arr, left, right, n, compare) { } } -// sort array between left and right (inclusive) so that the smallest k elements come first (unordered) +// Floyd-Rivest selection algorithm: +// sort an array between left and right (inclusive) so that the smallest k elements come first (unordered) function select(arr, left, right, k, compare) { var n, i, z, s, sd, newLeft, newRight, t, j; diff --git a/test/test.js b/test/test.js index 92491c4..9fc820b 100644 --- a/test/test.js +++ b/test/test.js @@ -194,6 +194,16 @@ t('#search finds matching points in the tree given a bbox', function (t) { t.end(); }); +t('#collides returns true when search finds matching points', function (t) { + + var tree = rbush(4).load(data); + var result = tree.collides([40, 20, 80, 70]); + + t.same(result, true); + + t.end(); +}); + t('#search returns an empty array if nothing found', function (t) { var result = rbush(4).load(data).search([200, 200, 210, 210]); @@ -201,6 +211,13 @@ t('#search returns an empty array if nothing found', function (t) { t.end(); }); +t('#collides returns false if nothing found', function (t) { + var result = rbush(4).load(data).collides([200, 200, 210, 210]); + + t.same(result, false); + t.end(); +}); + t('#all returns all points in the tree', function(t) { var tree = rbush(4).load(data); -- 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
