DOCSEARCHbyAlgolia
Submit Docs

rbush-knn

repository·main·Indexed 42 days ago

https://github.com/mourner/rbush-knn

k-nearest neighbors (kNN) search capabilities for the RBush spatial index. Version 4.0.0 provides a depth-first search algorithm using a priority queue to find the closest items to a specific coordinate, supporting optional filter functions and maximum search distances via the knn() API.

Tokens
775
Snippets
4
Records
4
Agent score
3%

What's inside rbush-knn

  1. Perform k-nearest neighbors search with rbush-knn

    main

    Use rbush-knn to perform k-nearest neighbors (kNN) searches on an existing RBush spatial index. The library implements a depth-first search algorithm using a priority queue to find the closest items to a specific coordinate.

    import RBush from 'rbush';
import knn from 'rbush-knn';

const tree = new RBush(); // create RBush tree
tree.load(data); // bulk insert

// return 10 nearest items around point [40, 40]
const neighbors = knn(tree, 40, 40, 10);

  2. Filter k-nearest neighbors by condition

    main

    You can provide an optional filter function to the knn function. The search will continue until it finds k items that satisfy the condition filterFn(item) === true.

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

  3. Reference the knn() API

    main

    The knn function performs the nearest neighbor search.

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

    // Parameters:
// 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)

  4. Perform k-Nearest Neighbor search with knn()

    main

    The knn function performs a k-nearest neighbor search on an RBush tree. It finds the closest items to a given point (x, y) within an RBush tree structure.

    Parameters:

    • tree: The RBush tree instance. The function expects the tree to have a .data property and a .toBBox method.
    • x: The x-coordinate of the search point.
    • y: The y-coordinate of the search point.
    • n: The maximum number of neighbors to return.
    • predicate: (Optional) A function used to filter results. If provided, only items for which predicate(candidate) returns true will be included in the result.
    • maxDistance: (Optional) The maximum search radius. Only items within this distance from the point (x, y) will be considered. The function uses squared distance for internal calculations.

    Returns: An array of the nearest items found.

    import knn from 'rbush-knn';

// Assuming 'tree' is an existing RBush instance
const neighbors = knn(tree, 10, 20, 5, (item) => item.active, 100);