High-performance 2D spatial index for rectangles (based on R*-tree with bulk loading and bulk insertion algorithms)
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.
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.
The following sample performance test was done by generating
random uniformly distributed rectangles of ~0.01% area and setting
Performed with Node.js v0.10.22 on a Retina Macbook Pro 15 (mid-2012).
|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|
var tree = rbush9;
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.
Insert an item:
var item = 20 40 30 50; // [x1, y1, x2, y2]treeinsertitem;
Remove a previously inserted item:
Clear all items:
Items inserted in the tree can have other arbitrary properties/elements that you can access later:
var item1 = 20 40 30 50 foo: 'bar';treeinsertitem1;var item2 = 15 15 30 30;item2foo = 'bar';treeinsertitem2;
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
maxY accessor strings
as a second argument to
rbush like this:
var tree = rbush9 '.minLng' '.minLat' '.maxLng' '.maxLat';treeinsertid: 'foo' minLng: 30 minLat: 50 maxLng: 40 maxLat: 60;
Bulk-insert the given data into the tree:
treeload10 10 15 2012 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.
var result = treesearch40 20 80 70;
Returns an array of data items (points or rectangles) that the given bounding box (
[minX, minY, maxX, maxY]) intersects.
var allItems = treeall;
Returns all items of the tree.
var result = treecollides40 20 80 70;
true if there are any items in the given bounding box, otherwise
// export data as JSON objectvar treeData = treetoJSON;// import previously exported datavar tree = rbush9fromJSONtreeData;
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.
For "k nearest neighbors around a point" type of queries for RBush, check out rbush-knn.
npm install # install dependenciesnpm test # check the code with JSHint and run testsnpm run perf # run performance benchmarksnpm run cov # report test coverage (with more detailed report in coverage/lcov-report/index.html)
RBush should run on Node and all major browsers. The only caveat: IE 8 needs an Array#indexOf polyfill for
remove method to work.
collidesmethod for fast collision detection.
allmethod for getting all of the tree items. #11
compareMinYmethods public, made it possible to avoid Content Security Policy issues by overriding them for custom format. #14 #12
First fully functional RBush release.