[node-rbush] 01/07: Imported Upstream version 2.0.0
Bas Couwenberg
sebastic at debian.org
Fri Jul 1 22:30:51 UTC 2016
This is an automated email from the git hooks/post-receive script.
sebastic pushed a commit to branch master
in repository node-rbush.
commit 813d3b8ba88ea6cc6f5f0f92974b205b0ac6c228
Author: Bas Couwenberg <sebastic at xs4all.nl>
Date: Wed Jun 29 22:34:21 2016 +0200
Imported Upstream version 2.0.0
---
.gitignore | 2 +
.npmignore | 4 +
README.md | 98 ++++++++++++++--------
bench/perf.js | 109 ++++--------------------
rbush.js => index.js | 232 +++++++++++++++++++--------------------------------
package.json | 25 +++---
test/test.js | 138 +++++++++++++++---------------
viz/viz.js | 52 ++++++------
8 files changed, 281 insertions(+), 379 deletions(-)
diff --git a/.gitignore b/.gitignore
index 801e184..64b21e7 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,5 @@
node_modules
npm-debug.log
coverage
+rbush.js
+rbush.min.js
diff --git a/.npmignore b/.npmignore
new file mode 100644
index 0000000..ecf30e1
--- /dev/null
+++ b/.npmignore
@@ -0,0 +1,4 @@
+bench
+viz
+test
+.travis.yml
diff --git a/README.md b/README.md
index 3d8246c..a44de93 100644
--- a/README.md
+++ b/README.md
@@ -34,48 +34,54 @@ An optional argument to `rbush` defines the maximum number of entries in a tree
It drastically affects the performance, so you should adjust it
considering the type of data and search queries you perform.
-### Adding and Removing Data
+### Adding Data
Insert an item:
```js
-var item = [20, 40, 30, 50]; // [x1, y1, x2, y2]
+var item = {
+ minX: 20,
+ minY: 40,
+ maxX: 30,
+ maxY: 50,
+ foo: 'bar'
+};
tree.insert(item);
```
+### Removing Data
+
Remove a previously inserted item:
```js
tree.remove(item);
```
-Clear all items:
+By default, RBush removes objects by reference.
+However, you can pass a custom `equals` function to compare by value for removal,
+which is useful when you only have a copy of the object you need removed (e.g. loaded from server):
```js
-tree.clear();
-```
+tree.remove(itemCopy, function (a, b) {
+ return a.id === b.id;
+});
-Items inserted in the tree can have other arbitrary properties/elements that you can access later:
+Remove all items:
```js
-var item1 = [20, 40, 30, 50, {foo: 'bar'}];
-tree.insert(item1);
-
-var item2 = [15, 15, 30, 30];
-item2.foo = 'bar';
-tree.insert(item2);
+tree.clear();
```
### Data Format
-By default, RBush assumes the format of data points to be `[minX, minY, maxX, maxY]`
-(bounding box coordinates, or just `[x, y, x, y]` for points).
-You can customize this by providing an array with `minX`, `minY`, `maxX`, `maxY` accessor strings
+By default, RBush assumes the format of data points to be an object
+with `minX`, `minY`, `maxX` and `maxY` properties.
+You can customize this by providing an array with corresponding accessor strings
as a second argument to `rbush` like this:
```js
-var tree = rbush(9, ['.minLng', '.minLat', '.maxLng', '.maxLat']);
-tree.insert({id: 'foo', minLng: 30, minLat: 50, maxLng: 40, maxLat: 60});
+var tree = rbush(9, ['[0]', '[1]', '[0]', '[1]']); // accept [x, y] points
+tree.insert([20, 50]);
```
### Bulk-Inserting Data
@@ -83,28 +89,35 @@ tree.insert({id: 'foo', minLng: 30, minLat: 50, maxLng: 40, maxLat: 60});
Bulk-insert the given data into the tree:
```js
-tree.load([
- [10, 10, 15, 20],
- [12, 15, 40, 64.5],
- ...
-]);
+tree.load([item1, item2, ...]);
```
Bulk insertion is usually ~2-3 times faster than inserting items one by one.
-After bulk loading (bulk insertion into an empty tree), subsequent query performance is also ~20-30% better.
+After bulk loading (bulk insertion into an empty tree),
+subsequent query performance is also ~20-30% better.
-When you do bulk insertion into an existing tree, it bulk-loads the given data into a separate tree
+Note that when you do bulk insertion into an existing tree,
+it bulk-loads the given data into a separate tree
and inserts the smaller tree into the larger tree.
-This means that bulk insertion works very well for clustered data (where items are close to each other),
+This means that bulk insertion works very well for clustered data
+(where items in one update are close to each other),
but makes query performance worse if the data is scattered.
### Search
```js
-var result = tree.search([40, 20, 80, 70]);
+var result = tree.search({
+ minX: 40,
+ minY: 20,
+ maxX: 80,
+ maxY: 70
+});
```
-Returns an array of data items (points or rectangles) that the given bounding box (`[minX, minY, maxX, maxY]`) intersects.
+Returns an array of data items (points or rectangles) that the given bounding box intersects.
+
+Note that the `search` method accepts a bounding box in `{minX, minY, maxX, maxY}` format
+regardless of the format specified in the constructor (which only affects inserted objects).
```js
var allItems = tree.all();
@@ -115,7 +128,7 @@ Returns all items of the tree.
### Collisions
```js
-var result = tree.collides([40, 20, 80, 70]);
+var result = tree.collides({minX: 40, minY: 20, maxX: 80, maxY: 70});
```
Returns `true` if there are any items intersecting the given bounding box, otherwise `false`.
@@ -134,6 +147,8 @@ var tree = rbush(9).fromJSON(treeData);
Importing and exporting as JSON allows you to use RBush on both the server (using Node.js) and the browser combined,
e.g. first indexing the data on the server and and then importing the resulting tree data on the client for searching.
+Note that the `nodeSize` option passed to the constructor must be the same in both trees for export/import to work properly.
+
### K-Nearest Neighbors
For "_k_ nearest neighbors around a point" type of queries for RBush,
@@ -144,16 +159,16 @@ check out [rbush-knn](https://github.com/mourner/rbush-knn).
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 v5.2.0 on a Retina Macbook Pro 15 (mid-2012).
+Performed with Node.js v6.2.2 on a Retina Macbook Pro 15 (mid-2012).
Test | RBush | [old RTree](https://github.com/imbcmdth/RTree) | Improvement
---------------------------- | ------ | ------ | ----
-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
+insert 1M items one by one | 3.18s | 7.83s | 2.5x
+1000 searches of 0.01% area | 0.03s | 0.93s | 30x
+1000 searches of 1% area | 0.35s | 2.27s | 6.5x
+1000 searches of 10% area | 2.18s | 9.53s | 4.4x
+remove 1000 items one by one | 0.02s | 1.18s | 50x
+bulk-insert 1M items | 1.25s | n/a | 6.7x
## Algorithms Used
@@ -187,6 +202,19 @@ RBush should run on Node and all major browsers. The only caveat: IE 8 needs an
## Changelog
+#### 2.0.0 — June 29, 2016
+
+- **Breaking:** changed the default format of inserted items from `[20, 40, 30, 50]` to `{minX: 20, minY: 40, maxX: 30, maxY: 50}`.
+- **Breaking:** changed the `search` method argument format from `[20, 40, 30, 50]` to `{minX: 20, minY: 40, maxX: 30, maxY: 50}`.
+- Improved performance by up to 30%.
+- Added `equalsFn` optional argument to `remove` to be able to remove by value rather than by reference.
+- Changed the source code to use CommonJS module format. Browser builds are automatically built and published to NPM.
+- Quickselect algorithm (used internally) is now a [separate module](https://github.com/mourner/quickselect).
+
+#### 1.4.3 — May 17, 2016
+
+- Fixed an error when inserting many empty bounding boxes.
+
#### 1.4.2 — Dec 16, 2015
- 50% faster insertion.
diff --git a/bench/perf.js b/bench/perf.js
index 45c2c79..276c86e 100644
--- a/bench/perf.js
+++ b/bench/perf.js
@@ -1,3 +1,4 @@
+'use strict';
var N = 1000000,
maxFill = 16;
@@ -5,13 +6,15 @@ var N = 1000000,
console.log('number: ' + N);
console.log('maxFill: ' + maxFill);
-
function randBox(size) {
var x = Math.random() * (100 - size),
y = Math.random() * (100 - size);
- return [x, y,
- x + size * Math.random(),
- y + size * Math.random()];
+ return {
+ minX: x,
+ minY: y,
+ maxX: x + size * Math.random(),
+ maxY: y + size * Math.random()
+ };
}
function genData(N, size) {
@@ -22,45 +25,34 @@ function genData(N, size) {
return data;
}
-
var data = genData(N, 1);
+var data2 = genData(N, 1);
+var bboxes100 = genData(1000, 100 * Math.sqrt(0.1));
+var bboxes10 = genData(1000, 10);
+var bboxes1 = genData(1000, 1);
-var rbush = typeof require !== 'undefined' ? require('../rbush.js') : rbush;
-var tree = rbush(maxFill);
+var rbush = typeof require !== 'undefined' ? require('..') : rbush;
+var tree = rbush(maxFill);
console.time('insert one by one');
-for (i = 0; i < N; i++) {
+for (var i = 0; i < N; i++) {
tree.insert(data[i]);
}
console.timeEnd('insert one by one');
-
-// console.time('bulk load');
-// tree.load(data);
-// console.timeEnd('bulk load');
-
-
-var bboxes100 = genData(1000, 100 * Math.sqrt(0.1));
-
console.time('1000 searches 10%');
for (i = 0; i < 1000; i++) {
tree.search(bboxes100[i]);
}
console.timeEnd('1000 searches 10%');
-
-var bboxes10 = genData(1000, 10);
-
console.time('1000 searches 1%');
for (i = 0; i < 1000; i++) {
tree.search(bboxes10[i]);
}
console.timeEnd('1000 searches 1%');
-
-var bboxes1 = genData(1000, 1);
-
console.time('1000 searches 0.01%');
for (i = 0; i < 1000; i++) {
tree.search(bboxes1[i]);
@@ -74,91 +66,18 @@ for (i = 0; i < 1000; i++) {
}
console.timeEnd('remove 1000 one by one');
-
-var data2 = genData(N, 1);
-
console.time('bulk-insert 1M more');
tree.load(data2);
console.timeEnd('bulk-insert 1M more');
-
console.time('1000 searches 1%');
for (i = 0; i < 1000; i++) {
tree.search(bboxes10[i]);
}
console.timeEnd('1000 searches 1%');
-
console.time('1000 searches 0.01%');
for (i = 0; i < 1000; i++) {
tree.search(bboxes1[i]);
}
console.timeEnd('1000 searches 0.01%');
-
-
-// console.time('100 naive searches 1%');
-// var result;
-// for (var j = 0; j < 100; j++) {
-// result = [];
-// for (i = 0; i < N; i++) {
-// if (tree._intersects(bboxes10[j], data[i])) {
-// result.push(data[i]);
-// }
-// }
-// }
-// console.timeEnd('100 naive searches 1%');
-
-
-
-var RTree = typeof require !== 'undefined' ? require('rtree') : RTree;
-
-var tree2 = new RTree(maxFill);
-
-function convertData(data) {
- var result = [];
- for (var i = 0; i < data.length; i++) {
- result.push({x: data[i][0], y: data[i][1], w: data[i][2] - data[i][0], h: data[i][3] - data[i][1]});
- }
- return result;
-}
-
-var datab = convertData(data);
-
-console.time('old RTree load one by one');
-for (var i = 0; i < N; i++) {
- tree2.insert(datab[i], i);
-}
-console.timeEnd('old RTree load one by one');
-
-
-var bboxes100b = convertData(bboxes100);
-
-console.time('1000 searches 10% 2');
-for (i = 0; i < 1000; i++) {
- tree2.search(bboxes100b[i]);
-}
-console.timeEnd('1000 searches 10% 2');
-
-
-var bboxes10b = convertData(bboxes10);
-
-console.time('1000 searches 1% 2');
-for (i = 0; i < 1000; i++) {
- tree2.search(bboxes10b[i]);
-}
-console.timeEnd('1000 searches 1% 2');
-
-
-var bboxes1b = convertData(bboxes1);
-
-console.time('1000 searches 0.01% 2');
-for (i = 0; i < 1000; i++) {
- tree2.search(bboxes1b[i]);
-}
-console.timeEnd('1000 searches 0.01% 2');
-
-console.time('old RTree remove 1000 one by one');
-for (var i = 0; i < 1000; i++) {
- tree2.remove(datab[i], i);
-}
-console.timeEnd('old RTree remove 1000 one by one');
diff --git a/rbush.js b/index.js
similarity index 72%
rename from rbush.js
rename to index.js
index 5df616d..c96e1af 100644
--- a/rbush.js
+++ b/index.js
@@ -1,12 +1,9 @@
-/*
- (c) 2015, Vladimir Agafonkin
- RBush, a JavaScript library for high-performance 2D spatial indexing of points and rectangles.
- https://github.com/mourner/rbush
-*/
-
-(function () {
'use strict';
+module.exports = rbush;
+
+var quickselect = require('quickselect');
+
function rbush(maxEntries, format) {
if (!(this instanceof rbush)) return new rbush(maxEntries, format);
@@ -33,7 +30,7 @@ rbush.prototype = {
result = [],
toBBox = this.toBBox;
- if (!intersects(bbox, node.bbox)) return result;
+ if (!intersects(bbox, node)) return result;
var nodesToSearch = [],
i, len, child, childBBox;
@@ -42,7 +39,7 @@ rbush.prototype = {
for (i = 0, len = node.children.length; i < len; i++) {
child = node.children[i];
- childBBox = node.leaf ? toBBox(child) : child.bbox;
+ childBBox = node.leaf ? toBBox(child) : child;
if (intersects(bbox, childBBox)) {
if (node.leaf) result.push(child);
@@ -61,7 +58,7 @@ rbush.prototype = {
var node = this.data,
toBBox = this.toBBox;
- if (!intersects(bbox, node.bbox)) return false;
+ if (!intersects(bbox, node)) return false;
var nodesToSearch = [],
i, len, child, childBBox;
@@ -70,7 +67,7 @@ rbush.prototype = {
for (i = 0, len = node.children.length; i < len; i++) {
child = node.children[i];
- childBBox = node.leaf ? toBBox(child) : child.bbox;
+ childBBox = node.leaf ? toBBox(child) : child;
if (intersects(bbox, childBBox)) {
if (node.leaf || contains(bbox, childBBox)) return true;
@@ -125,16 +122,11 @@ rbush.prototype = {
},
clear: function () {
- this.data = {
- children: [],
- height: 1,
- bbox: empty(),
- leaf: true
- };
+ this.data = createNode([]);
return this;
},
- remove: function (item) {
+ remove: function (item, equalsFn) {
if (!item) return this;
var node = this.data,
@@ -154,7 +146,7 @@ rbush.prototype = {
}
if (node.leaf) { // check current node
- index = node.children.indexOf(item);
+ index = findItem(item, node.children, equalsFn);
if (index !== -1) {
// item found, remove the item and condense tree upwards
@@ -165,7 +157,7 @@ rbush.prototype = {
}
}
- if (!goingUp && !node.leaf && contains(node.bbox, bbox)) { // go down
+ if (!goingUp && !node.leaf && contains(node, bbox)) { // go down
path.push(node);
indexes.push(i);
i = 0;
@@ -185,8 +177,8 @@ rbush.prototype = {
toBBox: function (item) { return item; },
- compareMinX: function (a, b) { return a[0] - b[0]; },
- compareMinY: function (a, b) { return a[1] - b[1]; },
+ compareMinX: compareNodeMinX,
+ compareMinY: compareNodeMinY,
toJSON: function () { return this.data; },
@@ -214,12 +206,7 @@ rbush.prototype = {
if (N <= M) {
// reached leaf level; return leaf
- node = {
- children: items.slice(left, right + 1),
- height: 1,
- bbox: null,
- leaf: true
- };
+ node = createNode(items.slice(left, right + 1));
calcBBox(node, this.toBBox);
return node;
}
@@ -232,12 +219,9 @@ rbush.prototype = {
M = Math.ceil(N / Math.pow(M, height - 1));
}
- node = {
- children: [],
- height: height,
- bbox: null,
- leaf: false
- };
+ node = createNode([]);
+ node.leaf = false;
+ node.height = height;
// split the items into M mostly square tiles
@@ -280,8 +264,8 @@ rbush.prototype = {
for (i = 0, len = node.children.length; i < len; i++) {
child = node.children[i];
- area = bboxArea(child.bbox);
- enlargement = enlargedArea(bbox, child.bbox) - area;
+ area = bboxArea(child);
+ enlargement = enlargedArea(bbox, child) - area;
// choose entry with the least area enlargement
if (enlargement < minEnlargement) {
@@ -307,7 +291,7 @@ rbush.prototype = {
_insert: function (item, level, isNode) {
var toBBox = this.toBBox,
- bbox = isNode ? item.bbox : toBBox(item),
+ bbox = isNode ? item : toBBox(item),
insertPath = [];
// find the best node for accommodating the item, saving all nodes along the path too
@@ -315,7 +299,7 @@ rbush.prototype = {
// put the item into the node
node.children.push(item);
- extend(node.bbox, bbox);
+ extend(node, bbox);
// split on node overflow; propagate upwards if necessary
while (level >= 0) {
@@ -340,14 +324,9 @@ rbush.prototype = {
var splitIndex = this._chooseSplitIndex(node, m, M);
- var newNode = {
- children: node.children.splice(splitIndex, node.children.length - splitIndex),
- height: node.height,
- bbox: null,
- leaf: false
- };
-
- if (node.leaf) newNode.leaf = true;
+ var newNode = createNode(node.children.splice(splitIndex, node.children.length - splitIndex));
+ newNode.height = node.height;
+ newNode.leaf = node.leaf;
calcBBox(node, this.toBBox);
calcBBox(newNode, this.toBBox);
@@ -358,12 +337,9 @@ rbush.prototype = {
_splitRoot: function (node, newNode) {
// split root node
- this.data = {
- children: [node, newNode],
- height: node.height + 1,
- bbox: null,
- leaf: false
- };
+ this.data = createNode([node, newNode]);
+ this.data.height = node.height + 1;
+ this.data.leaf = false;
calcBBox(this.data, this.toBBox);
},
@@ -425,13 +401,13 @@ rbush.prototype = {
for (i = m; i < M - m; i++) {
child = node.children[i];
- extend(leftBBox, node.leaf ? toBBox(child) : child.bbox);
+ extend(leftBBox, node.leaf ? toBBox(child) : child);
margin += bboxMargin(leftBBox);
}
for (i = M - m - 1; i >= m; i--) {
child = node.children[i];
- extend(rightBBox, node.leaf ? toBBox(child) : child.bbox);
+ extend(rightBBox, node.leaf ? toBBox(child) : child);
margin += bboxMargin(rightBBox);
}
@@ -441,7 +417,7 @@ rbush.prototype = {
_adjustParentBBoxes: function (bbox, path, level) {
// adjust bboxes along the given tree path
for (var i = level; i >= 0; i--) {
- extend(path[i].bbox, bbox);
+ extend(path[i], bbox);
}
},
@@ -471,71 +447,97 @@ rbush.prototype = {
this.compareMinX = new Function('a', 'b', compareArr.join(format[0]));
this.compareMinY = new Function('a', 'b', compareArr.join(format[1]));
- this.toBBox = new Function('a', 'return [a' + format.join(', a') + '];');
+ this.toBBox = new Function('a',
+ 'return {minX: a' + format[0] +
+ ', minY: a' + format[1] +
+ ', maxX: a' + format[2] +
+ ', maxY: a' + format[3] + '};');
}
};
+function findItem(item, items, equalsFn) {
+ if (!equalsFn) return items.indexOf(item);
+
+ for (var i = 0; i < items.length; i++) {
+ if (equalsFn(item, items[i])) return i;
+ }
+ return -1;
+}
// calculate node's bbox from bboxes of its children
function calcBBox(node, toBBox) {
- node.bbox = distBBox(node, 0, node.children.length, toBBox);
+ distBBox(node, 0, node.children.length, toBBox, node);
}
// min bounding rectangle of node children from k to p-1
-function distBBox(node, k, p, toBBox) {
- var bbox = empty();
+function distBBox(node, k, p, toBBox, destNode) {
+ if (!destNode) destNode = createNode(null);
+ destNode.minX = Infinity;
+ destNode.minY = Infinity;
+ destNode.maxX = -Infinity;
+ destNode.maxY = -Infinity;
for (var i = k, child; i < p; i++) {
child = node.children[i];
- extend(bbox, node.leaf ? toBBox(child) : child.bbox);
+ extend(destNode, node.leaf ? toBBox(child) : child);
}
- return bbox;
+ return destNode;
}
-function empty() { return [Infinity, Infinity, -Infinity, -Infinity]; }
-
function extend(a, b) {
- a[0] = Math.min(a[0], b[0]);
- a[1] = Math.min(a[1], b[1]);
- a[2] = Math.max(a[2], b[2]);
- a[3] = Math.max(a[3], b[3]);
+ a.minX = Math.min(a.minX, b.minX);
+ a.minY = Math.min(a.minY, b.minY);
+ a.maxX = Math.max(a.maxX, b.maxX);
+ a.maxY = Math.max(a.maxY, b.maxY);
return a;
}
-function compareNodeMinX(a, b) { return a.bbox[0] - b.bbox[0]; }
-function compareNodeMinY(a, b) { return a.bbox[1] - b.bbox[1]; }
+function compareNodeMinX(a, b) { return a.minX - b.minX; }
+function compareNodeMinY(a, b) { return a.minY - b.minY; }
-function bboxArea(a) { return (a[2] - a[0]) * (a[3] - a[1]); }
-function bboxMargin(a) { return (a[2] - a[0]) + (a[3] - a[1]); }
+function bboxArea(a) { return (a.maxX - a.minX) * (a.maxY - a.minY); }
+function bboxMargin(a) { return (a.maxX - a.minX) + (a.maxY - a.minY); }
function enlargedArea(a, b) {
- return (Math.max(b[2], a[2]) - Math.min(b[0], a[0])) *
- (Math.max(b[3], a[3]) - Math.min(b[1], a[1]));
+ return (Math.max(b.maxX, a.maxX) - Math.min(b.minX, a.minX)) *
+ (Math.max(b.maxY, a.maxY) - Math.min(b.minY, a.minY));
}
function intersectionArea(a, b) {
- var minX = Math.max(a[0], b[0]),
- minY = Math.max(a[1], b[1]),
- maxX = Math.min(a[2], b[2]),
- maxY = Math.min(a[3], b[3]);
+ var minX = Math.max(a.minX, b.minX),
+ minY = Math.max(a.minY, b.minY),
+ maxX = Math.min(a.maxX, b.maxX),
+ maxY = Math.min(a.maxY, b.maxY);
return Math.max(0, maxX - minX) *
Math.max(0, maxY - minY);
}
function contains(a, b) {
- return a[0] <= b[0] &&
- a[1] <= b[1] &&
- b[2] <= a[2] &&
- b[3] <= a[3];
+ return a.minX <= b.minX &&
+ a.minY <= b.minY &&
+ b.maxX <= a.maxX &&
+ b.maxY <= a.maxY;
}
function intersects(a, b) {
- return b[0] <= a[2] &&
- b[1] <= a[3] &&
- b[2] >= a[0] &&
- b[3] >= a[1];
+ return b.minX <= a.maxX &&
+ b.minY <= a.maxY &&
+ b.maxX >= a.minX &&
+ b.maxY >= a.minY;
+}
+
+function createNode(children) {
+ return {
+ children: children,
+ height: 1,
+ leaf: true,
+ minX: Infinity,
+ minY: Infinity,
+ maxX: -Infinity,
+ maxY: -Infinity
+ };
}
// sort an array so that items come in groups of n unsorted items, with groups sorted between each other;
@@ -552,66 +554,8 @@ function multiSelect(arr, left, right, n, compare) {
if (right - left <= n) continue;
mid = left + Math.ceil((right - left) / n / 2) * n;
- select(arr, left, right, mid, compare);
+ quickselect(arr, mid, left, right, compare);
stack.push(left, mid, mid, right);
}
}
-
-// 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;
-
- while (right > left) {
- if (right - left > 600) {
- n = right - left + 1;
- i = k - left + 1;
- z = Math.log(n);
- s = 0.5 * Math.exp(2 * z / 3);
- sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (i - n / 2 < 0 ? -1 : 1);
- newLeft = Math.max(left, Math.floor(k - i * s / n + sd));
- newRight = Math.min(right, Math.floor(k + (n - i) * s / n + sd));
- select(arr, newLeft, newRight, k, compare);
- }
-
- t = arr[k];
- i = left;
- j = right;
-
- swap(arr, left, k);
- if (compare(arr[right], t) > 0) swap(arr, left, right);
-
- while (i < j) {
- swap(arr, i, j);
- i++;
- j--;
- while (compare(arr[i], t) < 0) i++;
- while (compare(arr[j], t) > 0) j--;
- }
-
- if (compare(arr[left], t) === 0) swap(arr, left, j);
- else {
- j++;
- swap(arr, j, right);
- }
-
- if (j <= k) left = j + 1;
- if (k <= j) right = j - 1;
- }
-}
-
-function swap(arr, i, j) {
- var tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
-}
-
-
-// export as AMD/CommonJS module or global variable
-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/package.json b/package.json
index 0ce090e..4f0e753 100644
--- a/package.json
+++ b/package.json
@@ -1,6 +1,6 @@
{
"name": "rbush",
- "version": "1.4.3",
+ "version": "2.0.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",
"repository": {
@@ -17,31 +17,34 @@
],
"author": "Vladimir Agafonkin",
"license": "MIT",
- "main": "rbush.js",
+ "main": "index.js",
+ "browser": "rbush.js",
"devDependencies": {
"benchmark": "^2.1.0",
+ "browserify": "^13.0.1",
"eslint": "^2.10.2",
"eslint-config-mourner": "^2.0.1",
"faucet": "0.0.1",
"istanbul": "~0.4.3",
- "rtree": "~1.4.2",
- "tape": "^4.5.1"
+ "tape": "^4.5.1",
+ "uglify-js": "^2.6.4"
},
"scripts": {
- "test": "eslint rbush.js test/test.js && node test/test.js | faucet",
+ "test": "eslint index.js test/test.js && node test/test.js | faucet",
"perf": "node ./debug/perf.js",
- "cov": "istanbul cover test/test.js -x test/test.js"
+ "cov": "istanbul cover test/test.js -x test/test.js",
+ "build": "browserify index.js -s rbush -o rbush.js",
+ "build-min": "browserify index.js -s rbush | uglifyjs -c warnings=false -m > rbush.min.js",
+ "prepublish": "npm run build && npm run build-min"
},
"eslintConfig": {
"extends": "mourner",
"rules": {
- "indent": 0,
- "strict": 0,
"new-cap": 0,
"consistent-return": 0
- },
- "env": {
- "amd": true
}
+ },
+ "dependencies": {
+ "quickselect": "^1.0.0"
}
}
diff --git a/test/test.js b/test/test.js
index 3e464f0..21d6a44 100644
--- a/test/test.js
+++ b/test/test.js
@@ -1,61 +1,53 @@
'use strict';
-/*eslint key-spacing: 0, comma-spacing: 0, quotes: 0*/
+/*eslint key-spacing: 0, comma-spacing: 0 */
-var rbush = require('../rbush.js'),
+var rbush = require('..'),
t = require('tape');
function sortedEqual(t, a, b, compare) {
+ compare = compare || defaultCompare;
t.same(a.slice().sort(compare), b.slice().sort(compare));
}
+function defaultCompare(a, b) {
+ return (a.minX - b.minX) || (a.minY - b.minY) || (a.maxX - b.maxX) || (a.maxY - b.maxY);
+}
+
function someData(n) {
var data = [];
for (var i = 0; i < n; i++) {
- data.push([i, i, i, i]);
+ data.push({minX: i, minY: i, maxX: i, maxY: i});
}
return data;
}
+function arrToBBox(arr) {
+ return {
+ minX: arr[0],
+ minY: arr[1],
+ maxX: arr[2],
+ maxY: arr[3]
+ };
+}
+
var data = [[0,0,0,0],[10,10,10,10],[20,20,20,20],[25,0,25,0],[35,10,35,10],[45,20,45,20],[0,25,0,25],[10,35,10,35],
[20,45,20,45],[25,25,25,25],[35,35,35,35],[45,45,45,45],[50,0,50,0],[60,10,60,10],[70,20,70,20],[75,0,75,0],
[85,10,85,10],[95,20,95,20],[50,25,50,25],[60,35,60,35],[70,45,70,45],[75,25,75,25],[85,35,85,35],[95,45,95,45],
[0,50,0,50],[10,60,10,60],[20,70,20,70],[25,50,25,50],[35,60,35,60],[45,70,45,70],[0,75,0,75],[10,85,10,85],
[20,95,20,95],[25,75,25,75],[35,85,35,85],[45,95,45,95],[50,50,50,50],[60,60,60,60],[70,70,70,70],[75,50,75,50],
- [85,60,85,60],[95,70,95,70],[50,75,50,75],[60,85,60,85],[70,95,70,95],[75,75,75,75],[85,85,85,85],[95,95,95,95]];
+ [85,60,85,60],[95,70,95,70],[50,75,50,75],[60,85,60,85],[70,95,70,95],[75,75,75,75],[85,85,85,85],[95,95,95,95]]
+ .map(arrToBBox);
var emptyData = [[-Infinity, -Infinity, Infinity, Infinity],[-Infinity, -Infinity, Infinity, Infinity],
[-Infinity, -Infinity, Infinity, Infinity],[-Infinity, -Infinity, Infinity, Infinity],
- [-Infinity, -Infinity, Infinity, Infinity],[-Infinity, -Infinity, Infinity, Infinity]];
-
-var testTree = {"children":[{
- "children":[
- {"children":[[0,0,0,0],[10,10,10,10],[20,20,20,20],[25,0,25,0]],"height":1,"bbox":[0,0,25,20],"leaf":true},
- {"children":[[0,25,0,25],[10,35,10,35],[25,25,25,25],[20,45,20,45]],"height":1,"bbox":[0,25,25,45],"leaf":true},
- {"children":[[50,0,50,0],[35,10,35,10],[60,10,60,10],[45,20,45,20]],"height":1,"bbox":[35,0,60,20],"leaf":true},
- {"children":[[50,25,50,25],[35,35,35,35],[60,35,60,35],[45,45,45,45]],"height":1,"bbox":[35,25,60,45],"leaf":true}
- ],"height":2,"bbox":[0,0,60,45]
-},{
- "children":[
- {"children":[[0,50,0,50],[25,50,25,50],[10,60,10,60],[20,70,20,70]],"height":1,"bbox":[0,50,25,70],"leaf":true},
- {"children":[[0,75,0,75],[25,75,25,75],[10,85,10,85],[20,95,20,95]],"height":1,"bbox":[0,75,25,95],"leaf":true},
- {"children":[[35,60,35,60],[50,50,50,50],[60,60,60,60],[45,70,45,70]],"height":1,"bbox":[35,50,60,70],"leaf":true},
- {"children":[[50,75,50,75],[60,85,60,85],[45,95,45,95],[35,85,35,85]],"height":1,"bbox":[35,75,60,95],"leaf":true}
- ],"height":2,"bbox":[0,50,60,95]
-},{
- "children":[
- {"children":[[70,20,70,20],[75,0,75,0],[75,25,75,25],[70,45,70,45]],"height":1,"bbox":[70,0,75,45],"leaf":true},
- {"children":[[75,50,75,50],[70,70,70,70],[75,75,75,75],[70,95,70,95]],"height":1,"bbox":[70,50,75,95],"leaf":true},
- {"children":[[85,10,85,10],[95,20,95,20],[85,35,85,35],[95,45,95,45]],"height":1,"bbox":[85,10,95,45],"leaf":true},
- {"children":[[85,60,85,60],[95,70,95,70],[85,85,85,85],[95,95,95,95]],"height":1,"bbox":[85,60,95,95],"leaf":true}
- ],"height":2,"bbox":[70,0,95,95]
-}],"height":3,"bbox":[0,0,95,95]};
-
+ [-Infinity, -Infinity, Infinity, Infinity],[-Infinity, -Infinity, Infinity, Infinity]].map(arrToBBox);
t('constructor accepts a format argument to customize the data format', function (t) {
var tree = rbush(4, ['.minLng', '.minLat', '.maxLng', '.maxLat']);
- t.same(tree.toBBox({minLng: 1, minLat: 2, maxLng: 3, maxLat: 4}), [1, 2, 3, 4]);
+ t.same(tree.toBBox({minLng: 1, minLat: 2, maxLng: 3, maxLat: 4}),
+ {minX: 1, minY: 2, maxX: 3, maxY: 4});
t.end();
});
@@ -72,7 +64,12 @@ t('#toBBox, #compareMinX, #compareMinY can be overriden to allow custom data str
var tree = rbush(4);
tree.toBBox = function (item) {
- return [item.minLng, item.minLat, item.maxLng, item.maxLat];
+ return {
+ minX: item.minLng,
+ minY: item.minLat,
+ maxX: item.maxLng,
+ maxY: item.maxLat
+ };
};
tree.compareMinX = function (a, b) {
return a.minLng - b.minLng;
@@ -94,29 +91,29 @@ t('#toBBox, #compareMinX, #compareMinY can be overriden to allow custom data str
return a.minLng - b.minLng || a.minLat - b.minLat;
}
- sortedEqual(t, tree.search([-180, -90, 180, 90]), [
+ sortedEqual(t, tree.search({minX: -180, minY: -90, maxX: 180, maxY: 90}), [
{minLng: -115, minLat: 45, maxLng: -105, maxLat: 55},
{minLng: 105, minLat: 45, maxLng: 115, maxLat: 55},
{minLng: 105, minLat: -55, maxLng: 115, maxLat: -45},
{minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
], byLngLat);
- sortedEqual(t, tree.search([-180, -90, 0, 90]), [
+ sortedEqual(t, tree.search({minX: -180, minY: -90, maxX: 0, maxY: 90}), [
{minLng: -115, minLat: 45, maxLng: -105, maxLat: 55},
{minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
], byLngLat);
- sortedEqual(t, tree.search([0, -90, 180, 90]), [
+ sortedEqual(t, tree.search({minX: 0, minY: -90, maxX: 180, maxY: 90}), [
{minLng: 105, minLat: 45, maxLng: 115, maxLat: 55},
{minLng: 105, minLat: -55, maxLng: 115, maxLat: -45}
], byLngLat);
- sortedEqual(t, tree.search([-180, 0, 180, 90]), [
+ sortedEqual(t, tree.search({minX: -180, minY: 0, maxX: 180, maxY: 90}), [
{minLng: -115, minLat: 45, maxLng: -105, maxLat: 55},
{minLng: 105, minLat: 45, maxLng: 115, maxLat: 55}
], byLngLat);
- sortedEqual(t, tree.search([-180, -90, 180, 0]), [
+ sortedEqual(t, tree.search({minX: -180, minY: -90, maxX: 180, maxY: 0}), [
{minLng: 105, minLat: -55, maxLng: 115, maxLat: -45},
{minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
], byLngLat);
@@ -127,7 +124,7 @@ t('#toBBox, #compareMinX, #compareMinY can be overriden to allow custom data str
t('#load bulk-loads the given data given max node entries and forms a proper search tree', function (t) {
var tree = rbush(4).load(data);
- sortedEqual(t, tree.all(), rbush(4).fromJSON(testTree).all());
+ sortedEqual(t, tree.all(), data);
t.end();
});
@@ -211,12 +208,12 @@ t('#load properly merges data of smaller or bigger tree heights', function (t) {
t('#search finds matching points in the tree given a bbox', function (t) {
var tree = rbush(4).load(data);
- var result = tree.search([40, 20, 80, 70]);
+ var result = tree.search({minX: 40, minY: 20, maxX: 80, maxY: 70});
sortedEqual(t, result, [
[70,20,70,20],[75,25,75,25],[45,45,45,45],[50,50,50,50],[60,60,60,60],[70,70,70,70],
[45,20,45,20],[45,70,45,70],[75,50,75,50],[50,25,50,25],[60,35,60,35],[70,45,70,45]
- ]);
+ ].map(arrToBBox));
t.end();
});
@@ -224,9 +221,9 @@ t('#search finds matching points in the tree given a bbox', function (t) {
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]);
+ var result = tree.collides({minX: 40, minY: 20, maxX: 80, maxY: 70});
- t.same(result, true);
+ t.same(result, true);
t.end();
});
@@ -251,48 +248,39 @@ t('#all returns all points in the tree', function (t) {
var result = tree.all();
sortedEqual(t, result, data);
- sortedEqual(t, tree.search([0, 0, 100, 100]), data);
+ sortedEqual(t, tree.search({minX: 0, minY: 0, maxX: 100, maxY: 100}), data);
t.end();
});
t('#toJSON & #fromJSON exports and imports search tree in JSON format', function (t) {
- var tree = rbush(4);
- tree.fromJSON(testTree);
-
- var tree2 = rbush(4).load(data);
+ var tree = rbush(4).load(data);
+ var tree2 = rbush(4).fromJSON(tree.data);
sortedEqual(t, tree.all(), tree2.all());
t.end();
});
t('#insert adds an item to an existing tree correctly', function (t) {
- var tree = rbush(4).load([
+ var items = [
[0, 0, 0, 0],
[1, 1, 1, 1],
- [2, 2, 2, 2]
- ]);
- tree.insert([3, 3, 3, 3]);
-
- t.same(tree.toJSON(), {
- 'children':[[0,0,0,0],[1,1,1,1],[2,2,2,2],[3,3,3,3]],
- 'leaf':true,
- 'height':1,
- 'bbox':[0,0,3,3]
- });
+ [2, 2, 2, 2],
+ [3, 3, 3, 3],
+ [1, 1, 2, 2]
+ ].map(arrToBBox);
- tree.insert([1, 1, 2, 2]);
+ var tree = rbush(4).load(items.slice(0, 3));
+
+ tree.insert(items[3]);
+ t.equal(tree.toJSON().height, 1);
+ sortedEqual(t, tree.all(), items.slice(0, 4));
+
+ tree.insert(items[4]);
+ t.equal(tree.toJSON().height, 2);
+ sortedEqual(t, tree.all(), items);
- t.same(tree.toJSON(), {
- 'children':[
- {'children':[[0,0,0,0],[1,1,1,1]],'leaf':true,'height':1,'bbox':[0,0,1,1]},
- {'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],
- 'leaf':false
- });
t.end();
});
@@ -358,6 +346,19 @@ t('#remove brings the tree to a clear state when removing everything one by one'
t.same(tree.toJSON(), rbush(4).toJSON());
t.end();
});
+t('#remove accepts an equals function', function (t) {
+ var tree = rbush(4).load(data);
+
+ var item = {minX: 20, minY: 70, maxX: 20, maxY: 70, foo: 'bar'};
+
+ tree.insert(item);
+ tree.remove(JSON.parse(JSON.stringify(item)), function (a, b) {
+ return a.foo === b.foo;
+ });
+
+ sortedEqual(t, tree.all(), data);
+ t.end();
+});
t('#clear should clear all the data in the tree', function (t) {
t.same(
@@ -371,8 +372,7 @@ t('should have chainable API', function (t) {
rbush()
.load(data)
.insert(data[0])
- .remove(data[0])
- .fromJSON(testTree);
+ .remove(data[0]);
});
t.end();
});
diff --git a/viz/viz.js b/viz/viz.js
index 0ab5982..a51aeb2 100644
--- a/viz/viz.js
+++ b/viz/viz.js
@@ -13,34 +13,31 @@ if (window.devicePixelRatio > 1) {
function randBox(size) {
var x = Math.random() * (W - size),
y = Math.random() * (W - size);
- return [
- x, y,
- x + size * Math.random(),
- y + size * Math.random()
- ];
-}
-
-function randPoint() {
- var x = Math.random() * W,
- y = Math.random() * W;
- return [x, y];
+ return {
+ minX: x,
+ minY: y,
+ maxX: x + size * Math.random(),
+ maxY: y + size * Math.random()
+ };
}
function randClusterPoint(dist) {
var x = dist + Math.random() * (W - dist * 2),
y = dist + Math.random() * (W - dist * 2);
- return [x, y];
+ return {x: x, y: y};
}
function randClusterBox(cluster, dist, size) {
- var x = cluster[0] - dist + 2 * dist * (Math.random() + Math.random() + Math.random()) / 3,
- y = cluster[1] - dist + 2 * dist * (Math.random() + Math.random() + Math.random()) / 3;
-
- return [
- x, y,
- x + size * Math.random(),
- y + size * Math.random()
- ];
+ var x = cluster.x - dist + 2 * dist * (Math.random() + Math.random() + Math.random()) / 3,
+ y = cluster.y - dist + 2 * dist * (Math.random() + Math.random() + Math.random()) / 3;
+
+ return {
+ minX: x,
+ minY: y,
+ maxX: x + size * Math.random(),
+ maxY: y + size * Math.random(),
+ item: true
+ };
}
var colors = ['#f40', '#0b0', '#37f'],
@@ -54,10 +51,10 @@ function drawTree(node, level) {
rect.push(level ? colors[(node.height - 1) % colors.length] : 'grey');
rect.push(level ? 1 / Math.pow(level, 1.2) : 0.2);
rect.push([
- Math.round(node.bbox[0]),
- Math.round(node.bbox[1]),
- Math.round(node.bbox[2] - node.bbox[0]),
- Math.round(node.bbox[3] - node.bbox[1])
+ Math.round(node.minX),
+ Math.round(node.minY),
+ Math.round(node.maxX - node.minX),
+ Math.round(node.maxY - node.minY)
]);
rects.push(rect);
@@ -85,7 +82,12 @@ function draw() {
function search(e) {
console.time('1 pixel search');
- tree.search([e.clientX, e.clientY, e.clientX + 1, e.clientY + 1]);
+ tree.search({
+ minX: e.clientX,
+ minY: e.clientY,
+ maxX: e.clientX + 1,
+ maxY: e.clientY + 1
+ });
console.timeEnd('1 pixel search');
}
--
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/node-rbush.git
More information about the Pkg-grass-devel
mailing list