kdgrass

KDBush with flat API, which turns out to be even faster.

const kdgrass = require('kdgrass')

let grass = kdgrass(points);
let ids1 = grass.range(10, 10, 20, 20);  // bbox search - minX, minY, maxX, maxY
let ids2 = grass.within(10, 10, 5);      // radius search - x, y, radius

API

let grass = kdgrass(points, nodeSize?)

Creates an index from the given points.

• points: Input array of points in [x, y, x, y, ...] form.
• nodeSize: Size of the KD-tree node, 64 by default. Higher means faster indexing but slower search, and vise versa.

let index = kdgrass(points, 64);

grass.range(minX, minY, maxX, maxY)

Finds all items within the given bounding box and returns an array of indices that refer to the items in the original points input array.

let results = index.range(10, 10, 20, 20).map((id) => points[id]);

grass.within(x, y, radius)

Finds all items within a given radius from the query point and returns an array of indices.

let results = index.within(10, 10, 5).map((id) => points[id]);

See also

• kdbush − initial implementation with verbose API.
• rbush — r-tree implementation with insertion/removal API.