Struct KdTree

pub struct KdTree;

Implementation of K-D tree, a fast space-partitioning data structure. For each parent node, the indexed points are split with a hyperplane into two child nodes. Due to its tree-like structure, the K-D tree performs spatial queries in O(k * logN) time, where k is the number of points returned by the query. Calling from_batch returns a KdTree.

More details can be found here.

Unlike other NearestNeighbour implementations, KdTree requires that points be laid out contiguously in memory and will panic otherwise.

Implementations

impl KdTree

pub fn new() -> Self

Creates an instance of KdTree

Trait Implementations

impl Clone for KdTree

fn clone(&self) -> KdTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for KdTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for KdTree

fn default() -> KdTree

Returns the “default value” for a type.

impl NearestNeighbour for KdTree

fn from_batch_with_leaf_size<'a, F: Float, DT: Data<Elem = F>, D: 'a + Distance<F>>( &self, batch: &'a ArrayBase<DT, Ix2>, leaf_size: usize, dist_fn: D, ) -> Result<Box<dyn Send + Sync + NearestNeighbourIndex<F> + 'a>, BuildError>

Builds a spatial index using a MxN two-dimensional array representing M points with N dimensions. Also takes leaf_size, which specifies the number of elements in the leaf nodes of tree-like index structures.

fn from_batch<'a, F: Float, DT: Data<Elem = F>, D: 'a + Distance<F>>( &self, batch: &'a ArrayBase<DT, Ix2>, dist_fn: D, ) -> Result<Box<dyn Send + Sync + NearestNeighbourIndex<F> + 'a>, BuildError>

Builds a spatial index using a default leaf size. See from_batch_with_leaf_size for more information.

impl PartialEq for KdTree

fn eq(&self, other: &KdTree) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for KdTree

impl StructuralPartialEq for KdTree