npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

flatbush

v4.4.0

Published

Fast static spatial index for rectangles

Downloads

141,326

Readme

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 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.

Build Status minzipped size Simply Awesome

Usage

// initialize Flatbush for 1000 items
const index = new 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
const found = index.search(minX, minY, maxX, maxY).map((i) => items[i]);

// make a k-nearest-neighbors query
const neighborIds = index.neighbors(x, y, 5);

// instantly transfer the index from a worker to the main thread
postMessage(index.data, [index.data]);

// reconstruct the index from a raw array buffer
const index = Flatbush.from(e.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:

<script src="https://cdn.jsdelivr.net/npm/flatbush"></script>

API

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 an item index) and only includes it if the function returned a truthy value.

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

index.neighbors(x, y[, maxResults, maxDistance, filterFn])

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().

const ids = index.neighbors(10, 10, 5); // returns 5 ids

maxResults and maxDistance are Infinity by default. Also accepts a filterFn similar to index.search.

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 with Node v14:

bench | flatbush | rbush --- | --- | --- index 1,000,000 rectangles | 273ms | 1143ms 1000 searches 10% | 575ms | 781ms 1000 searches 1% | 63ms | 155ms 1000 searches 0.01% | 6ms | 17ms 1000 searches of 100 neighbors | 24ms | 43ms 1 search of 1,000,000 neighbors | 133ms | 280ms 100,000 searches of 1 neighbor | 710ms | 1170ms

Ports