Crate linkcell 

Periodic linked-cell k-nearest neighbour search.

vesin builds cutoff pair lists. nanoflann builds Euclidean KD-trees without a minimum-image convention. This crate is the missing piece: Allen and Tildesley’s linked cells, a k-heap per source, and an index box that grows one axis at a time until the k-th neighbour cannot lie past an unvisited face. The pair itself is Rapaport’s cell shift, not a per-pair nearest integer. pairs_within is the cutoff pair list with integer cell shifts (vesin/tonari ijS); knearest unique-indexes.

Algorithm

1. Fold every position into the primary cell (Cell::fractional, then Cell::cartesian).
2. Bin the folded points on a fractional mesh. The bin count along each axis uses the perpendicular face width, so a sheared dump is not treated as orthogonal.
3. Grow an index box of linked cells. The first visit is the 3×3×3 around the home bin. After that, only an axis whose unvisited plane is still inside the k-th neighbour grows. Occupants are stored in cell order. A neighbour cell whose slab cannot beat the worst heap entry is skipped. The cap is the space diagonal over the minimum cell height, so a shift outside {-1,0,1} is still visited when it is the Euclidean image.

The walk basis depends on the cell. An orthorhombic box, including a rectangular film, is used as stored. A restricted triclinic box (LAMMPS dump bounds, a CON angle, a hexagonal prism) is tilt-reduced in place and the shift is triangular. A general orientation is Minkowski-reduced. pairs_within keeps the caller’s basis, because the reported shift is an integer combination of that H.

Pair distances in the walk are not a per-pair minimum-image wrap. After the fold, a neighbour stencil (jx, jy, jz) contributes Cell::lattice_shift and Cell::dist2_shifted: a Cartesian subtract plus one lattice vector (the vesin / LAMMPS ghost trick). Orthorhombic boxes set the Cell::is_ortho flag and skip the two 3x3 matvecs: three independent wraps, and the shift is a scaled diagonal. The Highway batch (dist2_ortho_diffs) is that wrap for a raw difference. knearest_brute uses it on an orthorhombic box. pairs_within keeps the stencil image and does not wrap the shifted difference again.

Why a unique-cell stamp is wrong

A stamp that visits each linked cell once, with a single shift for every occupant, is not a minimum-image convention. Occupants of one cell can need different images of the same source (a wide bin, or a source near a face). The walk keys on the integer stencil (jx, jy, jz), including wraps: the same rem_euclid bin may appear with more than one Cell::lattice_shift.

Output

knearest returns one Neighbors row per input point, nearest first. knearest_into writes a packed n * k index buffer (-1 in unused slots), the same layout as lc_knearest.

Features

parallel (rayon over sources) is on by default for wall-clock. --no-default-features drops rayon and serializes the walk (re-enable capi if the C ABI is still required). The per-source k-heap (KHeap) stays on the stack for k <= 16; larger k spills to the heap.

Examples

Periodic image, not the raw Cartesian vector:

use linkcell::{knearest, Cell};

let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
let rows = knearest(&xyz, &sim, 1, None, None)?;
assert_eq!(rows[0].indices, vec![1]);
assert!((rows[0].dist2[0] - 0.64).abs() < 1e-12);

Two occupants of one linked cell (the whole box is a single bin) need different images of the source. A unique-cell stamp with one shift cannot serve both.

use linkcell::{knearest, Cell};

let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let xyz = [[0.1, 0.0, 0.0], [1.0, 0.0, 0.0], [9.8, 0.0, 0.0]];
let rows = knearest(&xyz, &sim, 2, None, Some(10.0))?;
assert_eq!(rows[0].indices, vec![2, 1]);
assert!((rows[0].dist2[0] - 0.09).abs() < 1e-12);
assert!((rows[0].dist2[1] - 0.81).abs() < 1e-12);

Packed n * k indices, unused slots -1:

use linkcell::{knearest_into, Cell};

let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]];
let mut out = [0; 4];
knearest_into(&xyz, &sim, 2, None, None, &mut out)?;
assert_eq!(out, [1, -1, 0, -1]);

The C ABI (lc_*) is the hourglass waist: packed n * k indices, matching squared distances, and lc_pairs_within for a cutoff list with the caller’s shift. C++ lives in include/linkcell.hpp as a RAII header over that ABI.

Structs

Cell

Periodic parallelepiped: columns of H, origin, and an ortho flag.

Neighbors

One source’s k nearest neighbours, nearest first.

Pair

One atom-image pair inside the cutoff.

PairColumns

Cutoff rows as columns: i[t], j[t], shift[t], dist2[t].

lc_cell

Periodic parallelepiped. Lattice vectors are a, b, c (same as vesin rows).

lc_pair

One cutoff row: source i, target j, shift S, squared distance. The C++ linkcell::ShiftedPair has this layout.

Enums

Error

Why a search could not run.

Functions

dist2_many

Squared MIC distances from p to each packed candidate in qs.

dist2_ortho_diffs

Orthorhombic wrap of precomputed differences, one reciprocal per axis.

dist2_pairs

Squared MIC distances for packed pair lists ps and qs.

knearest

k-nearest neighbours of every point (or of the masked subset).

knearest_brute

Brute-force k-nearest. Tests and small systems only.

knearest_into

Write k-nearest indices, nearest first, into caller storage.

knearest_into_d2

Write k-nearest indices and squared distances, nearest first.

knearest_into_many

Frame-major batch: xyz is n_frames * n points, out_* are n_frames * n * k. One shared cell. mask is length n or None.

lc_knearest^⚠

k-nearest neighbours for n points.

lc_knearest_d2^⚠

Like lc_knearest, and write squared distances into out_d2.

lc_knearest_many^⚠

Frame-major batch. xyz is n_frames * n packed triples. out_nn / out_d2 are n_frames * n * k. One shared cell. mask is length n or NULL. out_d2 may be NULL.

lc_last_error

Thread-local last-error string from this thread’s most recent lc_knearest.

lc_pairs_within^⚠

Cutoff pairs with the vesin / tonari shift S.

lc_pairs_within_rows^⚠

lc_pairs_within with one array of lc_pair rows.

lc_version

Library version string. Process-static, NUL-terminated. Do not free.

pairs_within

Pairs with dist2 < cutoff², one row per atom-image.

pairs_within_columns

The same rows as pairs_within, as four columns.

pop_efficiencies

POP3 factors for one run: load balance, communication efficiency, parallel efficiency.

pop_engage

Turn POP3 counters on for this process.

pop_prepare

Give every worker a slot. Call once before the timed repetitions.

pop_reset

Zero the useful-time counters. Slot assignment stays.

pop_snapshot

Useful nanoseconds on each worker, in slot order.

reduce_pairs

Drop self images and collapse duplicate (i, j) rows.

reduce_pairs_packed

Same reduction over a packed n * 2 C buffer.

wrap_many

Minimum-image wrap of packed difference vectors.