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 (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 itemsconstindex=newFlatbush(1000);// fill it with 1000 rectanglesfor(constpofitems){index.add(p.minX,p.minY,p.maxX,p.maxY);}// perform the indexingindex.finish();// make a bounding box queryconstfound=index.search(minX,minY,maxX,maxY).map((i)=>items[i]);// make a k-nearest-neighbors queryconstneighborIds=index.neighbors(x,y,5);// instantly transfer the index from a worker to the main threadpostMessage(index.data,[index.data]);// reconstruct the index from a raw array bufferconstindex=Flatbush.from(e.data);Install using NPM (npm install flatbush) or Yarn (yarn add flatbush), then:
// import as an ES moduleimportFlatbushfrom'flatbush';// or require as a CommonJS moduleconstFlatbush=require('flatbush');Or use a browser build directly:
<scriptsrc="https://unpkg.com/flatbush@3.2.1/flatbush.min.js"></script>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).
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 Flatbush object.
Returns an array of indices of items in a given bounding box. Item indices refer to the value returned by index.add().
constids=index.search(10,10,20,20);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.
constids=index.search(10,10,20,20,(i)=>items[i].foo==='bar');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().
constids=index.neighbors(10,10,5);// returns 5 idsmaxResults and maxDistance are Infinity by default.
Also accepts a filterFn similar to index.search.
Recreates a Flatbush index from raw ArrayBuffer data
(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.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.
Running npm run bench with Node v10.11.0:
| bench | flatbush | rbush |
|---|---|---|
| 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 |