rbush

NPM

Install with NPM:

npm install rbush

Then import as a module:

import RBush from 'rbush';

Browser (ESM)

Use directly in the browser via jsDelivr:

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

Browser (Global Variable)

Use the browser bundle which provides an RBush global variable:

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

Use tree.load() to bulk-insert an array of items. Bulk insertion is typically 2-3x faster than individual insertions.

Note on performance:

• If loading into an empty tree, subsequent query performance improves by ~20-30%.
• If loading into an existing tree, RBush builds a separate tree for the new data and inserts it into the larger tree. This is efficient for clustered data but can degrade query performance if the new data is scattered.

tree.load([item1, item2, ...]);

You can serialize the tree to JSON for storage or to transfer data between a server (Node.js) and a client (browser).

Important: The nodeSize option passed to the constructor must be identical in both the exporting and importing trees for the data to be valid.

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

// import previously exported data
// Note: nodeSize must match the original tree
const tree = rbush(9).fromJSON(treeData);

Spatial Search

Find all items that intersect a given bounding box. The search box must be in {minX, minY, maxX, maxY} format, regardless of your custom data format.

const result = tree.search({
    minX: 40,
    minY: 20,
    maxX: 80,
    maxY: 70
});

Collision Detection

Check if any items intersect the given bounding box. Returns true or false.

const hasCollision = tree.collides({minX: 40, minY: 20, maxX: 80, maxY: 70});

Get all items

const allItems = tree.all();

const result = tree.search({
    minX: 40,
    minY: 20,
    maxX: 80,
    maxY: 70
});

const collides = tree.collides({minX: 40, minY: 20, maxX: 80, maxY: 70});

const allItems = tree.all();

Insert an item

Items must follow the default data format (see Data Format) or a custom format.

tree.insert(item);

Remove an item

By default, remove uses object reference. To remove an item using a copy (e.g., from a server), provide a custom equals comparator:

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

Clear all items

tree.clear();

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

By default, RBush expects objects with minX, minY, maxX, and maxY properties. You can customize how data is read and compared by extending the RBush class and overriding toBBox, compareMinX, and compareMinY.

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

Initialize a new R-tree instance using new RBush().

You can optionally pass a nodeSize argument to define the maximum number of entries in a tree node. The default is 9.

• Higher value: Faster insertion, slower search.
• Lower value: Slower insertion, faster search.

const tree = new RBush();
// or with custom node size
const tree = new RBush(16);