Struct KdTree 

pub struct KdTree<F>
where
    F: Float + FromPrimitive + Debug + PartialOrd + FloatCore,
{ /* private fields */ }

KD-Tree for efficient nearest neighbor searches

The KD-tree partitions space recursively, making nearest neighbor searches much more efficient than brute force methods.

Examples

use scirs2_core::ndarray::Array2;
use scirs2_interpolate::spatial::kdtree::KdTree;

// Create sample 2D points
let points = Array2::from_shape_vec((5, 2), vec![
    0.0, 0.0,
    1.0, 0.0,
    0.0, 1.0,
    1.0, 1.0,
    0.5, 0.5,
]).unwrap();

// Build KD-tree
let kdtree = KdTree::new(points).unwrap();

// Find the nearest neighbor to point (0.6, 0.6)
let query = vec![0.6, 0.6];
let (idx, distance) = kdtree.nearest_neighbor(&query).unwrap();

// idx should be 4 (the point at (0.5, 0.5))
assert_eq!(idx, 4);

Implementations

impl<F> KdTree<F>

where F: Float + FromPrimitive + Debug + PartialOrd + FloatCore,

pub fn new<S>(points: ArrayBase<S, Ix2>) -> InterpolateResult<Self>

where S: Data<Elem = F>,

Create a new KD-tree from points

Arguments

• points - Point coordinates with shape (n_points, n_dims)

Returns

A new KD-tree for efficient nearest neighbor searches

pub fn with_leaf_size<S>( _points: ArrayBase<S, Ix2>, leaf_size: usize, ) -> InterpolateResult<Self>

where S: Data<Elem = F>,

Create a new KD-tree with a specified leaf size

Arguments

• points - Point coordinates with shape (n_points, n_dims)
• leaf_size - Maximum number of points in a leaf node

Returns

A new KD-tree for efficient nearest neighbor searches

pub fn nearest_neighbor(&self, query: &[F]) -> InterpolateResult<(usize, F)>

Find the nearest neighbor to a query point

Arguments

• query - Query point coordinates

Returns

Tuple containing (point_index, distance) of the nearest neighbor

pub fn k_nearest_neighbors( &self, query: &[F], k: usize, ) -> InterpolateResult<Vec<(usize, F)>>

Find k nearest neighbors to a query point

Arguments

• query - Query point coordinates
• k - Number of nearest neighbors to find

Returns

Vector of (point_index, distance) tuples, sorted by distance

pub fn points_within_radius( &self, query: &[F], radius: F, ) -> InterpolateResult<Vec<(usize, F)>>

Find all points within a specified radius of a query point

Arguments

• query - Query point coordinates
• radius - Search radius

Returns

Vector of (point_index, distance) tuples for all points within radius

pub fn len(&self) -> usize

Get the number of points in the KD-tree

pub fn is_empty(&self) -> bool

Check if the KD-tree is empty

pub fn dim(&self) -> usize

Get the dimension of points in the KD-tree

pub fn points(&self) -> &Array2<F>

Get a reference to the points in the KD-tree

pub fn radius_neighbors( &self, query: &[F], radius: F, ) -> InterpolateResult<Vec<(usize, F)>>

Find all points within a specified radius (alias for points_within_radius)

Arguments

• query - Query point coordinates
• radius - Search radius

Returns

Vector of (point_index, distance) tuples for all points within radius

pub fn radius_neighbors_view( &self, query: &ArrayView1<'_, F>, radius: F, ) -> InterpolateResult<Vec<(usize, F)>>

Find all points within a specified radius using an array view

Arguments

• query - Query point coordinates as an array view
• radius - Search radius

Returns

Vector of (point_index, distance) tuples for all points within radius

pub fn k_nearest_neighbors_optimized( &self, query: &[F], k: usize, max_distance: Option<F>, ) -> InterpolateResult<Vec<(usize, F)>>

Enhanced k-nearest neighbor search with early termination optimization

This method provides improved performance for k-NN queries by using adaptive search strategies and early termination when possible.

Arguments

• query - Query point coordinates
• k - Number of nearest neighbors to find
• max_distance - Optional maximum search distance for early termination

Returns

Vector of (point_index, distance) tuples, sorted by distance

pub fn query_nearest( &self, query: &ArrayView1<'_, F>, k: usize, ) -> InterpolateResult<Array1<usize>>

Find the nearest neighbors to a query point and return their indices

Arguments

• query - Coordinates of the query point as an array view
• k - Number of nearest neighbors to find

Returns

An array of indices of the k nearest neighbors

Trait Implementations

impl<F> Clone for KdTree<F>

where F: Float + FromPrimitive + Debug + PartialOrd + FloatCore + Clone,

fn clone(&self) -> KdTree<F>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F> Debug for KdTree<F>

where F: Float + FromPrimitive + Debug + PartialOrd + FloatCore + Debug,

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

Formats the value using the given formatter.

impl<F> OptimizedSpatialSearch<F> for KdTree<F>

where F: Float + FromPrimitive + Debug + Send + Sync + FloatCore,

Default implementation of OptimizedSpatialSearch for KdTree

fn batch_k_nearest_neighbors( &self, queries: &ArrayView2<'_, F>, k: usize, ) -> InterpolateResult<Vec<Vec<(usize, F)>>>

Perform batch k-nearest neighbor search for multiple queries

fn parallel_k_nearest_neighbors( &self, queries: &ArrayView2<'_, F>, k: usize, workers: Option<usize>, ) -> InterpolateResult<Vec<Vec<(usize, F)>>>

Perform parallel k-nearest neighbor search

fn adaptive_k_nearest_neighbors( &self, query: &[F], k: usize, ) -> InterpolateResult<Vec<(usize, F)>>

Adaptive k-nearest neighbor search that adjusts strategy based on query characteristics

fn multi_radius_search( &self, query: &[F], radii: &[F], ) -> InterpolateResult<Vec<Vec<(usize, F)>>>

Range search with multiple radii for the same query point