mourner / rbush-knn Goto Github PK

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.

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?

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?

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)

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.

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

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

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!

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)