Skip to content
A very fast static spatial index for 2D points and rectangles in JavaScript
JavaScript
Branch: master
Clone or download
Pull request Compare This branch is 60 commits behind mourner:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
.travis.yml
LICENSE
README.md
bench.js
index.js
package.json
test.js

README.md

flatbush

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 typed array (which can be transfered).

Build Status Simply Awesome

Example

// initialize flatbush for 1000 items
const index = flatbush(1000);

// fill it with 1000 rectangles
for (const p of items) {
    index.add(p.minX, p.minY, p.maxX, p.maxY);
}

// perform the indexing
index.finish();

// make a bounding box query
var found = index.search(minX, minY, maxX, maxY).map((i) => items[i]);

Install

Install using NPM (npm install flatbush) or Yarn (yarn add flatbush), then either:

// require in Node / Browserify
var flatbush = require('flatbush');

// or import as a ES module
import flatbush from 'flatbush';

Or use a browser build directly:

<script src="https://unpkg.com/flatbush@1.3.0/flatbush.min.js"></script>

API

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 (16 by default); experiment with different values for best performance.
  • ArrayType: the array type used for tree storage (Float64Array by default); other types may be faster in certain cases (e.g. Int32Array when your data is integer)

index.add(minX, minY, maxX, maxY)

Adds a given rectangle to the index.

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 in a given bounding box.

var ids = 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.

var ids = index.search(10, 10, 20, 20, (i) => items[i].foo === 'bar');

Performance

Running npm run bench:

1000000 rectangles

flatbush: 299.147ms
1000 searches 10%: 784.722ms
1000 searches 1%: 113.550ms
1000 searches 0.01%: 15.212ms

rbush: 1169.129ms
1000 searches 10%: 957.165ms
1000 searches 1%: 188.941ms
1000 searches 0.01%: 18.105ms
You can’t perform that action at this time.