mourner · Nov 29, 2017 · Dec 1, 2017 · Dec 1, 2017 · Dec 1, 2017 · Dec 4, 2017
diff --git a/.gitignore b/.gitignore
@@ -1,5 +1,8 @@
 node_modules
 npm-debug.log
 coverage
-rbush.js
-rbush.min.js
+rbush3d.js
+rbush3d.min.js
+package-lock.json
+dist
+.nyc_output
diff --git a/.npmignore b/.npmignore
@@ -1,4 +1,13 @@
+src
 bench
 viz
 test
 .travis.yml
+.vscode
+.gitignore
+tsconfig.json
+tsconfig.build.json
+tslint.json
+dist
+.nyc_output
+coverage
diff --git a/.travis.yml b/.travis.yml
@@ -2,3 +2,12 @@ language: node_js
 node_js:
   - "4"
   - "stable"
+branches:
+  only:
+  - master
+install:
+- npm install
+script:
+- npm test
+after_success:
+- npm run coveralls
diff --git a/.vscode/settings.json b/.vscode/settings.json
@@ -0,0 +1,15 @@
+{
+    "search.exclude": {
+        "node_modules": true,
+        "coverage": true
+    },
+    "files.exclude": {
+        "**/.git": true,
+        "**/.DS_Store": true,
+        "node_modules": true,
+        "package-lock.json": true,
+        "coverage": true,
+        ".nyc_output": true
+    },
+    "editor.tabSize": 2,
+}
diff --git a/MIT-LICENSE b/MIT-LICENSE
@@ -1,4 +1,4 @@
-Copyright (c) 2016 Vladimir Agafonkin
+Copyright (c) 2017 Eronana
 
 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
@@ -1,59 +1,54 @@
-RBush
+RBush-3D
 =====
 
