Struct petal_neighbors::VantagePointTree

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

A data structure for nearest neighbor search in a multi-dimensional space, which is partitioned into two parts for each vantage point: those points closer to the vantage point than a threshold, and those farther.

Implementations

impl<'a, A> VantagePointTree<'a, A> where
    A: Float + Zero + AddAssign + 'a, 

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

Builds a vantage point 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 vantage point 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, needle: &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::{VantagePointTree, distance};

let points = array![[1., 1.], [1., 2.], [9., 9.]];
let tree = VantagePointTree::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);