Crate flannrust 

Rust port of nanoflann: a STATIC kd-tree (tree::KdTree, KDTreeSingleIndexAdaptor) and a DYNAMIC Bentley-Saxe forest (dynamic::DynamicKdTree, KDTreeSingleIndexDynamicAdaptor) supporting point add/remove after construction; behavioral parity with nanoflann 1.12.1.

Contracts (see the README for the full list, deviations, and input domain)

• L2/L2Simple distances and radii are SQUARED (L1 is summed absolute value); SO2 is an UNsquared wrapped angle of only the LAST dimension (single-shot wrap, inputs assumed already in [-pi, pi]).
• Radius search is strictly dist < radius (boundary excluded); box search is inclusive on all faces, unsorted, traversal order, no params.
• kNN ties keep traversal order by default (result_set::KeepInsertionOrder); opt into result_set::SmallestIndexWins for NANOFLANN_FIRST_MATCH.
• eps: a node is visited iff mindist * (1 + eps) <= worst_dist, eps widened to the distance type BEFORE the multiply-add.
• Queries snapshot the dataset at build(); growth afterward is invisible until a rebuild.
• ResultItem is #[repr(C)] { index, distance }.
• Coordinates must be finite: NaN/±inf inputs are outside this crate’s domain (see the README’s “Input domain” section).
• Under the default parallel feature, KdTreeBuilder::build() requires DataSource: Sync; non-Sync data sources use tree::KdTreeBuilder::build_sequential instead. dynamic::DynamicKdTreeBuilder::build never needs Sync at all (the dynamic forest has no parallel build path).
• dynamic::DynamicKdTree::add_points’s contiguous-append contract (DEVIATION from C++): a genuinely-new (non-reactivation) point index must equal the forest’s running point_count at the moment it is processed — nanoflann silently corrupts its bookkeeping on a misaligned call, this port panics instead. Reactivating a previously-removed index is exempt (legally any start/end).
• dynamic::DynamicKdTree::find_neighbors’s empty-forest quirk (inherited from C++): with zero occupied slots, result.full() reflects an untouched result set — false for knn/rknn, but hardwired true for result_set::RadiusResultSet regardless of whether anything was ever added.
• The dim-32/64 L2/L1 kernel speedup (M2.5, see the README’s “dim-32/64 knn” section) requires the DataSource impl to override data_source::DataSource::point_row; a DataSource that only implements point_component gets none of it, at any dimensionality.

Example

use flannrust::{ConstDim, KdTreeBuilder};

let pts: &[[f64; 3]] = &[
    [0.0, 0.0, 0.0],
    [10.0, 10.0, 10.0],
    [1.0, 1.0, 1.0],
];
let tree = KdTreeBuilder::new(ConstDim::<3>, pts).build();

let mut indices = [0u32; 2];
let mut dists = [0.0f64; 2];
let found = tree.knn_search(&[0.1, 0.1, 0.1], &mut indices, &mut dists);

assert_eq!(found, 2);
assert_eq!(indices[0], 0); // nearest point is [0.0, 0.0, 0.0]

Re-exports

pub use bbox::Interval;

pub use data_source::DataSource;

pub use data_source::FlatSlice;

pub use data_source::OwnedRows;

pub use dim::ConstDim;

pub use dim::Dim;

pub use dim::DynDim;

pub use dynamic::DynamicKdTree;

pub use dynamic::DynamicKdTreeBuilder;

pub use filter::AcceptAll;

pub use filter::PointFilter;

pub use metric::Distance;

pub use metric::L2Fma;

pub use metric::L2Simple;

pub use metric::L1;

pub use metric::L2;

pub use metric::SO2;

pub use metric::SO3;

pub use params::BuildThreads;

pub use params::SearchParams;

pub use result_set::KeepInsertionOrder;

pub use result_set::KnnResultSet;

pub use result_set::RadiusResultSet;

pub use result_set::ResultItem;

pub use result_set::ResultSet;

pub use result_set::RknnResultSet;

pub use result_set::SmallestIndexWins;

pub use result_set::TieBreak;

pub use scalar::DistanceValue;

pub use scalar::IndexType;

pub use scalar::Scalar;

pub use tree::KdTree;

pub use tree::KdTreeBuilder;

Modules

bbox

Per-dimension [low, high] bounding intervals (Interval) and the dataset-bounding-box scan (compute_bounding_box) used to seed the tree builder’s root box.

data_source

Zero-copy dataset access: the DataSource trait callers implement to hand their point cloud to a KdTreeBuilder, plus three built-in implementations (&[[T; N]], the row-major FlatSlice, and the owned row-major OwnedRows).

dim

Dimensionality strategy: compile-time (ConstDim<N>) or runtime (DynDim), both implementing the Dim trait so the rest of the crate is generic over which one a tree was built with.

dynamic

Bentley-Saxe dynamic forest: a faithful port of nanoflann’s KDTreeSingleIndexDynamicAdaptor (nanoflann.hpp:2521-2718) plus the sub-tree class it wraps, KDTreeSingleIndexDynamicAdaptor_ (nanoflann.hpp:2248-2504, in particular its buildIndex() at nanoflann.hpp:2345-2367). This module provides the FOREST BOOKKEEPING — add_points/remove_point/the merge-and-rebuild schedule — and SEARCH: DynamicKdTree::find_neighbors (= C++’s forest findNeighbors, nanoflann.hpp:2704-2713) plus the additive knn_search/rknn_search/ radius_search wrappers, all tombstone-filtered via TombstoneFilter.

filter

Per-point search filter — the M2 seam for nanoflann’s CRTP isActive() hook (nanoflann.hpp ~1240: if (!obj.isActive(accessor)) continue;). The static adaptor’s isActive always returns true; the (future, M2) dynamic adaptor overrides it to skip tombstoned (removed) points.

metric

Distance metric adaptors, ported verbatim from nanoflann 1.12.1’s L1_Adaptor / L2_Adaptor / L2_Simple_Adaptor / SO2_Adaptor / SO3_Adaptor (nanoflann.hpp lines 552-783). The 4-way unroll and descending-remainder summation order is preserved exactly so our distances match the C++ bit-for-bit on well-behaved (e.g. integer-valued) data — later milestones cross-validate against the reference implementation.

params

Search-time parameters (nanoflann’s SearchParameters, nanoflann.hpp:874-881).

result_set

Result-set collectors: the ResultSet trait the tree walk feeds candidates into, its built-in implementations (KnnResultSet, RknnResultSet, RadiusResultSet), and the TieBreak policy that decides equal-distance ordering.

scalar

Scalar traits: coordinate element types (Scalar), accumulated distance values (DistanceValue), and point-index types (IndexType). f32/f64 implement Scalar/DistanceValue; u32/u64/usize implement IndexType.

tree

Public façade: KdTreeBuilder (configuration) and KdTree (the built, queryable index). Wires together dim.rs/data_source.rs/metric.rs (configuration), build.rs (construction), and search.rs (queries).