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 (so you can transfer it between threads or store it as a compact binary file).
Supports geographic locations with the geoflatbush extension.
// initialize Flatbush for 1000 itemsconst index = 1000;// fill it with 1000 rectanglesfor const p of itemsindex;// perform the indexingindex;// make a bounding box queryconst found = index;// make a k-nearest-neighbors queryconst neighborIds = index;// instantly transfer the index from a worker to the main thread;// reconstruct the index from a raw array bufferconst index = Flatbush;
Install using NPM (
npm install flatbush) or Yarn (
yarn add flatbush), then:
// import as an ES module;// or require as a CommonJS moduleconst Flatbush = ;
Or use a browser build directly:
new Flatbush(numItems[, nodeSize, ArrayType])
Creates a Flatbush index that will hold a given number of items (
numItems). Additionally accepts:
nodeSize: size of the tree node (
16by 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 (
Float64Arrayby default); other types may be faster in certain cases (e.g.
Int32Arraywhen your data is integer).
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.
Performs indexing of the added rectangles.
Their number must match the one provided when creating a
index.search(minX, minY, maxX, maxY[, filterFn])
Returns an array of indices of items in a given bounding box. Item indices refer to the value returned by
const ids = index;
If given a
filterFn, calls it on every found item (passing an item index)
and only includes it if the function returned a truthy value.
const ids = index;
index.neighbors(x, y[, maxResults, maxDistance, filterFn])
Returns an array of item indices in order of distance from the given
(known as K nearest neighbors, or KNN). Item indices refer to the value returned by
const ids = index; // returns 5 ids
Infinity by default.
Also accepts a
filterFn similar to
Recreates a Flatbush index from raw
(that's exposed as
index.data on a previously indexed Flatbush instance).
Very useful for transferring indices between threads or storing them in a file.
data: array buffer that holds the index.
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.
npm run bench with Node v10.11.0:
|index 1,000,000 rectangles||263ms||1208ms|
|1000 searches 10%||594ms||1105ms|
|1000 searches 1%||68ms||213ms|
|1000 searches 0.01%||9ms||27ms|
|1000 searches of 100 neighbors||29ms||58ms|
|1 search of 1,000,000 neighbors||148ms||781ms|
|100,000 searches of 1 neighbor||870ms||1548ms|