Crate aann 

Approximate all-nearest-neighbour search over neighbourhood graphs.

Given two 3D point clouds, each equipped with a neighbourhood graph in CSR form (e.g. the vertex adjacency of a Delaunay triangulation, see graph_from_simplices), this crate finds for every point of the query cloud its (approximate) nearest neighbour(s) in the target cloud via a warm-started greedy graph descent. Distances are SIMD-accelerated via the wide crate, so the crate builds on stable Rust.

The Python bindings live behind the non-default python cargo feature; with default features this is a pure-Rust library.

use aann::{graph_from_simplices, PreparedF64};
use aann::ndarray::array;

// Target cloud: the 4 corners of the unit tetrahedron, fully connected
// by a single Delaunay simplex.
let points = array![[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]];
let (indptr, indices) = graph_from_simplices(array![[0u64, 1, 2, 3]].view(), 4);
let target = PreparedF64::new(points.view(), indptr.view(), indices.view());

// Query cloud with its own neighbourhood graph (here: two points linked
// to each other).
let queries = array![[0.1, 0.0, 0.0], [0.9, 0.1, 0.0]];
let (qptr, qidx) = (array![0u32, 1, 2], array![1u32, 0]);
let (dists, idxs) = target.query(queries.view(), qptr.view(), qidx.view(), None);
assert_eq!(idxs.to_vec(), vec![0, 1]);
assert!((dists[0] - 0.1).abs() < 1e-12);

Re-exports

pub use ndarray;

Structs

GroupedQueriesF32

A reusable, Morton-sorted concatenation of many query clouds’ points, built ONCE for a whole all-by-all and descended against each target with $prepared::query_grouped. The concat + Morton sort are target- independent, so hoisting them here (instead of redoing them per target) is what lets the grouped descent keep its ~2x single-thread / ~4x multi- thread gain rather than spending ~half its time re-sorting per target.

GroupedQueriesF64

A reusable, Morton-sorted concatenation of many query clouds’ points, built ONCE for a whole all-by-all and descended against each target with $prepared::query_grouped. The concat + Morton sort are target- independent, so hoisting them here (instead of redoing them per target) is what lets the grouped descent keep its ~2x single-thread / ~4x multi- thread gain rather than spending ~half its time re-sorting per target.

NeighborhoodF32

A neighborhood graph over $t coordinates.

NeighborhoodF64

A neighborhood graph over $t coordinates.

PreparedF32

A prepared neighbourhood graph that owns its SIMD-packed points and CSR adjacency, so the packing is done once at construction and reused across every query. This is the persistent counterpart to the per-call $search: building let tree = $prepared::new(...) once and calling tree.query(...) many times (e.g. one target vs many query clouds, or an all-by-all) avoids repacking the target on each call.

PreparedF64

A prepared neighbourhood graph that owns its SIMD-packed points and CSR adjacency, so the packing is done once at construction and reused across every query. This is the persistent counterpart to the per-call $search: building let tree = $prepared::new(...) once and calling tree.query(...) many times (e.g. one target vs many query clouds, or an all-by-all) avoids repacking the target on each call.

Workspace

Reusable per-thread scratch for the k=1 all-nearest-neighbour descent (search_into_f64 / search_into_f32 and the query_*_into methods).

Functions

box_box_dist2_f32

Squared euclidean distance between two axis-aligned boxes (0 when they overlap). A lower bound on the distance between any point of box A and any point of box B, so $box_box_dist2(..) > ub² proves no pair is within ub – lets a whole separated query cloud be skipped in one test.

box_box_dist2_f64

Squared euclidean distance between two axis-aligned boxes (0 when they overlap). A lower bound on the distance between any point of box A and any point of box B, so $box_box_dist2(..) > ub² proves no pair is within ub – lets a whole separated query cloud be skipped in one test.

box_dist2_f32

Squared euclidean distance from packed point p to the axis-aligned box [bmin, bmax] (0 when p lies inside). Because the box contains every target point, this is a lower bound on p’s distance to any of them, so $box_dist2(..) > ub² proves no target lies within ub – the geometric hook the greedy descent otherwise lacks. The packed pad lane is 0 in p, bmin and bmax, so it contributes nothing.

box_dist2_f64

Squared euclidean distance from packed point p to the axis-aligned box [bmin, bmax] (0 when p lies inside). Because the box contains every target point, this is a lower bound on p’s distance to any of them, so $box_dist2(..) > ub² proves no target lies within ub – the geometric hook the greedy descent otherwise lacks. The packed pad lane is 0 in p, bmin and bmax, so it contributes nothing.

