[node-rbush] 01/07: Imported Upstream version 1.4.3
Sebastiaan Couwenberg
sebastic at moszumanska.debian.org
Wed May 18 05:40:31 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 d10b604f8125f97491ac2cd91c6dec7d7cf75034
Author: Bas Couwenberg <sebastic at xs4all.nl>
Date: Wed May 18 07:30:31 2016 +0200
Imported Upstream version 1.4.3
---
.travis.yml | 3 ++-
MIT-LICENSE | 2 +-
README.md | 40 ++++++++++++++++++++--------------------
package.json | 24 +++++++++++++-----------
rbush.js | 6 +-----
test/test.js | 27 +++++++++++++++++++++++++++
6 files changed, 64 insertions(+), 38 deletions(-)
diff --git a/.travis.yml b/.travis.yml
index 6e5919d..8131feb 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -1,3 +1,4 @@
language: node_js
node_js:
- - "0.10"
+ - "4"
+ - "stable"
diff --git a/MIT-LICENSE b/MIT-LICENSE
index a4e7516..94d9eed 100644
--- a/MIT-LICENSE
+++ b/MIT-LICENSE
@@ -1,4 +1,4 @@
-Copyright (c) 2015 Vladimir Agafonkin
+Copyright (c) 2016 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
diff --git a/README.md b/README.md
index a856921..3d8246c 100644
--- a/README.md
+++ b/README.md
@@ -1,16 +1,16 @@
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.
+RBush is a high-performance JavaScript library for 2D **spatial indexing** of points and rectangles.
+It's 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)
+[](https://travis-ci.org/mourner/rbush)
+[](https://github.com/mourner/projects)
## Demos
@@ -22,22 +22,6 @@ 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 v5.2.0 on a Retina Macbook Pro 15 (mid-2012).
-
-Test | RBush | [old RTree](https://github.com/imbcmdth/RTree) | Improvement
----------------------------- | ------ | ------ | ----
-insert 1M items one by one | 4.7s | 9.26s | 2x
-1000 searches of 0.01% area | 0.06s | 1.12s | 20x
-1000 searches of 1% area | 0.43s | 2.73s | 6.3x
-1000 searches of 10% area | 2.19s | 11.56s | 5.3x
-remove 1000 items one by one | 0.02s | 1.44s | 65x
-bulk-insert 1M items | 1.38s | n/a | 6.7x
-
## Usage
### Creating a Tree
@@ -155,6 +139,22 @@ e.g. first indexing the data on the server and and then importing the resulting
For "_k_ nearest neighbors around a point" type of queries for RBush,
check out [rbush-knn](https://github.com/mourner/rbush-knn).
+## 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 v5.2.0 on a Retina Macbook Pro 15 (mid-2012).
+
+Test | RBush | [old RTree](https://github.com/imbcmdth/RTree) | Improvement
+---------------------------- | ------ | ------ | ----
+insert 1M items one by one | 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
+
## 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)
diff --git a/package.json b/package.json
index 9ebe175..0ce090e 100644
--- a/package.json
+++ b/package.json
@@ -1,8 +1,12 @@
{
"name": "rbush",
- "version": "1.4.2",
+ "version": "1.4.3",
"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": {
+ "type": "git",
+ "url": "git://github.com/mourner/rbush.git"
+ },
"keywords": [
"spatial",
"tree",
@@ -12,19 +16,16 @@
"math"
],
"author": "Vladimir Agafonkin",
- "repository": {
- "type": "git",
- "url": "git://github.com/mourner/rbush.git"
- },
+ "license": "MIT",
"main": "rbush.js",
"devDependencies": {
- "benchmark": "^1.0.0",
- "eslint": "^1.10.3",
- "eslint-config-mourner": "^1.0.1",
+ "benchmark": "^2.1.0",
+ "eslint": "^2.10.2",
+ "eslint-config-mourner": "^2.0.1",
"faucet": "0.0.1",
- "istanbul": "~0.4.1",
+ "istanbul": "~0.4.3",
"rtree": "~1.4.2",
- "tape": "^4.0.0"
+ "tape": "^4.5.1"
},
"scripts": {
"test": "eslint rbush.js test/test.js && node test/test.js | faucet",
@@ -36,7 +37,8 @@
"rules": {
"indent": 0,
"strict": 0,
- "new-cap": 0
+ "new-cap": 0,
+ "consistent-return": 0
},
"env": {
"amd": true
diff --git a/rbush.js b/rbush.js
index f6975df..5df616d 100644
--- a/rbush.js
+++ b/rbush.js
@@ -8,8 +8,6 @@
'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
@@ -300,7 +298,7 @@ rbush.prototype = {
}
}
- node = targetNode;
+ node = targetNode || node.children[0];
}
return node;
@@ -468,8 +466,6 @@ rbush.prototype = {
// 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]));
diff --git a/test/test.js b/test/test.js
index ff016ff..3e464f0 100644
--- a/test/test.js
+++ b/test/test.js
@@ -25,6 +25,10 @@ var data = [[0,0,0,0],[10,10,10,10],[20,20,20,20],[25,0,25,0],[35,10,35,10],[45,
[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 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},
@@ -151,6 +155,29 @@ t('#load does nothing if loading empty data', function (t) {
t.end();
});
+t('#load handles the insertion of maxEntries + 2 empty bboxes', function (t) {
+ var tree = rbush(4)
+ .load(emptyData);
+
+ t.equal(tree.toJSON().height, 2);
+ sortedEqual(t, tree.all(), emptyData);
+
+ t.end();
+});
+
+t('#insert handles the insertion of maxEntries + 2 empty bboxes', function (t) {
+ var tree = rbush(4);
+
+ emptyData.forEach(function (datum) {
+ tree.insert(datum);
+ });
+
+ t.equal(tree.toJSON().height, 2);
+ sortedEqual(t, tree.all(), emptyData);
+
+ t.end();
+});
+
t('#load properly splits tree root when merging trees of the same height', 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
More information about the Pkg-grass-devel
mailing list