rbush

What is rbush?

The rbush npm package is a high-performance JavaScript library for 2D spatial indexing of points and rectangles. It's based on an R-tree, a data structure for spatial indexing, which allows for efficient querying of spatial data like rectangles and points. It is commonly used for tasks such as collision detection, geospatial queries, and storing spatial data efficiently.

What are rbush's main functionalities?

Inserting items

This feature allows you to insert items into the RBush tree. Each item is an object with minX, minY, maxX, and maxY properties, which define the bounding box of the item.

const RBush = require('rbush');
const tree = new RBush();
tree.insert({minX: 20, minY: 40, maxX: 30, maxY: 50, data: {id: 'item1'}});

Bulk-inserting items

This feature allows you to bulk-insert an array of items into the RBush tree, which can be more efficient than inserting them one by one.

const RBush = require('rbush');
const tree = new RBush();
tree.load([
  {minX: 20, minY: 40, maxX: 30, maxY: 50},
  {minX: 15, minY: 10, maxX: 25, maxY: 30}
]);

Searching for items

This feature allows you to search for items in the RBush tree that intersect with the given bounding box.

const RBush = require('rbush');
const tree = new RBush();
// ... after inserting items into the tree
const results = tree.search({minX: 40, minY: 20, maxX: 80, maxY: 70});

Removing items

This feature allows you to remove a previously inserted item from the RBush tree.

const RBush = require('rbush');
const tree = new RBush();
const item = {minX: 20, minY: 40, maxX: 30, maxY: 50};
tree.insert(item);
tree.remove(item);

Clearing the tree

This feature allows you to remove all items from the RBush tree, effectively clearing it.

const RBush = require('rbush');
const tree = new RBush();
tree.clear();

Other packages similar to rbush

flatbush

Flatbush is a very fast static spatial index for 2D points and rectangles in JavaScript. It's similar to rbush but is optimized for static data and bulk insertion, and it's significantly faster for this use case.

geokdbush

Geokdbush is a geographic extension for the kdbush, the fastest static spatial index for points in JavaScript. It enables geographic queries such as finding all points within a certain distance from a given location, which is a different approach compared to rbush's rectangle-based indexing.

s2-geometry

S2 Geometry is a library for spherical geometry that allows you to index and query geographic data on the sphere. It's different from rbush which works with planar geometry, making s2-geometry suitable for large-scale geographic applications.

README

RBush

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.

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
• uniformly distributed random data

Usage

Installing RBush

Install with NPM: npm install rbush, then import as a module:

import RBush from 'rbush';

Or use as a module directly in the browser with jsDelivr:

<script type="module">
    import RBush from 'https://cdn.jsdelivr.net/npm/rbush/+esm';
</script>

Alternatively, there's a browser bundle with an RBush global variable:

<script src="https://cdn.jsdelivr.net/npm/rbush"></script>

Creating a Tree

const tree = new RBush();

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. Higher value means faster insertion and slower search, and vice versa.

const tree = new RBush(16);

Adding Data

Insert an item:

const item = {
    minX: 20,
    minY: 40,
    maxX: 30,
    maxY: 50,
    foo: 'bar'
};
tree.insert(item);

Removing Data

Remove a previously inserted item:

tree.remove(item);

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):

tree.remove(itemCopy, (a, b) => {
    return a.id === b.id;
});

Remove all items:

tree.clear();

Data Format

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 overriding toBBox, compareMinX and compareMinY methods like this:

class MyRBush extends RBush {
    toBBox([x, y]) { return {minX: x, minY: y, maxX: x, maxY: y}; }
    compareMinX(a, b) { return a.x - b.x; }
    compareMinY(a, b) { return a.y - b.y; }
}
const tree = new MyRBush();
tree.insert([20, 50]); // accepts [x, y] points

If you're indexing a static list of points (you don't need to add/remove points after indexing), you should use kdbush which performs point indexing 5-8x faster than RBush.

Bulk-Inserting Data

Bulk-insert the given data into the tree:

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.

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 in one update are close to each other), but makes query performance worse if the data is scattered.

Search

const 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 intersects.

Note that the search method accepts a bounding box in {minX, minY, maxX, maxY} format regardless of the data format.

const allItems = tree.all();

Returns all items of the tree.

Collisions

const 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.

Export and Import

// export data as JSON object
const treeData = tree.toJSON();

// import previously exported data
const 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, check out 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	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

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
• The R*-tree: An Efficient and Robust Access Method for Points and Rectangles+
• OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree
• Bulk Insertions into R-Trees Using the Small-Tree-Large-Tree Approach
• R-Trees: Theory and Applications (book)

Development

npm ci       # install dependencies
npm test     # lint the code and run tests
npm run perf # run performance benchmarks
npm run cov  # report test coverage

Compatibility

RBush v4+ is published as a ES module and no longer supports CommonJS environments. It works universally in modern browsers, but you can transpile the code on your end to support IE11.