euclidean_distance_f32

Squared euclidean distance between two packed points.

euclidean_distance_f64

Squared euclidean distance between two packed points.

find_nn_f32

Approximate nearest neighbour of p among the points in y, via a greedy descent that starts at start. The descent moves to a strictly-closer node, or – on an exact distance tie – to the one with the lower vertex id. Without that tie-break the incumbent always wins, so which of several equidistant points is returned depends on the start vertex, and the start vertex depends on how the caller batched its queries (see morton_perm). Ties are common on grid-quantised clouds (e.g. resampled skeletons), where the unstable index picks a different tangent vector downstream.

find_nn_f64

Approximate nearest neighbour of p among the points in y, via a greedy descent that starts at start. The descent moves to a strictly-closer node, or – on an exact distance tie – to the one with the lower vertex id. Without that tie-break the incumbent always wins, so which of several equidistant points is returned depends on the start vertex, and the start vertex depends on how the caller batched its queries (see morton_perm). Ties are common on grid-quantised clouds (e.g. resampled skeletons), where the unstable index picks a different tangent vector downstream.

graph_from_simplices

Build a vertex-adjacency CSR graph from Delaunay tetrahedra.

morton_perm

Argsort points into Morton (Z-order) so spatially-near points are adjacent. Returns perm with perm[k] = original index of the k-th point in Z-order. Used by the per-target grouped descent to interleave many query clouds so co-located points (from different clouds) share a block – and thus one gather.

pack_points_f32

Pack an (N, 3) point array into SIMD [x, y, z, 0.0] lanes.

pack_points_f64

Pack an (N, 3) point array into SIMD [x, y, z, 0.0] lanes.

search_blocked_f32

PROTOTYPE – blocked/batched k=1 all-nearest-neighbour descent.

search_blocked_f64

PROTOTYPE – blocked/batched k=1 all-nearest-neighbour descent.

search_f32

The full all-nearest-neighbours search over two graphs: for each point in x, find its nearest neighbour among the points in y. Allocates the output arrays and scratch fresh; for an all-by-all where buffers can be recycled, prefer $search_into / $prepared::query_prepared_into.

search_f64

The full all-nearest-neighbours search over two graphs: for each point in x, find its nearest neighbour among the points in y. Allocates the output arrays and scratch fresh; for an all-by-all where buffers can be recycled, prefer $search_into / $prepared::query_prepared_into.

search_into_f32

Buffer-reuse form of $search: writes each query point’s nearest neighbour into the caller-owned dists/idx (both resized to the query cloud size) and recycles the DFS scratch held in ws. With a warm ws and warm output buffers this performs no heap allocation – the hot path for an all-by-all inner loop (see $prepared::query_prepared_into). Behaviour is identical to $search; only the buffers’ provenance differs.

search_into_f64

Buffer-reuse form of $search: writes each query point’s nearest neighbour into the caller-owned dists/idx (both resized to the query cloud size) and recycles the DFS scratch held in ws. With a warm ws and warm output buffers this performs no heap allocation – the hot path for an all-by-all inner loop (see $prepared::query_prepared_into). Behaviour is identical to $search; only the buffers’ provenance differs.

search_k_f32

The k>1 all-nearest-neighbours search: the same DFS walk and warm-start chaining as the k=1 $search, but each query runs the best-first $findk and is seeded with the previous query’s best hit. Rows are (inf, |y|)-padded when the search exhausts with fewer than k results (disconnected graph or k > |y|); the outer loop restarts the walk on every unvisited x vertex, so disconnected query graphs are covered too.

search_k_f64

The k>1 all-nearest-neighbours search: the same DFS walk and warm-start chaining as the k=1 $search, but each query runs the best-first $findk and is seeded with the previous query’s best hit. Rows are (inf, |y|)-padded when the search exhausts with fewer than k results (disconnected graph or k > |y|); the outer loop restarts the walk on every unvisited x vertex, so disconnected query graphs are covered too.

search_pruned_f32

Bound-aware $search: prune = Some((target_min, target_max, ub, query_box?)) reports the miss marker (inf, |y|) for every query point with no y neighbour within ub, using the target box to skip the descent where it provably can’t help (see $search_into / $resolve_prune). None is plain $search.

search_pruned_f64

Bound-aware $search: prune = Some((target_min, target_max, ub, query_box?)) reports the miss marker (inf, |y|) for every query point with no y neighbour within ub, using the target box to skip the descent where it provably can’t help (see $search_into / $resolve_prune). None is plain $search.