sweco-se / rbush-knn-sphere Goto Github PK

k-nearest neighbors search for RBush. Implements a simple depth-first kNN search algorithm using a priority queue, with spatial coordinates.

var RBush = require('rbush');
var knn = require('@sweco-se/rbush-knn-sphere');

var tree = new RBush(); // create RBush tree
tree.load(data); // bulk insert
var neighbors = knn(tree, 40, 40, 10); // return 10 nearest items around point [40, 40]

You can optionally pass a filter function to find k neighbors that satisfy a certain condition:

var neighbors = knn(tree, 40, 40, 10, function (item) {
    return item.foo === 'bar';
});

Or specify a maximum radius in metres to limit the search to:

var neighbors = knn(tree, 40, 40, 10, null, 1000);

knn(tree, x, y, [k, filterFn, maxDistance])

• tree: an RBush tree
• x, y: query coordinates
• k: number of neighbors to search for (Infinity by default)
• filterFn: optional filter function; k nearest items where filterFn(item) === true will be returned.
• maxDistance (optional): maximum distance in metres between neighbors and the query coordinates (Infinity by default)

@sweco-se/rbush-knn-sphere (forked repo):

• Breaking: forked from original repo by @sefjod and renamed to @sweco-se/rbush-knn-sphere
• Changed max distance calculation to support spatial coordinates

mourner/rbush-knn (original repo):

• Breaking: fixed maxDistance argument — now it's taken into account correctly (rather than being used as a max squared distance). h/t @AleksandarFaraj
• Updated dependencies & compatibility with RBush v3.

• Breaking: updated to be compatible with RBush 2.0.
• Breaking: signature changed from tree, [x, y], k, filterFn to tree, x, y, k, filterFn
• Improved performance by ~20%.

• Add an optional filter function argument.

• 2.5x performance improvement!

• Fixed an error when requesting more items than the tree has. #1

• Initial release.