flatbush

You can install Flatbush via NPM for Node.js environments or use it directly in the browser via CDN.

NPM

npm install flatbush

Browser (ESM)

Use jsDelivr to import as a module:

<script type="module">
    import Flatbush from 'https://cdn.jsdelivr.net/npm/flatbush/+esm';
</script>

Browser (Global Variable)

Use the standard script tag for a bundle with a Flatbush global:

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

Returns an array of indices of items intersecting or touching a given bounding box. Item indices correspond to the values returned by index.add().

Options:

• filterFn: A callback function (i, x0, y0, x1, y1) => boolean. If provided, only items for which the function returns a truthy value are included. If you provide a callback with arguments, you can handle results directly inside the search call instead of receiving an array.

Examples:

Basic search:

const ids = index.search(10, 10, 20, 20);

Search with a filter:

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

Handling results via callback:

index.search(10, 10, 20, 20, (i, x0, y0, x1, y1) => {
    console.log(`Item found: ${items[i]}, bbox: ${x0} ${y0} ${x1} ${y1}`);
});

index.search(minX, minY, maxX, maxY[, filterFn])

Returns an array of item indices ordered by distance from the given (x, y) coordinates.

Options:

• maxResults: Maximum number of neighbors to return (default: Infinity).
• maxDistance: Maximum distance to search (default: Infinity).
• filterFn: A callback function (i) => boolean to filter potential results. Unlike search, you should not use the callback to handle results; it is only for filtering.

Example:

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

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

Creates a new Flatbush instance from an existing ArrayBuffer or SharedArrayBuffer. This is the primary method for transferring an index from a Web Worker to the main thread or loading a saved index from a file.

Example:

// Reconstruct from data received in a message event
const index = Flatbush.from(e.data);

// Or transfer via postMessage
postMessage(index.data, [index.data]);

Flatbush.from(data[, byteOffset])

The following properties are available on a Flatbush instance:

• data: The underlying array buffer holding the index.
• minX, minY, maxX, maxY: The bounding box of the entire dataset.
• numItems: Total number of stored items.
• nodeSize: Number of items in a node tree.
• ArrayType: The type used for internal coordinate storage.
• IndexArrayType: The type used for internal item index storage.

You can create a new Flatbush index by calling the Flatbush constructor. You must specify the number of items the index will hold. You can optionally configure the nodeSize, the ArrayType used for coordinate storage, and the ArrayBufferType used for the underlying data storage.

Parameters:

• numItems (number): The total number of rectangles to be added. Required.
• nodeSize (number, default: 16): The size of the tree node. Must be between 2 and 65535.
• ArrayType (TypedArrayConstructor, default: Float64Array): The typed array class used for coordinates.
• ArrayBufferType (ArrayBufferConstructor | SharedArrayBufferConstructor, default: ArrayBuffer): The buffer type used to store data.

Use the add method to insert rectangles into the index. Each rectangle is defined by its bounding box coordinates. The method returns a zero-based, incremental index representing the newly added rectangle, which you can use to retrieve the item later during searches.

Parameters:

• minX (number): Minimum X coordinate.
• minY (number): Minimum Y coordinate.
• maxX (number, default: minX): Maximum X coordinate.
• maxY (number, default: minY): Maximum Y coordinate.

Returns:

• number: The zero-based index of the added rectangle.

The static from() method allows you to recreate a Flatbush index from an existing ArrayBuffer or SharedArrayBuffer. This is highly efficient for loading pre-built indexes from disk or transferring them between workers.

Parameters:

• data (ArrayBufferLike): The buffer containing the serialized Flatbush data.
• byteOffset (number, default: 0): The byte offset to the start of the Flatbush buffer. Must be 8-byte aligned.

Returns:

• Flatbush: A new index instance pointing to the provided data.

Throws:

• If byteOffset is not 8-byte aligned.
• If data is not an ArrayBuffer or SharedArrayBuffer.
• If the data does not contain the Flatbush magic number (0xfb).
• If the version in the data does not match the current library version.

The search method performs a spatial query to find all items that intersect or touch a given bounding box.

Parameters:

• minX (number): Minimum X of the query box.
• minY (number): Minimum Y of the query box.
• maxX (number): Maximum X of the query box.
• maxY (number): Maximum Y of the query box.
• filterFn (function, optional): A callback function (index, x0, y0, x1, y1) => boolean. If provided, only items where this function returns true will be included in the results. The arguments represent the item's index and its bounding box coordinates.

Returns:

• number[]: An array of indices of the items found.

After adding all rectangles using add(), you must call finish() before performing any spatial queries. The finish() method performs the actual indexing (sorting items via Hilbert values and building the R-tree structure). If you attempt to search before calling finish(), an error will be thrown.

Note: You must add exactly the number of items specified in the constructor, or finish() will throw an error.

The neighbors method searches for items in order of their distance from a specific point $(x, y)$. This is useful for k-nearest-neighbor (k-NN) queries.

Parameters:

• x (number): The X coordinate of the point.
• y (number): The Y coordinate of the point.
• maxResults (number, default: Infinity): The maximum number of neighbors to return.
• maxDistance (number, default: Infinity): The maximum distance to search within.
• filterFn (function, optional): A callback function (index) => boolean used to filter results.

Returns:

• number[]: An array of indices of the items found, sorted by distance.