mourner/rbush-knn

k-nearest neighbors search (KNN) for RBush

rbush-knn

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

var RBush = require('rbush');
var knn = require('rbush-knn');

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';
});

API

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 between neighbors and the query coordinates (Infinity by default)

Changelog

3.0.1 (Mar 19, 2020)

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

2.0.0 (Jun 30, 2016)

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

1.1.0 (Feb 29, 2015)

• Add an optional filter function argument.

1.0.2 (Jun 25, 2015)

• 2.5x performance improvement!

1.0.1 (Jun 10, 2015)

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

1.0.0 (Apr 24, 2015)

• Initial release.

rbush-knn's Issues

Error when # nearest items wanted exceeds items in rbush

I get this error when doing something like var neighbors = knn(tree, [coords.lng, coords.lat], 50)

/repo/node_modules/rbush-knn/index.js:23
        while (queue.peek()._knnItem && result.length < n) result.push(queue.p
                           ^
TypeError: Cannot read property '_knnItem' of undefined
    at knn (/repo/node_modules/rbush-knn/index.js:23:28)

release new version to npm + typing

Hi,

right now I am using it directly over github, is it possible to release the new version to npm (and possibly also add a typing file or what its called)

Right now I am importing it in TypeScript via (installed via npm install git+https://github.com/mourner/rbush-knn.git:

// @ts-expect-error doesn't have a type
import knn from 'rbush-knn';

Distance cutoff

Hi there, I wanted to ask if it sounds like a good idea to send the box distance as the second parameter to the filter function (predicate), to enable checking that the returned items are not further away than a certain distance.

I realize this can already be achieved with the available item data (minX, maxX, etc.) and furthermore a distance cutoff may not efficiently be implemented in the filter itself — since returning false after the candidates get too far away will only cause the tree to be queried further (to fill in K items) with no chance of later items to be closer.

May be that a separate argument for the cutoff would be better suited? (If, of course, it's in the scope of this library)

Queue is not a constructor

When using rbush-knn with webpack, I get Queue is not a constructor from line 14 of index.js:

var queue = new Queue(undefined, compareDist);

At this point, Queue is a module. I can fix it for my use by changing the top of the file to:

'use strict';

import Queue  from 'tinyqueue';

export default function knn(tree, x, y, n, predicate, maxDistance) {

then Queue is a class and new Queue works fine

I'm fairly new to using modules. I don't know if this is the correct fix , but if it looks useful I can send a PR for it.

Allow the use of custom method for distance sorting of nodes

The sort algorithm using the axis distance to the query point (while fast) is only correct when coordinates are flat. It should allow the use of a custom method for sorting when coordinates do not refer to a flat model for example earth coordinates using Haversine formula/Spherical laws of cosine/Equirectangular etc.

npm repository contains obsolete version

Doesn't return nearest neighbor

I'm getting some unexpected results from knn, like it ignores some of my points.

const tree = new RBush();
tree.load([
  [0, 0],
  [10, 10],
  ]);
console.log(knn(tree, 0, 0, 1)); // Prints [[10, 10]].

(Observable notebook)

Why doesn't it print [[0, 0]]? Am I doing something wrong?

Thanks!

maxDistance unclear

Hello!

I noticed that the explanation for maxDistance is lacking after getting some bad results and reading the source code. Perhaps this is some domain specific knowledge for cartographers, but it was unclear for me.

maxDistance (optional): maximum distance between neighbours and the query coordinates (Infinity by default)

It's not clear that the distance should be expressed as distance^2.

Taking the pythagoras theorem into account: a^2+b^2=c^2

The functions boxDist returns a^2+b^2, but is comparing to c^1 not c^2

From index.js

            dist = boxDist(x, y, node.leaf ? toBBox(child) : child);
            if (!maxDistance || dist <= maxDistance) {

From index.js

function boxDist(x, y, box) {
    var dx = axisDist(x, box.minX, box.maxX),
        dy = axisDist(y, box.minY, box.maxY);
    return dx * dx + dy * dy;
}

Suggestion:

1. square maxDistance (maxDistance = maxDistance * maxDistance) in index.js or,
2. change the readme

Spherical Surface

From the code below (taken from lines 39-53 of index.js), spherical coordinates may yield funky results.

function compareDist(a, b) {
    return a.dist - b.dist;
}

function boxDist(x, y, box) {
    var dx = axisDist(x, box.minX, box.maxX),
        dy = axisDist(y, box.minY, box.maxY);
    return dx * dx + dy * dy;
}

function axisDist(k, min, max) {
    return k < min ? min - k :
           k <= max ? 0 :
           k - max;
}

1. boxDist, as you probably know, does not support spherical coordinates. Utilizing the Haversine formula in some way for the case of lat/lng could give improved results.
2. axisDist has a longitude wraparound problem. For example, a call to axisDist(-179, 178, 179) will return 357, but -179 is 2 degrees away from the max, 179.

I think there is some cool potential here to add support for spherical coordinates. What do you think?

Boolean predicate for query

I think it would be very helpful if there would be an option to pass a function that returns a boolean value to the knn algorithm. If that is the case, the algorithm just considers items that satisfy that predicate.

What do people think about this idea?