[node-rbush] 01/02: Imported Upstream version 1.3.4
Johan Van de Wauw
johanvdw-guest at moszumanska.debian.org
Sat Jan 17 11:28:13 UTC 2015
This is an automated email from the git hooks/post-receive script.
johanvdw-guest pushed a commit to branch master
in repository node-rbush.
commit 76871340122533d75d80f5a7616c190587e3a7bc
Author: Johan Van de Wauw <johan.vandewauw at gmail.com>
Date: Wed Jan 7 20:54:12 2015 +0100
Imported Upstream version 1.3.4
---
.gitignore | 3 +
.travis.yml | 3 +
MIT-LICENSE | 19 ++
README.md | 216 +++++++++++++++++
bench/bulk.bench.js | 21 ++
bench/bulksearch.bench.js | 38 +++
bench/gendata.js | 26 ++
bench/insert.bench.js | 33 +++
bench/perf.js | 164 +++++++++++++
bench/search.bench.js | 40 ++++
package.json | 47 ++++
rbush.js | 587 ++++++++++++++++++++++++++++++++++++++++++++++
test/test.js | 329 ++++++++++++++++++++++++++
viz/viz-cluster.html | 72 ++++++
viz/viz-uniform.html | 68 ++++++
viz/viz.js | 96 ++++++++
16 files changed, 1762 insertions(+)
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..801e184
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+node_modules
+npm-debug.log
+coverage
diff --git a/.travis.yml b/.travis.yml
new file mode 100644
index 0000000..6e5919d
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,3 @@
+language: node_js
+node_js:
+ - "0.10"
diff --git a/MIT-LICENSE b/MIT-LICENSE
new file mode 100644
index 0000000..226ace0
--- /dev/null
+++ b/MIT-LICENSE
@@ -0,0 +1,19 @@
+Copyright (c) 2013 Vladimir Agafonkin
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..6022826
--- /dev/null
+++ b/README.md
@@ -0,0 +1,216 @@
+RBush
+=====
+
+RBush is a high-performance JavaScript library for 2D **spatial indexing** of points and rectangles
+by [Vladimir Agafonkin](http://github.com/mourner),
+based on an optimized **R-tree** data structure with **bulk insertion** support.
+
+*Spatial index* is a special data structure for points and rectangles
+that allows you to perform queries like "all items within this bounding box" very efficiently
+(e.g. hundreds of times faster than looping over all items).
+It's most commonly used in maps and data visualizations.
+
+[](https://travis-ci.org/mourner/rbush)
+
+## Demos
+
+The demos contain visualization of trees generated from 50k bulk-loaded random points.
+Open web console to see benchmarks;
+click on buttons to insert or remove items;
+click to perform search under the cursor.
+
+* [uniformly distributed random data](http://mourner.github.io/rbush/viz/viz-uniform.html)
+* [randomly clustered data](http://mourner.github.io/rbush/viz/viz-cluster.html)
+
+## Performance
+
+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).
+
+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
+
+## Usage
+
+### Creating a Tree
+
+```js
+var tree = rbush(9);
+```
+
+An optional argument to `rbush` defines the maximum number of entries in a tree node.
+It drastically affects the performance, so you should adjust it
+considering the type of data and search queries you perform.
+
+### Adding and Removing Data
+
+Insert an item:
+
+```js
+var item = [20, 40, 30, 50]; // [x1, y1, x2, y2]
+tree.insert(item);
+```
+
+Remove a previously inserted item:
+
+```js
+tree.remove(item);
+```
+
+Clear all items:
+
+```js
+tree.clear();
+```
+
+Items inserted in the tree can have other arbitrary properties/elements that you can access later:
+
+```js
+var item1 = [20, 40, 30, 50, {foo: 'bar'}];
+tree.insert(item1);
+
+var item2 = [15, 15, 30, 30];
+item2.foo = 'bar';
+tree.insert(item2);
+```
+
+### 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
+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});
+```
+
+### Bulk-Inserting Data
+
+Bulk-insert the given data into the tree:
+
+```js
+tree.load([
+ [10, 10, 15, 20],
+ [12, 15, 40, 64.5],
+ ...
+]);
+```
+
+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.
+
+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),
+but makes query performance worse if the data is scattered.
+
+### Search
+
+```js
+var result = tree.search([40, 20, 80, 70]);
+```
+
+Returns an array of data items (points or rectangles) that the given bounding box (`[minX, minY, maxX, maxY]`) intersects.
+
+```js
+var allItems = tree.all();
+```
+
+Returns all items of the tree.
+
+### Export and Import
+
+```js
+// export data as JSON object
+var treeData = tree.toJSON();
+
+// import previously exported data
+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.
+
+## 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 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)
+* search: standard non-recursive R-tree search
+
+## Papers
+
+* [R-trees: a Dynamic Index Structure For Spatial Searching](http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf)
+* [The R*-tree: An Efficient and Robust Access Method for Points and Rectangles+](http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf)
+* [OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree](http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf)
+* [Bulk Insertions into R-Trees Using the Small-Tree-Large-Tree Approach](http://www.cs.arizona.edu/~bkmoon/papers/dke06-bulk.pdf)
+* [R-Trees: Theory and Applications (book)](http://www.apress.com/9781852339777)
+
+## Development
+
+```bash
+npm install # install dependencies
+
+npm test # check the code with JSHint and run tests
+npm run perf # run performance benchmarks
+npm run cov # report test coverage (with more detailed report in coverage/lcov-report/index.html)
+```
+
+## Changelog
+
+#### 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).
+- Fixed performance regression for high node sizes.
+
+#### 1.3.3 — Aug 30, 2014
+
+- Improved bulk insertion performance by ~60-70%.
+- Improved insertion performance by ~40%.
+- Improved search performance by ~30%.
+
+#### 1.3.2 — Nov 25, 2013
+
+- Improved removal performance by ~50%. [#18](https://github.com/mourner/rbush/pull/18)
+
+#### 1.3.1 — Nov 24, 2013
+
+- Fixed minor error in the choose split axis algorithm. [#17](https://github.com/mourner/rbush/pull/17)
+- Much better test coverage (near 100%). [#6](https://github.com/mourner/rbush/issues/6)
+
+#### 1.3.0 — Nov 21, 2013
+
+- Significantly improved search performance (especially on large-bbox queries — up to 3x faster). [#11](https://github.com/mourner/rbush/pull/11)
+- Added `all` method for getting all of the tree items. [#11](https://github.com/mourner/rbush/pull/11)
+- Made `toBBox`, `compareMinX`, `compareMinY` methods public, made it possible to avoid Content Security Policy issues by overriding them for custom format. [#14](https://github.com/mourner/rbush/pull/14) [#12](https://github.com/mourner/rbush/pull/12)
+
+#### 1.2.5 — Nov 5, 2013
+
+- Fixed a bug where insertion failed on a tree that had all items removed previously. [#10](https://github.com/mourner/rbush/issues/10)
+
+#### 1.2.4 — Oct 25, 2013
+
+- Added Web Workers support. [#9](https://github.com/mourner/rbush/pull/9)
+
+#### 1.2.3 — Aug 30, 2013
+
+- Added AMD support. [#8](https://github.com/mourner/rbush/pull/8)
+
+#### 1.2.2 — Aug 27, 2013
+
+- Eliminated recursion when recalculating node bboxes (on insert, remove, load).
+
+#### 1.2.0 — Jul 19, 2013
+
+First fully functional RBush release.
diff --git a/bench/bulk.bench.js b/bench/bulk.bench.js
new file mode 100644
index 0000000..52e31b4
--- /dev/null
+++ b/bench/bulk.bench.js
@@ -0,0 +1,21 @@
+var Benchmark = require('benchmark'),
+ rbush = require('../rbush'),
+ genData = require('./gendata');
+
+var N = 10000,
+ maxFill = 16;
+
+var data = genData(N, 1);
+
+new Benchmark.Suite()
+.add('bulk loading ' + N + ' items (' + maxFill + ' node size)', function () {
+ var tree = rbush(maxFill);
+ tree.load(data);
+})
+.on('error', function(event) {
+ console.log(event.target.error);
+})
+.on('cycle', function(event) {
+ console.log(String(event.target));
+})
+.run();
diff --git a/bench/bulksearch.bench.js b/bench/bulksearch.bench.js
new file mode 100644
index 0000000..39b3af8
--- /dev/null
+++ b/bench/bulksearch.bench.js
@@ -0,0 +1,38 @@
+var Benchmark = require('benchmark'),
+ rbush = require('../rbush'),
+ genData = require('./gendata');
+
+var N = 10000,
+ maxFill = 16;
+
+var data = genData(N, 1);
+var bboxes100 = genData(1000, 100 * Math.sqrt(0.1));
+var bboxes10 = genData(1000, 10);
+var bboxes1 = genData(1000, 1);
+
+var tree = rbush(maxFill);
+tree.load(data);
+
+new Benchmark.Suite()
+.add('1000 searches 10% after bulk loading ' + N, function () {
+ for (i = 0; i < 1000; i++) {
+ tree.search(bboxes100[i]);
+ }
+})
+.add('1000 searches 1% after bulk loading ' + N, function () {
+ for (i = 0; i < 1000; i++) {
+ tree.search(bboxes10[i]);
+ }
+})
+.add('1000 searches 0.01% after bulk loading ' + N, function () {
+ for (i = 0; i < 1000; i++) {
+ tree.search(bboxes1[i]);
+ }
+})
+.on('error', function(event) {
+ console.log(event.target.error);
+})
+.on('cycle', function(event) {
+ console.log(String(event.target));
+})
+.run();
diff --git a/bench/gendata.js b/bench/gendata.js
new file mode 100644
index 0000000..27bf1ae
--- /dev/null
+++ b/bench/gendata.js
@@ -0,0 +1,26 @@
+
+module.exports = genData;
+
+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()];
+}
+
+function genData(N, size) {
+ var data = [];
+ for (var i = 0; i < N; i++) {
+ data.push(randBox(size));
+ }
+ return data;
+};
+
+genData.convert = function (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;
+}
diff --git a/bench/insert.bench.js b/bench/insert.bench.js
new file mode 100644
index 0000000..6fc7ad5
--- /dev/null
+++ b/bench/insert.bench.js
@@ -0,0 +1,33 @@
+var Benchmark = require('benchmark'),
+ rbush = require('../rbush'),
+ genData = require('./gendata');
+
+var RTree = require('rtree');
+
+
+var N = 10000,
+ maxFill = 16;
+
+var data = genData(N, 1);
+var data2 = genData.convert(data);
+
+new Benchmark.Suite()
+.add('insert ' + N + ' items (' + maxFill + ' node size)', function () {
+ var tree = rbush(maxFill);
+ for (var i = 0; i < N; i++) {
+ tree.insert(data[i]);
+ }
+})
+.add('insert ' + N + ' items (' + maxFill + ' node size), old RTree', function () {
+ var tree2 = new RTree(maxFill);
+ for (var i = 0; i < N; i++) {
+ tree2.insert(data2[i], i);
+ }
+})
+.on('error', function(event) {
+ console.log(event.target.error);
+})
+.on('cycle', function(event) {
+ console.log(String(event.target));
+})
+.run();
diff --git a/bench/perf.js b/bench/perf.js
new file mode 100644
index 0000000..45c2c79
--- /dev/null
+++ b/bench/perf.js
@@ -0,0 +1,164 @@
+
+var N = 1000000,
+ maxFill = 16;
+
+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()];
+}
+
+function genData(N, size) {
+ var data = [];
+ for (var i = 0; i < N; i++) {
+ data.push(randBox(size));
+ }
+ return data;
+}
+
+
+var data = genData(N, 1);
+
+var rbush = typeof require !== 'undefined' ? require('../rbush.js') : rbush;
+var tree = rbush(maxFill);
+
+
+console.time('insert one by one');
+for (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]);
+}
+console.timeEnd('1000 searches 0.01%');
+
+
+console.time('remove 1000 one by one');
+for (i = 0; i < 1000; i++) {
+ tree.remove(data[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/bench/search.bench.js b/bench/search.bench.js
new file mode 100644
index 0000000..0b03464
--- /dev/null
+++ b/bench/search.bench.js
@@ -0,0 +1,40 @@
+var Benchmark = require('benchmark'),
+ rbush = require('../rbush'),
+ genData = require('./gendata');
+
+var N = 10000,
+ maxFill = 16;
+
+var data = genData(N, 1);
+var bboxes100 = genData(1000, 100 * Math.sqrt(0.1));
+var bboxes10 = genData(1000, 10);
+var bboxes1 = genData(1000, 1);
+
+var tree = rbush(maxFill);
+for (var i = 0; i < N; i++) {
+ tree.insert(data[i]);
+}
+
+new Benchmark.Suite()
+.add('1000 searches 10% after bulk loading ' + N, function () {
+ for (i = 0; i < 1000; i++) {
+ tree.search(bboxes100[i]);
+ }
+})
+.add('1000 searches 1% after bulk loading ' + N, function () {
+ for (i = 0; i < 1000; i++) {
+ tree.search(bboxes10[i]);
+ }
+})
+.add('1000 searches 0.01% after bulk loading ' + N, function () {
+ for (i = 0; i < 1000; i++) {
+ tree.search(bboxes1[i]);
+ }
+})
+.on('error', function(event) {
+ console.log(event.target.error);
+})
+.on('cycle', function(event) {
+ console.log(String(event.target));
+})
+.run();
diff --git a/package.json b/package.json
new file mode 100644
index 0000000..7dd10dd
--- /dev/null
+++ b/package.json
@@ -0,0 +1,47 @@
+{
+ "name": "rbush",
+ "version": "1.3.4",
+ "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": [
+ "spatial",
+ "tree",
+ "search",
+ "rectangle",
+ "index",
+ "math"
+ ],
+ "author": "Vladimir Agafonkin",
+ "repository": {
+ "type": "git",
+ "url": "git://github.com/mourner/rbush.git"
+ },
+ "main": "rbush.js",
+ "devDependencies": {
+ "benchmark": "^1.0.0",
+ "faucet": "0.0.1",
+ "istanbul": "~0.3.0",
+ "jshint": "^2.5.5",
+ "rtree": "~1.4.2",
+ "tape": "^2.14.0"
+ },
+ "scripts": {
+ "test": "jshint rbush.js test/test.js && node test/test.js | faucet",
+ "perf": "node ./debug/perf.js",
+ "cov": "istanbul cover test/test.js -x test/test.js"
+ },
+ "jshintConfig": {
+ "unused": "true",
+ "undef": true,
+ "trailing": true,
+ "eqeqeq": true,
+ "es3": true,
+ "indent": 4,
+ "node": true,
+ "browser": true,
+ "worker": true,
+ "globals": {
+ "define": false
+ }
+ }
+}
diff --git a/rbush.js b/rbush.js
new file mode 100644
index 0000000..b151197
--- /dev/null
+++ b/rbush.js
@@ -0,0 +1,587 @@
+/*
+ (c) 2013, Vladimir Agafonkin
+ RBush, a JavaScript library for high-performance 2D spatial indexing of points and rectangles.
+ https://github.com/mourner/rbush
+*/
+
+(function () { 'use strict';
+
+function rbush(maxEntries, format) {
+
+ // jshint newcap: false, validthis: true
+ if (!(this instanceof rbush)) return new rbush(maxEntries, format);
+
+ // max entries in a node is 9 by default; min node fill is 40% for best performance
+ this._maxEntries = Math.max(4, maxEntries || 9);
+ this._minEntries = Math.max(2, Math.ceil(this._maxEntries * 0.4));
+
+ if (format) {
+ this._initFormat(format);
+ }
+
+ this.clear();
+}
+
+rbush.prototype = {
+
+ all: function () {
+ return this._all(this.data, []);
+ },
+
+ search: function (bbox) {
+
+ var node = this.data,
+ result = [],
+ toBBox = this.toBBox;
+
+ if (!intersects(bbox, node.bbox)) return result;
+
+ 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) result.push(child);
+ else if (contains(bbox, childBBox)) this._all(child, result);
+ else nodesToSearch.push(child);
+ }
+ }
+ node = nodesToSearch.pop();
+ }
+
+ return result;
+ },
+
+ load: function (data) {
+ if (!(data && data.length)) return this;
+
+ if (data.length < this._minEntries) {
+ for (var i = 0, len = data.length; i < len; i++) {
+ this.insert(data[i]);
+ }
+ return this;
+ }
+
+ // recursively build the tree with the given data from stratch using OMT algorithm
+ var node = this._build(data.slice(), 0, data.length - 1, 0);
+
+ if (!this.data.children.length) {
+ // save as is if tree is empty
+ this.data = node;
+
+ } else if (this.data.height === node.height) {
+ // split root if trees have the same height
+ this._splitRoot(this.data, node);
+
+ } else {
+ if (this.data.height < node.height) {
+ // swap trees if inserted one is bigger
+ var tmpNode = this.data;
+ this.data = node;
+ node = tmpNode;
+ }
+
+ // insert the small tree into the large tree at appropriate level
+ this._insert(node, this.data.height - node.height - 1, true);
+ }
+
+ return this;
+ },
+
+ insert: function (item) {
+ if (item) this._insert(item, this.data.height - 1);
+ return this;
+ },
+
+ clear: function () {
+ this.data = {
+ children: [],
+ height: 1,
+ bbox: empty(),
+ leaf: true
+ };
+ return this;
+ },
+
+ remove: function (item) {
+ if (!item) return this;
+
+ var node = this.data,
+ bbox = this.toBBox(item),
+ path = [],
+ indexes = [],
+ i, parent, index, goingUp;
+
+ // depth-first iterative tree traversal
+ while (node || path.length) {
+
+ if (!node) { // go up
+ node = path.pop();
+ parent = path[path.length - 1];
+ i = indexes.pop();
+ goingUp = true;
+ }
+
+ if (node.leaf) { // check current node
+ index = node.children.indexOf(item);
+
+ if (index !== -1) {
+ // item found, remove the item and condense tree upwards
+ node.children.splice(index, 1);
+ path.push(node);
+ this._condense(path);
+ return this;
+ }
+ }
+
+ if (!goingUp && !node.leaf && contains(node.bbox, bbox)) { // go down
+ path.push(node);
+ indexes.push(i);
+ i = 0;
+ parent = node;
+ node = node.children[0];
+
+ } else if (parent) { // go right
+ i++;
+ node = parent.children[i];
+ goingUp = false;
+
+ } else node = null; // nothing found
+ }
+
+ return this;
+ },
+
+ toBBox: function (item) { return item; },
+
+ compareMinX: function (a, b) { return a[0] - b[0]; },
+ compareMinY: function (a, b) { return a[1] - b[1]; },
+
+ toJSON: function () { return this.data; },
+
+ fromJSON: function (data) {
+ this.data = data;
+ return this;
+ },
+
+ _all: function (node, result) {
+ var nodesToSearch = [];
+ while (node) {
+ if (node.leaf) result.push.apply(result, node.children);
+ else nodesToSearch.push.apply(nodesToSearch, node.children);
+
+ node = nodesToSearch.pop();
+ }
+ return result;
+ },
+
+ _build: function (items, left, right, height) {
+
+ var N = right - left + 1,
+ M = this._maxEntries,
+ node;
+
+ if (N <= M) {
+ // reached leaf level; return leaf
+ node = {
+ children: items.slice(left, right + 1),
+ height: 1,
+ bbox: null,
+ leaf: true
+ };
+ calcBBox(node, this.toBBox);
+ return node;
+ }
+
+ if (!height) {
+ // target height of the bulk-loaded tree
+ height = Math.ceil(Math.log(N) / Math.log(M));
+
+ // target number of root entries to maximize storage utilization
+ M = Math.ceil(N / Math.pow(M, height - 1));
+ }
+
+ // TODO eliminate recursion?
+
+ node = {
+ children: [],
+ height: height,
+ bbox: null
+ };
+
+ // split the items into M mostly square tiles
+
+ var N2 = Math.ceil(N / M),
+ N1 = N2 * Math.ceil(Math.sqrt(M)),
+ i, j, right2, right3;
+
+ multiSelect(items, left, right, N1, this.compareMinX);
+
+ for (i = left; i <= right; i += N1) {
+
+ right2 = Math.min(i + N1 - 1, right);
+
+ multiSelect(items, i, right2, N2, this.compareMinY);
+
+ for (j = i; j <= right2; j += N2) {
+
+ right3 = Math.min(j + N2 - 1, right2);
+
+ // pack each entry recursively
+ node.children.push(this._build(items, j, right3, height - 1));
+ }
+ }
+
+ calcBBox(node, this.toBBox);
+
+ return node;
+ },
+
+ _chooseSubtree: function (bbox, node, level, path) {
+
+ var i, len, child, targetNode, area, enlargement, minArea, minEnlargement;
+
+ while (true) {
+ path.push(node);
+
+ if (node.leaf || path.length - 1 === level) break;
+
+ minArea = minEnlargement = Infinity;
+
+ for (i = 0, len = node.children.length; i < len; i++) {
+ child = node.children[i];
+ area = bboxArea(child.bbox);
+ enlargement = enlargedArea(bbox, child.bbox) - area;
+
+ // choose entry with the least area enlargement
+ if (enlargement < minEnlargement) {
+ minEnlargement = enlargement;
+ minArea = area < minArea ? area : minArea;
+ targetNode = child;
+
+ } else if (enlargement === minEnlargement) {
+ // otherwise choose one with the smallest area
+ if (area < minArea) {
+ minArea = area;
+ targetNode = child;
+ }
+ }
+ }
+
+ node = targetNode;
+ }
+
+ return node;
+ },
+
+ _insert: function (item, level, isNode) {
+
+ var toBBox = this.toBBox,
+ bbox = isNode ? item.bbox : toBBox(item),
+ insertPath = [];
+
+ // find the best node for accommodating the item, saving all nodes along the path too
+ var node = this._chooseSubtree(bbox, this.data, level, insertPath);
+
+ // put the item into the node
+ node.children.push(item);
+ extend(node.bbox, bbox);
+
+ // split on node overflow; propagate upwards if necessary
+ while (level >= 0) {
+ if (insertPath[level].children.length > this._maxEntries) {
+ this._split(insertPath, level);
+ level--;
+ } else break;
+ }
+
+ // adjust bboxes along the insertion path
+ this._adjustParentBBoxes(bbox, insertPath, level);
+ },
+
+ // split overflowed node into two
+ _split: function (insertPath, level) {
+
+ var node = insertPath[level],
+ M = node.children.length,
+ m = this._minEntries;
+
+ this._chooseSplitAxis(node, m, M);
+
+ var newNode = {
+ children: node.children.splice(this._chooseSplitIndex(node, m, M)),
+ height: node.height
+ };
+
+ if (node.leaf) newNode.leaf = true;
+
+ calcBBox(node, this.toBBox);
+ calcBBox(newNode, this.toBBox);
+
+ if (level) insertPath[level - 1].children.push(newNode);
+ else this._splitRoot(node, newNode);
+ },
+
+ _splitRoot: function (node, newNode) {
+ // split root node
+ this.data = {
+ children: [node, newNode],
+ height: node.height + 1
+ };
+ calcBBox(this.data, this.toBBox);
+ },
+
+ _chooseSplitIndex: function (node, m, M) {
+
+ var i, bbox1, bbox2, overlap, area, minOverlap, minArea, index;
+
+ minOverlap = minArea = Infinity;
+
+ for (i = m; i <= M - m; i++) {
+ bbox1 = distBBox(node, 0, i, this.toBBox);
+ bbox2 = distBBox(node, i, M, this.toBBox);
+
+ overlap = intersectionArea(bbox1, bbox2);
+ area = bboxArea(bbox1) + bboxArea(bbox2);
+
+ // choose distribution with minimum overlap
+ if (overlap < minOverlap) {
+ minOverlap = overlap;
+ index = i;
+
+ minArea = area < minArea ? area : minArea;
+
+ } else if (overlap === minOverlap) {
+ // otherwise choose distribution with minimum area
+ if (area < minArea) {
+ minArea = area;
+ index = i;
+ }
+ }
+ }
+
+ return index;
+ },
+
+ // sorts node children by the best axis for split
+ _chooseSplitAxis: function (node, m, M) {
+
+ var compareMinX = node.leaf ? this.compareMinX : compareNodeMinX,
+ compareMinY = node.leaf ? this.compareMinY : compareNodeMinY,
+ xMargin = this._allDistMargin(node, m, M, compareMinX),
+ yMargin = this._allDistMargin(node, m, M, compareMinY);
+
+ // if total distributions margin value is minimal for x, sort by minX,
+ // otherwise it's already sorted by minY
+ if (xMargin < yMargin) node.children.sort(compareMinX);
+ },
+
+ // total margin of all possible split distributions where each node is at least m full
+ _allDistMargin: function (node, m, M, compare) {
+
+ node.children.sort(compare);
+
+ var toBBox = this.toBBox,
+ leftBBox = distBBox(node, 0, m, toBBox),
+ rightBBox = distBBox(node, M - m, M, toBBox),
+ margin = bboxMargin(leftBBox) + bboxMargin(rightBBox),
+ i, child;
+
+ for (i = m; i < M - m; i++) {
+ child = node.children[i];
+ extend(leftBBox, node.leaf ? toBBox(child) : child.bbox);
+ margin += bboxMargin(leftBBox);
+ }
+
+ for (i = M - m - 1; i >= m; i--) {
+ child = node.children[i];
+ extend(rightBBox, node.leaf ? toBBox(child) : child.bbox);
+ margin += bboxMargin(rightBBox);
+ }
+
+ return margin;
+ },
+
+ _adjustParentBBoxes: function (bbox, path, level) {
+ // adjust bboxes along the given tree path
+ for (var i = level; i >= 0; i--) {
+ extend(path[i].bbox, bbox);
+ }
+ },
+
+ _condense: function (path) {
+ // go through the path, removing empty nodes and updating bboxes
+ for (var i = path.length - 1, siblings; i >= 0; i--) {
+ if (path[i].children.length === 0) {
+ if (i > 0) {
+ siblings = path[i - 1].children;
+ siblings.splice(siblings.indexOf(path[i]), 1);
+
+ } else this.clear();
+
+ } else calcBBox(path[i], this.toBBox);
+ }
+ },
+
+ _initFormat: function (format) {
+ // data format (minX, minY, maxX, maxY accessors)
+
+ // uses eval-type function compilation instead of just accepting a toBBox function
+ // because the algorithms are very sensitive to sorting functions performance,
+ // so they should be dead simple and without inner calls
+
+ // jshint evil: true
+
+ var compareArr = ['return a', ' - b', ';'];
+
+ 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') + '];');
+ }
+};
+
+
+// calculate node's bbox from bboxes of its children
+function calcBBox(node, toBBox) {
+ node.bbox = distBBox(node, 0, node.children.length, toBBox);
+}
+
+// min bounding rectangle of node children from k to p-1
+function distBBox(node, k, p, toBBox) {
+ var bbox = empty();
+
+ for (var i = k, child; i < p; i++) {
+ child = node.children[i];
+ extend(bbox, node.leaf ? toBBox(child) : child.bbox);
+ }
+
+ return bbox;
+}
+
+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]);
+ 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 bboxArea(a) { return (a[2] - a[0]) * (a[3] - a[1]); }
+function bboxMargin(a) { return (a[2] - a[0]) + (a[3] - a[1]); }
+
+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]));
+}
+
+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]);
+
+ 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];
+}
+
+function intersects (a, b) {
+ return b[0] <= a[2] &&
+ b[1] <= a[3] &&
+ b[2] >= a[0] &&
+ b[3] >= a[1];
+}
+
+// sort an array so that items come in groups of n unsorted items, with groups sorted between each other;
+// combines selection algorithm with binary divide & conquer approach
+
+function multiSelect(arr, left, right, n, compare) {
+ var stack = [left, right],
+ mid;
+
+ while (stack.length) {
+ right = stack.pop();
+ left = stack.pop();
+
+ if (right - left <= n) continue;
+
+ mid = left + Math.ceil((right - left) / n / 2) * n;
+ select(arr, left, right, mid, compare);
+
+ stack.push(left, mid, mid, right);
+ }
+}
+
+// sort 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(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
new file mode 100644
index 0000000..4739142
--- /dev/null
+++ b/test/test.js
@@ -0,0 +1,329 @@
+var rbush = require('../rbush.js'),
+ t = require('tape');
+
+function sortedEqual(t, a, b, compare) {
+ t.same(a.slice().sort(compare), b.slice().sort(compare));
+}
+
+function someData(n) {
+ var data = [];
+
+ for (var i = 0; i < n; i++) {
+ data.push([i, i, i, i]);
+ }
+ return data;
+}
+
+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]];
+
+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]};
+
+
+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.end();
+});
+
+t('constructor uses 9 max entries by default', function (t) {
+ var tree = rbush().load(someData(9));
+ t.equal(tree.toJSON().height, 1);
+
+ var tree2 = rbush().load(someData(10));
+ t.equal(tree2.toJSON().height, 2);
+ t.end();
+});
+
+t('#toBBox, #compareMinX, #compareMinY can be overriden to allow custom data structures', function (t) {
+
+ var tree = rbush(4);
+ tree.toBBox = function (item) {
+ return [item.minLng, item.minLat, item.maxLng, item.maxLat];
+ };
+ tree.compareMinX = function (a, b) {
+ return a.minLng - b.minLng;
+ };
+ tree.compareMinY = function (a, b) {
+ return a.minLat - b.minLat;
+ };
+
+ var data = [
+ {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}
+ ];
+
+ tree.load(data);
+
+ function byLngLat (a, b) {
+ return a.minLng - b.minLng || a.minLat - b.minLat;
+ }
+
+ sortedEqual(t, tree.search([-180, -90, 180, 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]), [
+ {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]), [
+ {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]), [
+ {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]), [
+ {minLng: 105, minLat: -55, maxLng: 115, maxLat: -45},
+ {minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
+ ], byLngLat);
+
+ t.end();
+});
+
+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());
+
+ t.end();
+});
+
+t('#load uses standard insertion when given a low number of items', function (t) {
+
+ var tree = rbush(8)
+ .load(data)
+ .load(data.slice(0, 3));
+
+ var tree2 = rbush(8)
+ .load(data)
+ .insert(data[0])
+ .insert(data[1])
+ .insert(data[2]);
+
+ t.same(tree.toJSON(), tree2.toJSON());
+ t.end();
+});
+
+t('#load does nothing if loading empty data', function (t) {
+ var tree = rbush().load([]);
+
+ t.same(tree.toJSON(), rbush().toJSON());
+ t.end();
+});
+
+t('#load properly splits tree root when merging trees of the same height', function (t) {
+ var tree = rbush(4)
+ .load(data)
+ .load(data);
+
+ t.equal(tree.toJSON().height, 4);
+ sortedEqual(t, tree.all(), data.concat(data));
+
+ t.end();
+});
+
+t('#load properly merges data of smaller or bigger tree heights', function (t) {
+ var smaller = someData(10);
+
+ var tree1 = rbush(4)
+ .load(data)
+ .load(smaller);
+
+ var tree2 = rbush(4)
+ .load(smaller)
+ .load(data);
+
+ t.equal(tree1.toJSON().height, tree2.toJSON().height);
+
+ sortedEqual(t, tree1.all(), data.concat(smaller));
+ sortedEqual(t, tree2.all(), data.concat(smaller));
+
+ t.end();
+});
+
+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]);
+
+ 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]
+ ]);
+
+ t.end();
+});
+
+t('#search returns an empty array if nothing found', function (t) {
+ var result = rbush(4).load(data).search([200, 200, 210, 210]);
+
+ t.same(result, []);
+ t.end();
+});
+
+t('#all returns all points in the tree', function(t) {
+
+ var tree = rbush(4).load(data);
+ var result = tree.all();
+
+ sortedEqual(t, result, data);
+ sortedEqual(t, tree.search([0, 0, 100, 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);
+
+ 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([
+ [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]
+ });
+
+ tree.insert([1, 1, 2, 2]);
+
+ 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]
+ });
+ t.end();
+});
+
+t('#insert does nothing if given undefined', function (t) {
+ t.same(
+ rbush().load(data),
+ rbush().load(data).insert());
+ t.end();
+});
+
+t('#insert forms a valid tree if items are inserted one by one', function (t) {
+ var tree = rbush(4);
+
+ for (var i = 0; i < data.length; i++) {
+ tree.insert(data[i]);
+ }
+
+ var tree2 = rbush(4).load(data);
+
+ t.ok(tree.toJSON().height - tree2.toJSON().height <= 1);
+
+ sortedEqual(t, tree.all(), tree2.all());
+ t.end();
+});
+
+t('#remove removes items correctly', function (t) {
+ var tree = rbush(4).load(data);
+
+ var len = data.length;
+
+ tree.remove(data[0]);
+ tree.remove(data[1]);
+ tree.remove(data[2]);
+
+ tree.remove(data[len - 1]);
+ tree.remove(data[len - 2]);
+ tree.remove(data[len - 3]);
+
+ sortedEqual(t,
+ data.slice(3, len - 3),
+ tree.all());
+ t.end();
+});
+t('#remove does nothing if nothing found', function (t) {
+ t.same(
+ rbush().load(data),
+ rbush().load(data).remove([13, 13, 13, 13]));
+ t.end();
+});
+t('#remove does nothing if given undefined', function (t) {
+ t.same(
+ rbush().load(data),
+ rbush().load(data).remove());
+ t.end();
+});
+t('#remove brings the tree to a clear state when removing everything one by one', function (t) {
+ var tree = rbush(4).load(data);
+
+ for (var i = 0; i < data.length; i++) {
+ tree.remove(data[i]);
+ }
+
+ t.same(tree.toJSON(), rbush(4).toJSON());
+ t.end();
+});
+
+t('#clear should clear all the data in the tree', function (t) {
+ t.same(
+ rbush(4).load(data).clear().toJSON(),
+ rbush(4).toJSON());
+ t.end();
+});
+
+t('should have chainable API', function (t) {
+ t.doesNotThrow(function () {
+ rbush()
+ .load(data)
+ .insert(data[0])
+ .remove(data[0])
+ .fromJSON(testTree);
+ });
+ t.end();
+});
diff --git a/viz/viz-cluster.html b/viz/viz-cluster.html
new file mode 100644
index 0000000..a6298df
--- /dev/null
+++ b/viz/viz-cluster.html
@@ -0,0 +1,72 @@
+<!doctype html>
+
+<title>RBush Tree Visualization</title>
+<canvas id="canvas" width="701" height="701"></canvas>
+<br>
+<button id="insert1">Insert 50000</button>
+<button id="insert2">Insert 1000</button>
+<button id="insert3">Bulk-insert 50000</button>
+<button id="insert4">Bulk-insert 1000</button>
+<button id="remove">Remove leftmost 10000</button>
+
+<script src="../rbush.js"></script>
+<script src="viz.js"></script>
+<script>
+
+var N = 100000,
+ M = 30,
+ R = 100;
+
+function genData(N, M, R) {
+ var data = [];
+ for (var i = 0; i < M; i++) {
+ var cluster = randClusterPoint(R);
+
+ for (var j = 0; j < N / M; j++) {
+ data.push(randClusterBox(cluster, R, 1));
+ }
+ }
+ return data;
+}
+
+var tree = rbush(16);
+var data = [];
+
+genBulkInsert(N, M)();
+
+function genInsertOneByOne(K, M) {
+ return function () {
+ var data2 = genData(K, M, R);
+
+ console.time('insert ' + K + ' items');
+ for (var i = 0; i < K; i++) {
+ tree.insert(data2[i]);
+ }
+ console.timeEnd('insert ' + K + ' items');
+
+ draw();
+ };
+}
+
+function genBulkInsert(K, M) {
+ return function () {
+ var data2 = genData(K, M, R);
+
+ console.time('bulk-insert ' + K + ' items');
+ tree.load(data2);
+ console.timeEnd('bulk-insert ' + K + ' items');
+
+ data = data.concat(data2);
+
+ draw();
+ };
+}
+
+document.getElementById('insert1').onclick = genInsertOneByOne(50000, M);
+document.getElementById('insert2').onclick = genInsertOneByOne(1000, 1);
+document.getElementById('insert3').onclick = genBulkInsert(50000, M);
+document.getElementById('insert4').onclick = genBulkInsert(1000, 1);
+document.getElementById('canvas').onclick = search;
+document.getElementById('remove').onclick = remove;
+
+</script>
diff --git a/viz/viz-uniform.html b/viz/viz-uniform.html
new file mode 100644
index 0000000..4a5bb3c
--- /dev/null
+++ b/viz/viz-uniform.html
@@ -0,0 +1,68 @@
+<!doctype html>
+
+<title>RBush Tree Visualization</title>
+<canvas id="canvas" width="701" height="701"></canvas>
+<br>
+<button id="insert1">Insert 50000</button>
+<button id="insert2">Insert 1000</button>
+<button id="insert3">Bulk-insert 50000</button>
+<button id="insert4">Bulk-insert 1000</button>
+<button id="remove">Remove leftmost 10000</button>
+
+<script src="../rbush.js"></script>
+<script src="viz.js"></script>
+<script>
+
+var N = 50000;
+
+function genData(N) {
+ var data = [];
+ for (var i = 0; i < N; i++) {
+ data[i] = randBox(1);
+ }
+ return data;
+}
+
+var tree = rbush(10);
+var data = [];
+
+genBulkInsert(N)();
+
+function genInsertOneByOne(K) {
+ return function () {
+ var data2 = genData(K);
+
+ console.time('insert ' + K + ' items');
+ for (var i = 0; i < K; i++) {
+ tree.insert(data2[i]);
+ }
+ console.timeEnd('insert ' + K + ' items');
+
+ data = data.concat(data2);
+
+ draw();
+ };
+}
+
+function genBulkInsert(K) {
+ return function () {
+ var data2 = genData(K);
+
+ console.time('bulk-insert ' + K + ' items');
+ tree.load(data2);
+ console.timeEnd('bulk-insert ' + K + ' items');
+
+ data = data.concat(data2);
+
+ draw();
+ };
+}
+
+document.getElementById('insert1').onclick = genInsertOneByOne(50000);
+document.getElementById('insert2').onclick = genInsertOneByOne(1000);
+document.getElementById('insert3').onclick = genBulkInsert(50000);
+document.getElementById('insert4').onclick = genBulkInsert(1000);
+document.getElementById('canvas').onclick = search;
+document.getElementById('remove').onclick = remove;
+
+</script>
diff --git a/viz/viz.js b/viz/viz.js
new file mode 100644
index 0000000..e6d3714
--- /dev/null
+++ b/viz/viz.js
@@ -0,0 +1,96 @@
+var W = 700,
+ canvas = document.getElementById('canvas'),
+ ctx = canvas.getContext('2d');
+
+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];
+}
+
+function randClusterPoint(dist) {
+ var x = dist + Math.random() * (W - dist * 2),
+ y = dist + Math.random() * (W - dist * 2);
+ return [x, 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 colors = ['#f40', '#37f', '#0b0'],
+ rects;
+
+function drawTree(node, level) {
+ if (!node) { return; }
+
+ var rect = [];
+
+ rect.push(level ? colors[(level - 1) % colors.length] : 'grey');
+ rect.push(level ? 1 / level : 1);
+ rect.push([
+ Math.round(node.bbox[0]) + 0.5,
+ Math.round(node.bbox[1]) + 0.5,
+ Math.round(node.bbox[2] - node.bbox[0]),
+ Math.round(node.bbox[3] - node.bbox[1])
+ ]);
+
+ rects.push(rect);
+
+ if (node.leaf) return;
+ if (level === 6) { return; }
+
+ for (var i = 0; i < node.children.length; i++) {
+ drawTree(node.children[i], level + 1);
+ }
+}
+
+function draw() {
+ rects = [];
+ drawTree(tree.data, 0);
+
+ ctx.fillStyle = 'white';
+ ctx.fillRect(0, 0, W + 1, W + 1);
+
+ for (var i = rects.length - 1; i >= 0; i--) {
+ ctx.strokeStyle = rects[i][0];
+ ctx.globalAlpha = rects[i][1];
+ ctx.strokeRect.apply(ctx, rects[i][2]);
+ }
+}
+
+function search(e) {
+ console.time('1 pixel search');
+ tree.search([e.clientX, e.clientY, e.clientX + 1, e.clientY + 1]);
+ console.timeEnd('1 pixel search');
+}
+
+function remove() {
+ data.sort(tree.compareMinX);
+ console.time('remove 10000');
+ for (var i = 0; i < 10000; i++) {
+ tree.remove(data[i]);
+ }
+ console.timeEnd('remove 10000');
+
+ data.splice(0, 10000);
+
+ draw();
+};
--
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