Crate manifold_knn 

Dynamic-programming k-nearest-neighbor queries for birth-ordered point clouds.

This crate implements the query-side data structure described by Wang et al., Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds.

The paper separates the method into two concerns:

1. Maintain a successor table. When a point j is inserted, append j to every earlier point whose Voronoi cell is pruned by the insertion. In a Delaunay implementation this means appending j to the Delaunay neighbors of j in the prefix triangulation.
2. Answer k-NN queries by first following the dynamic-programming 1-NN path, then expanding only the successor lists of the best candidates.

This crate implements item 2, plus safe helpers for constructing and updating successor tables. With the optional delaunay-3d feature it can also build insertion-time successor tables directly from the delaunay crate’s 3D incremental triangulation API.

Example

use manifold_knn::ManifoldKnn;

let points = vec![
    [0.0, 0.0, 0.0],
    [1.0, 0.0, 0.0],
    [0.0, 1.0, 0.0],
    [0.0, 0.0, 1.0],
];

// Exact but quadratic fallback: every later point is a successor of every
// earlier point. This is useful for tests and small point sets.
let index = ManifoldKnn::<3>::from_complete_successors(points)?;
let nn = index.knn(&[0.2, 0.1, 0.0], 2)?;

assert_eq!(nn.len(), 2);
assert_eq!(nn[0].index, 0);

Re-exports

pub use delaunay3d::Delaunay3dKernel;

pub use delaunay3d::DelaunayManifoldKnn3;

pub use delaunay3d::DelaunayTriangulation3;

Modules

delaunay3d

3D Delaunay integration backed by a custom optimized triangulation.

Structs

DeleteReport

Summary returned by deletion/update operations.

ManifoldKnn

Dynamic-programming k-NN index over a fixed-dimensional Euclidean point set.

Neighbor

A nearest-neighbor result.

QueryWorkspace

Reusable query workspace to avoid allocations during nearest-neighbor queries.

SuccessorTable

Successor table used by the Manifold k-NN dynamic program.

Enums

Error

Errors returned by manifold-knn construction, update, and query APIs.