-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.
+RBush-3D is 3D version of [RBush](https://github.com/mourner/rbush).
 
-*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.
+[![Build Status](https://travis-ci.org/Eronana/rbush-3d.svg?branch=master)](https://travis-ci.org/Eronana/rbush-3d)
+[![Coverage Status](https://coveralls.io/repos/github/Eronana/rbush-3d/badge.svg?branch=master)](https://coveralls.io/github/Eronana/rbush-3d?branch=master)
 
-[![Build Status](https://travis-ci.org/mourner/rbush.svg?branch=master)](https://travis-ci.org/mourner/rbush)
-[![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
+## TODO
+- [x] real 3D test
+- [ ] Demos
+- [x] Benchmarks
 
-## 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.
-
-* [randomly clustered data](http://mourner.github.io/rbush/viz/viz-cluster.html)
-* [uniformly distributed random data](http://mourner.github.io/rbush/viz/viz-uniform.html)
 
 ## Install
 
-Install with NPM (`npm install rbush`), or use CDN links for browsers:
-[rbush.js](https://unpkg.com/rbush@2.0.1/rbush.js),
-[rbush.min.js](https://unpkg.com/rbush@2.0.1/rbush.min.js)
+Install with NPM (`npm install rbush-3d`), and Chinese user could use CNPM(`cnpm install rbush-3d`).
+
+Or use CDN links for browsers:
+[rbush3d.js](https://unpkg.com/rbush-3d@0.0.4/dist/rbush3d.js),
+[rbush3d.min.js](https://unpkg.com/rbush-3d@0.0.4/dist/rbush3d.min.js)
 
 ## Usage
 
 ### Creating a Tree
 
-```js
-var tree = rbush();
+```typescript
+import { RBush3D } from 'rbush-3d';
+const tree = new RBush3D();
 ```
 
-An optional argument to `rbush` defines the maximum number of entries in a tree node.
-`9` (used by default) is a reasonable choice for most applications.
+An optional argument to `RBush3D` defines the maximum number of entries in a tree node.
+`16` (used by default) is a reasonable choice for most applications.
 Higher value means faster insertion and slower search, and vice versa.
 
-```js
-var tree = rbush(16);
+```typescript
+const tree = new RBush3D(16);
 ```
 
 ### Adding Data
 
 Insert an item:
 
-```js
-var item = {
+```typescript
+const item = {
     minX: 20,
     minY: 40,
+    minZ: 60,
     maxX: 30,
     maxY: 50,
+    maxZ: 70,
     foo: 'bar'
 };
 tree.insert(item);
@@ -63,45 +58,43 @@ tree.insert(item);
 
 Remove a previously inserted item:
 
-```js
+```typescript
 tree.remove(item);
 ```
 
-By default, RBush removes objects by reference.
+By default, RBush-3D 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
+```typescript
 tree.remove(itemCopy, function (a, b) {
     return a.id === b.id;
 });
 ```
 
 Remove all items:
 
-```js
+```typescript
 tree.clear();
 ```
 
 ### Data Format
 
-By default, RBush assumes the format of data points to be an object
-with `minX`, `minY`, `maxX` and `maxY` properties.
+By default, RBush-3D assumes the format of data points to be an object
+with `minX`, `minY`, `minZ`, `maxX`, `maxY` and `maxZ` properties.
 You can customize this by providing an array with corresponding accessor strings
-as a second argument to `rbush` like this:
+as a second argument to `rbush3d` like this:
 
-```js
-var tree = rbush(9, ['[0]', '[1]', '[0]', '[1]']); // accept [x, y] points
-tree.insert([20, 50]);
+```typescript
+const tree = rbush3d(16, ['[0]', '[1]', '[2]', '[0]', '[1]', '[2]']); // accept [x, y, z] points
+tree.insert([20, 50, 80]);
 ```
 
-If you're indexing a static list of points (you don't need to add/remove points after indexing), you should use [kdbush](https://github.com/mourner/kdbush) which performs point indexing 5-8x faster than RBush.
-
 ### Bulk-Inserting Data
 
 Bulk-insert the given data into the tree:
 
-```js
+```typescript
 tree.load([item1, item2, ...]);
 ```
 
@@ -118,70 +111,68 @@ but makes query performance worse if the data is scattered.
 
 ### Search
 
-```js
-var result = tree.search({
+```typescript
+const result = tree.search({
     minX: 40,
     minY: 20,
+    minZ: 50,
     maxX: 80,
-    maxY: 70
+    maxY: 70,
+    maxZ: 90
 });
 ```
 
 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
+Note that the `search` method accepts a bounding box in `{minX, minY, minZ, maxX, maxY, maxZ}` format
 regardless of the format specified in the constructor (which only affects inserted objects).
 
-```js
-var allItems = tree.all();
+```typescript
+const allItems = tree.all();
 ```
 
 Returns all items of the tree.
 
 ### Collisions
 
-```js
-var result = tree.collides({minX: 40, minY: 20, maxX: 80, maxY: 70});
+```typescript
+const result = tree.collides({minX: 40, minY: 20, minZ: 50, maxX: 80, maxY: 70, maxZ: 90});
 ```
 
 Returns `true` if there are any items intersecting the given bounding box, otherwise `false`.
 
 
 ### Export and Import
 
-```js
+```typescript
 // export data as JSON object
-var treeData = tree.toJSON();
+const treeData = tree.toJSON();
 
 // import previously exported data
-var tree = rbush(9).fromJSON(treeData);
+const tree = rbush3d(16).fromJSON(treeData);
 ```
 
-Importing and exporting as JSON allows you to use RBush on both the server (using Node.js) and the browser combined,
+Importing and exporting as JSON allows you to use RBush-3D 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,
-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 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   | 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
+(see `debug/perf.ts` script).
+Performed with Node.js v8.9.1 on a MacBook Pro (15-inch, 2017).
+
+Test                         | RBush-3D | [RBush](https://github.com/mourner/rbush) (2D version)
+---------------------------- | -------- | ------
+insert 1M items one by one   | 4.30s    | 2.94s
+1000 searches of 0.01% area  | 0.02s    | 0.03s
+1000 searches of 1% area     | 0.09s    | 0.31s
+1000 searches of 10% area    | 0.73s    | 1.80s
+remove 1000 items one by one | 0.02s    | 0.02s
+bulk-insert 1M items         | 1.40s    | 1.17s
+
 
 ## Algorithms Used
 
@@ -202,90 +193,10 @@ bulk-insert 1M items         | 1.25s  | n/a    | 6.7x
 ## Development
 
 ```bash
-npm install  # install dependencies
+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)
+npm test      # check the code with JSHint and run tests
+npm run perf  # run performance benchmarks
+npm run cover # report test coverage (with more detailed report in coverage/lcov-report/index.html)
+npm run viz   # show 3d visualization in browser
 ```
-
-## Compatibility
-
-RBush should run on Node and all major browsers. The only caveat: IE 8 needs an [Array#indexOf polyfill](https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf#Polyfill) for `remove` method to work.
-
-## Changelog
-
-#### 2.0.1 &mdash; June 29, 2016
-
-- Fixed browser builds in NPM.
-
-#### 2.0.0 &mdash; 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 &mdash; May 17, 2016
-
-- Fixed an error when inserting many empty bounding boxes.
-
-#### 1.4.2 &mdash; Dec 16, 2015
-
-- 50% faster insertion.
-
-#### 1.4.1 &mdash; Sep 16, 2015
-
-- Fixed insertion in IE8.
-
-#### 1.4.0 &mdash; Apr 22, 2015
-
-- Added `collides` method for fast collision detection.
-
-#### 1.3.4 &mdash; 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 &mdash; Aug 30, 2014
-
-- Improved bulk insertion performance by ~60-70%.
-- Improved insertion performance by ~40%.
-- Improved search performance by ~30%.
-
-#### 1.3.2 &mdash; Nov 25, 2013
-
-- Improved removal performance by ~50%. [#18](https://github.com/mourner/rbush/pull/18)
-
-#### 1.3.1 &mdash; 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 &mdash; 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 &mdash; 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 &mdash; Oct 25, 2013
-
-- Added Web Workers support. [#9](https://github.com/mourner/rbush/pull/9)
-
-#### 1.2.3 &mdash; Aug 30, 2013
-
-- Added AMD support. [#8](https://github.com/mourner/rbush/pull/8)
-
-#### 1.2.2 &mdash; Aug 27, 2013
-
-- Eliminated recursion when recalculating node bboxes (on insert, remove, load).
-
-#### 1.2.0 &mdash; Jul 19, 2013
-
-First fully functional RBush release.