Struct KdTree 

pub struct KdTree { /* private fields */ }

Efficient KD-Tree implementation for nearest neighbor search.

Nodes live in a single contiguous Vec (nodes); children are referenced by index. root is the index of the tree root (always 0 when non-empty).

Implementations

impl KdTree

pub const NO_CHILD: u32 = NIL

Child value in FlatKdNode meaning “no child”.

pub fn flat_nodes(&self) -> impl ExactSizeIterator<Item = FlatKdNode> + '_

The tree’s nodes in their stored order. The root is the first node (when the tree is not empty), and children are referenced by position in this sequence. A query walks it like any binary kd-tree: go to the child on the query’s side of the split, and visit the other child only if the split plane is closer than the current best match.

pub fn new(points: &[Point3f]) -> Result<Self>

Create a new KD-tree from a slice of points.

Points with a NaN or infinite coordinate are left out of the tree and are never returned as neighbors (indices of the remaining points still refer to points). Organized clouds store invalid returns as NaN; a NaN split value would send every query down one side and make the finite points on the other side unreachable.

pub fn from_points(points: Vec<Point3f>) -> Result<Self>

Like KdTree::new, but takes ownership of the points instead of copying them (useful when the caller already built a converted copy).

pub fn find_k_nearest_into( &self, query: &Point3f, k: usize, out: &mut Vec<(usize, f32)>, )

Find the k nearest neighbors of query, writing them into out as (original_index, squared_distance), closest first.

out is cleared first and its allocation is reused, so calling this in a loop (one buffer per thread) does no allocation per query. This is the hot path of normal estimation. k is expected to be small (tens): neighbors are kept in a sorted array rather than a heap.

pub fn find_nearest_bounded( &self, query: &Point3f, bound_sq: f32, seed: Option<(usize, f32)>, ) -> Option<(usize, f32)>

Find the single nearest neighbor of query, allocation-free.

bound_sq is a squared-distance upper bound: only points strictly closer than it are considered, and the far side of a split is skipped as soon as it cannot beat the best so far. Pass f32::INFINITY for an unbounded search. When the caller already knows a candidate (e.g. last ICP iteration’s match), pass its index and squared distance as seed so the search starts pruned; seed is returned if nothing closer is found.

Returns (original_index, squared_distance), or None if no point lies within the bound and no seed was given. This is the hot path for ICP correspondence search, so — unlike find_k_nearest — it uses a fixed-size stack and no heap, result Vec, or sqrt.

Trait Implementations

impl NearestNeighborSearch for KdTree

fn find_k_nearest(&self, query: &Point3f, k: usize) -> Vec<(usize, f32)>

Find the k nearest neighbors, closest first, as (index, distance).

For many queries in a loop, KdTree::find_k_nearest_into avoids the allocation per call.

fn find_radius_neighbors( &self, query: &Point3f, radius: f32, ) -> Vec<(usize, f32)>

Find all neighbors within radius using an iterative stack-based traversal.