Struct petal_neighbors::BallTree

pub struct BallTree<'a, A> where
    A: Float,  { /* fields omitted */ }

A data structure for nearest neighbor search in a multi-dimensional space, which is partitioned into a nested set of hyperspheres, or "balls".

Implementations

impl<'a, A> BallTree<'a, A> where
    A: Float + Zero + AddAssign + DivAssign + FromPrimitive, 

pub fn new<T>(
    points: T,
    distance: Distance<A>,
    reduced_distance: Option<Distance<A>>
) -> Result<Self, ArrayError> where
    T: Into<CowArray<'a, A, Ix2>>, 

Builds a ball tree using the given distance metric.

Errors

• ArrayError::Empty if points is an empty array.
• ArrayError::NotContiguous if any row in points is not contiguous in memory.

pub fn euclidean<T>(points: T) -> Result<Self, ArrayError> where
    T: Into<CowArray<'a, A, Ix2>>, 

Builds a ball tree with a euclidean distance metric.

Errors

• ArrayError::Empty if points is an empty array.
• ArrayError::NotContiguous if any row in points is not contiguous in memory.

pub fn query_nearest<S>(&self, point: &ArrayBase<S, Ix1>) -> (usize, A) where
    S: Data<Elem = A>, 

Finds the nearest neighbor and its distance in the tree.

Examples

use ndarray::{array, aview1};
use petal_neighbors::{BallTree, distance};

let points = array![[1., 1.], [1., 2.], [9., 9.]];
let tree = BallTree::euclidean(points).expect("valid array");
let (index, distance) = tree.query_nearest(&aview1(&[8., 8.]));
assert_eq!(index, 2);  // points[2] is the nearest.
assert!((2_f64.sqrt() - distance).abs() < 1e-8);

pub fn query<S>(
    &self,
    point: &ArrayBase<S, Ix1>,
    k: usize
) -> (Vec<usize>, Vec<A>) where
    S: Data<Elem = A>, 

Finds the nearest k neighbors and their distances in the tree. The return values are sorted in the ascending order in distance.

Examples

use ndarray::{array, aview1};
use petal_neighbors::{BallTree, distance};

let points = array![[1., 1.], [1., 2.], [9., 9.]];
let tree = BallTree::euclidean(points).expect("non-empty input");
let (indices, distances) = tree.query(&aview1(&[3., 3.]), 2);
assert_eq!(indices, &[1, 0]);  // points[1] is the nearest, followed by points[0].

pub fn query_radius<S>(
    &self,
    point: &ArrayBase<S, Ix1>,
    distance: A
) -> Vec<usize> where
    S: Data<Elem = A>, 

Finds all neighbors whose distances from point are less than or equal to distance.

Examples

use ndarray::{array, aview1};
use petal_neighbors::{BallTree, distance};

let points = array![[1., 0.], [2., 0.], [9., 0.]];
let tree = BallTree::euclidean(points).expect("non-empty input");
let indices = tree.query_radius(&aview1(&[3., 0.]), 1.5);
assert_eq!(indices, &[1]);  // The distance to points[1] is less than 1.5.