[node-rbush] 01/07: Imported Upstream version 1.4.0

[Sebastiaan Couwenberg]

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 <sebastic at xs4all.nl>
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