A really fast static spatial index for 2D points and rectangles in JavaScript.
An efficient implementation of the packed Hilbert R-tree algorithm. Enables fast spatial queries on a very large number of objects (e.g. millions), which is very useful in maps, data visualizations and computational geometry algorithms. Similar to RBush, with the following key differences:
Static: you can't add/remove items after initial indexing.
Faster indexing and search, with much lower memory footprint.
Index is stored as a single array buffer (to transfer between threads or save as a compact binary file).
Supports geographic locations with the geoflatbush extension. See also: KDBush, a similar library for points.
Usage
// initialize Flatbush for 1000 itemsconst index = new Flatbush(1000);// fill it with 1000 rectanglesfor (const p of items) { index.add(p.minX, p.minY, p.maxX, p.maxY);}// perform the indexingindex.finish();// make a bounding box queryconst found = index.search(minX, minY, maxX, maxY).map((i) => items[i]);// make a k-nearest-neighbors queryconst neighborIds = index.neighbors(x, y, 5);// instantly transfer the index from a worker to the main threadpostMessage(index.data, [index.data]);
Install
Install with NPM: npm install flatbush, then import as a module:
import Flatbush from 'flatbush';
Or use as a module directly in the browser with jsDelivr:
<script type="module"> import Flatbush from 'https://cdn.jsdelivr.net/npm/flatbush/+esm';</script>
Alternatively, there's a browser bundle with a Flatbush global variable:
new Flatbush(numItems[, nodeSize, ArrayType, ArrayBufferType])
Creates a Flatbush index that will hold a given number of items (numItems). Additionally accepts:
nodeSize: size of the tree node (16 by default); experiment with different values for best performance (increasing this value makes indexing faster and queries slower, and vise versa).
ArrayType: the array type used for coordinates storage (Float64Array by default);
other types may be faster in certain cases (e.g. Int32Array when your data is integer).
ArrayBufferType: the array buffer type used to store data (ArrayBuffer by default);
you may prefer SharedArrayBuffer if you want to share the index between threads (multiple Worker, SharedWorker or ServiceWorker).
index.add(minX, minY[, maxX, maxY])
Adds a given rectangle to the index. Returns a zero-based, incremental number that represents the newly added rectangle.
If not provided, maxX and maxY default to minX and minY (essentially adding a point).
index.finish()
Performs indexing of the added rectangles.
Their number must match the one provided when creating a Flatbush object.
index.search(minX, minY, maxX, maxY[, filterFn])
Returns an array of indices of items intersecting or touching a given bounding box. Item indices refer to the value returned by index.add().
const ids = index.search(10, 10, 20, 20);
If given a filterFn, calls it on every found item (passing the item's index & bounding box coordinates)
and only includes it if the function returned a truthy value.
Returns true if any item intersects or touches a given bounding box (and passes filterFn if given),
stopping at the first match. Much faster than search(...).length > 0 when there are many potential hits.
Returns an array of item indices in order of distance from the given x, y
(known as K nearest neighbors, or KNN). Item indices refer to the value returned by index.add().
maxResults and maxDistance are Infinity by default.
If given a filterFn, calls it on items that potentially belong to the results (passing the item's index)
and only includes an item if the function returned a truthy value.
Unlike search, it shouldn't be used for handling results.
Flatbush.from(data[, byteOffset])
Recreates a Flatbush index from raw ArrayBuffer or SharedArrayBuffer data
(that's exposed as index.data on a previously indexed Flatbush instance).
Very useful for transferring or sharing indices between threads or storing them in a file.
Properties
data: array buffer that holds the index.
minX, minY, maxX, maxY: bounding box of the data.
numItems: number of stored items.
nodeSize: number of items in a node tree.
ArrayType: array type used for internal coordinates storage.
IndexArrayType: array type used for internal item indices storage.
Performance
Running node bench.js on a MacBook Pro (M1 Pro, Node v24):