• Stars
    star
    2,411
  • Rank 19,080 (Top 0.4 %)
  • Language
    JavaScript
  • License
    MIT License
  • Created over 11 years ago
  • Updated 6 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

RBush โ€” a high-performance JavaScript R-tree-based 2D spatial index for points and rectangles

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.

Build Status

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.

Install

Install with NPM (npm install rbush), or use CDN links for browsers: rbush.js, rbush.min.js

Usage

Importing RBush

// as a ES module
import RBush from 'rbush';

// as a CommonJS module
const RBush = require('rbush');

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

Development

npm install  # install dependencies

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

Compatibility

RBush should run on Node and all major browsers that support ES5.

More Repositories

1

suncalc

A tiny JavaScript library for calculating sun/moon positions and phases.
JavaScript
3,056
star
2

simplify-js

High-performance JavaScript polyline simplification library
JavaScript
2,274
star
3

bullshit.js

A bookmarklet for translating marketing speak into human-readable text. ๐Ÿ’ฉ
JavaScript
1,846
star
4

flatbush

A very fast static spatial index for 2D points and rectangles in JavaScript ๐ŸŒฑ
JavaScript
1,404
star
5

simpleheat

A tiny JavaScript library for drawing heatmaps with Canvas
JavaScript
927
star
6

dead-simple-grid

Dead Simple Grid is a responsive CSS grid micro framework that is just that. Dead simple.
HTML
747
star
7

kdbush

A fast static index for 2D points
JavaScript
618
star
8

tinyqueue

The smallest and simplest priority queue in JavaScript.
JavaScript
428
star
9

projects

A list of awesome open source projects Volodymyr Agafonkin is involved in.
410
star
10

geokdbush

The fastest spatial index for geographic locations in JavaScript
JavaScript
334
star
11

robust-predicates

Fast robust predicates for computational geometry in JavaScript
JavaScript
296
star
12

road-orientation-map

A visualization of road orientations on an interactive map
JavaScript
295
star
13

rbush-knn

k-nearest neighbors search (KNN) for RBush
JavaScript
207
star
14

delaunator-rs

Fast 2D Delaunay triangulation in Rust. A port of Delaunator.
Rust
201
star
15

tinyjam

A radically simple, zero-configuration static site generator in JavaScript
JavaScript
153
star
16

flatqueue

A very fast and simple JavaScript priority queue
JavaScript
133
star
17

quickselect

A fast selection algorithm in JavaScript.
JavaScript
82
star
18

seidel

[DEPRECATED] A JS polygon triangulation library
JavaScript
82
star
19

icomesh

Fast JavaScript icosphere mesh generation library for WebGL visualizations
JavaScript
53
star
20

bbtree

Self-balancing Binary Search Trees in JavaScript
JavaScript
49
star
21

yeahjs

A tiny, modern, fast EJS templating library
JavaScript
45
star
22

geoflatbush

Geographic kNN extension for Flatbush
JavaScript
43
star
23

kdbush.hpp

A fast static spatial index for 2D points in C++11
C++
33
star
24

worker-data-load

A test that shows the benefit of loading large amounts of data directly in a worker instead of a page.
JavaScript
33
star
25

Leaflet.TouchHover

A plugin for adding hover-like interaction to Leaflet maps on mobile devices
JavaScript
27
star
26

eslint-config-mourner

A strict ESLint config for my JavaScript projects
JavaScript
19
star
27

suncalc-go

SunCalc written in Go
Go
18
star
28

yeahml

A tiny subset of YAML for JavaScript
JavaScript
8
star
29

serenity-tm

Serenity is a light, minimal syntax highlighting theme for Sublime Text and Textmate.
8
star
30

pbf-split

Splits a Node stream of protocol buffer messages
JavaScript
7
star
31

hello-lib

Simple boilerplate for my small JS libraries.
JavaScript
7
star
32

color-metrics

JavaScript
6
star
33

agafonkin.com

My little personal page
HTML
5
star
34

fanny

A simple and fast multilayer feedforward neural network implementation in JS, made for learning purposes.
JavaScript
5
star
35

hain

Hain triangulation algorithm in JS (work in progress)
C++
4
star
36

mourner

2
star
37

mourner.github.com

Nothing here yet.
1
star