Module kdtree 

KD-Tree for efficient nearest neighbor searches

This module provides a KD-Tree implementation for efficient nearest neighbor and range searches in multidimensional spaces.

The KD-Tree (k-dimensional tree) is a space-partitioning data structure that organizes points in a k-dimensional space. It enables efficient range searches and nearest neighbor searches.

Features

• Fast nearest neighbor queries with customizable k
• Range queries with distance threshold
• Support for different distance metrics (Euclidean, Manhattan, Chebyshev, etc.)
• Parallel query processing (when using the parallel feature)
• Customizable leaf size for performance tuning

Examples

use scirs2_spatial::KDTree;
use scirs2_core::ndarray::array;

// Create a KD-Tree with points in 2D space
let points = array![[1.0, 2.0], [3.0, 4.0], [5.0, 6.0], [7.0, 8.0]];
let kdtree = KDTree::new(&points).unwrap();

// Find the nearest neighbor to [4.0, 5.0]
let (idx, dist) = kdtree.query(&[4.0, 5.0], 1).unwrap();
assert_eq!(idx.len(), 1); // Should return exactly one neighbor

// Find all points within radius 3.0 of [4.0, 5.0]
let (indices, distances) = kdtree.query_radius(&[4.0, 5.0], 3.0).unwrap();

Advanced Usage

Using custom distance metrics:

use scirs2_spatial::KDTree;
use scirs2_spatial::distance::ManhattanDistance;
use scirs2_core::ndarray::array;

// Create a KD-Tree with Manhattan distance metric
let points = array![[1.0, 2.0], [3.0, 4.0], [5.0, 6.0], [7.0, 8.0]];
let metric = ManhattanDistance::new();
let kdtree = KDTree::with_metric(&points, metric).unwrap();

// Find the nearest neighbor to [4.0, 5.0] using Manhattan distance
let (idx, dist) = kdtree.query(&[4.0, 5.0], 1).unwrap();

Using custom leaf size for performance tuning:

use scirs2_spatial::KDTree;
use scirs2_core::ndarray::array;

// Create a KD-Tree with custom leaf size
let points = array![[1.0, 2.0], [3.0, 4.0], [5.0, 6.0], [7.0, 8.0],
                     [9.0, 10.0], [11.0, 12.0], [13.0, 14.0], [15.0, 16.0]];
let leafsize = 2; // Default is 16
let kdtree = KDTree::with_leaf_size(&points, leafsize).unwrap();

Structs

KDTree

A KD-Tree for efficient nearest neighbor searches

Rectangle

A rectangle representing a hyperrectangle in k-dimensional space