projective-grid

Recover a projective lattice — an (i, j) → point labelling on a square or hexagonal grid — from a set of 2D feature points plus optional per-feature local axis directions.

You bring the points (from whatever corner / feature detector you already have); projective-grid figures out how they tile a regular lattice under perspective and hands back each point's integer grid coordinate together with a fitted projective transform.

The crate is deliberately small and image-free: there are no image, pixel-buffer, or camera types anywhere in the public surface, and no target-specific identifiers (marker IDs, ring IDs, calibration metadata). It is target-agnostic — the same lattice recovery serves a chessboard detector, a laser-dot cloud, a scanned form, or a photographed board game. The detection surface is single-precision (f32); the standalone projective geometry kernel stays generic over f32 / f64 via the [Float] trait.

When to use it

Reach for projective-grid when you already have a cloud of 2D points that should lie on a regular grid and you need to know which grid cell each one is — robustly, under perspective and mild lens distortion.

It handles:

• Perspective + mild distortion — the lattice is fitted projectively, and the grow / topological paths use local geometry that tolerates curvature a single global homography would not.
• Multi-component grids — when the lattice is split into islands (e.g. by occlusion), detect_grid_all returns each connected component with its own labels; detect_grid returns just the largest.
• Component merging — nearby components that share a consistent lattice are reconciled using local geometry only.

When not to use it

This crate does lattice recovery and projective consistency, not feature detection. It will not find corners in an image for you — the caller supplies the points (and, optionally, local axis directions per point). If you have an image and need corners first, run a corner detector and convert its output into PointFeature / OrientedFeature values before calling in.

It recovers both square and hexagonal lattices. Both use the topological assembler — the sole grid builder in this crate. Hex runs the same Delaunay back-half — its triangles are the unit cells directly, so there is no diagonal/quad-merge stage. The lattice family is selected by LatticeKind on the request; there is no further algorithm choice to make.

Three kinds of evidence

How much you know about each point's orientation picks the Evidence variant. The square variants share one back-half — the less-oriented kinds synthesize the missing axes from neighbour geometry and then run the same strategy — so they produce the same GridDetection shape. The same evidence ladder applies to hex (Positions synthesizes three axis families; Oriented1 keeps its measured family and estimates the other two; [Evidence::Oriented3] supplies them directly):

• Unoriented — Evidence::Positions (&[PointFeature]). Just points: a dot grid, a circle grid, or corners with no axis estimate. Both local grid directions are recovered per point from neighbour chords folded modulo π. The synthesis does not assume the axes are 90° apart, but nearest-neighbour selection itself is not projectively invariant. It works when the lattice is the dominant, moderately projected local structure; if your point cloud carries dense sub-lattice clutter (e.g. marker-glyph corners between the true grid points), neighbour statistics cannot recover the axes — supply measured orientations (Oriented1/Oriented2) instead.

• Single-axis — Evidence::Oriented1 (&[OrientedFeature<1>]). One trusted physical family per point (e.g. a detector that recovers a dominant edge orientation). The supplied angle and sigma are kept. Square estimates one missing family; hex estimates two from six-neighbour chord evidence.

• Dual-axis — Evidence::Oriented2 (&[OrientedFeature<2>]). Two local grid directions per point — the native shape, e.g. ChESS-style corner axes. No synthesis; the strongest input.

• Triple-axis — [Evidence::Oriented3] (&[OrientedFeature<3>]). The hex-native shape: a hexagonal lattice has three axis families, and a detector that recovers all three feeds them here. (Square, Oriented3) stays UnsupportedCombination (square has only two families).

Coordinate hypotheses are consumed by the separate check_consistency entry point, which scores caller-proposed labels against a projective fit; they are deliberately not a detection evidence variant.

Evidence × lattice support matrix

All square and hex paths run the same topological assembler — the sole grid builder in the crate.

Readiness

The support matrix says which combinations are implemented, not that every combination has equal field evidence. (Square, Oriented2)—including the in-workspace chessboard detector—is the mature path. Square Positions and Oriented1 are evidence-limited. Hex Positions, Oriented1, and Oriented3 are experimental: deterministic synthetic affine/perspective, noise, dropout, shuffle, seam, and clutter fixtures cover their current contract, but no real-image campaign has established production recall or precision. Treat missing detections as expected and validate labels for the target domain.

Quickstart

A fully self-contained, image-free example: synthesize a small 3×3 grid, wrap the features as evidence, detect, and read the recovered labels. (This is the body of examples/hello_grid.rs — cargo run -p projective-grid --example hello_grid.)

use nalgebra::Point2;
use projective_grid::{
    detect_grid, DetectionRequest, Evidence, LatticeKind, LocalAxis,
    OrientedFeature, PointFeature,
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Build a 3x3 grid of oriented features. The `+ j * 6.0` term adds a
    // mild perspective-style shear so this is a genuine projective grid.
    let mut features: Vec<OrientedFeature<2>> = Vec::new();
    for j in 0..3 {
        for i in 0..3 {
            let x = 60.0 + i as f32 * 40.0 + j as f32 * 6.0;
            let y = 50.0 + j as f32 * 40.0;
            let point = PointFeature::new(features.len(), Point2::new(x, y));
            // Two roughly-orthogonal local axes: horizontal and vertical.
            let axes = [
                LocalAxis::new(0.0, Some(0.02)),
                LocalAxis::new(std::f32::consts::FRAC_PI_2, Some(0.02)),
            ];
            features.push(OrientedFeature::new(point, axes));
        }
    }

    // Wrap as Oriented2 evidence and ask for a square lattice.
    let request = DetectionRequest::new(
        LatticeKind::Square,
        Evidence::Oriented2(&features),
    );

    let detection = detect_grid(request)?;
    for entry in detection.grid().entries() {
        // coord.u = i, coord.v = j; source_index maps back to the input slice.
        println!("(i={}, j={}) <- feature {}", entry.coord.u, entry.coord.v, entry.source_index);
    }
    Ok(())
}

Running it prints all nine features, labelled (0,0) through (2,2) with a sub-pixel fit residual.

Algorithm (square)

Square lattice detection uses the topological assembler — the sole grid builder in the crate. It consumes Evidence::Oriented2 (or synthesizes axes from Positions / Oriented1) and produces a GridDetection:

• the Shu/Brunton/Fiala axis-driven grid finder (Delaunay triangulation + a per-cell axis test). Image-free; recovers dense grids and copes well with distortion. May return several components (see detect_grid_all).

Hex also uses the topological assembler. On a hex point lattice the Delaunay triangles are the unit cells, so the diagonal/quad-merge stage is bypassed; the axial (q, r) walk and the projective fit back-half are shared with the square topological path.

Inputs & outputs

Inputs are wrapped in an Evidence enum — see Three kinds of evidence above. For square lattices Positions, Oriented1, and Oriented2 are supported; for hex lattices Positions, Oriented1, and Oriented3 are supported on the topological path. The remaining combinations (Square, Oriented3) and (Hex, Oriented2) return UnsupportedCombination.

Output is a GridDetection. Its fitted transform is mandatory on success; rejected evidence is available only after enabling the diagnostics feature, through the projective_grid::diagnostics entry points:

Learn more

Algorithm deep-dive and conceptual background: book chapter. Release posture and remaining stabilization work: road to 1.0. Version history and release notes: changelog.

License

Licensed under either of MIT or Apache-2.0 at your option.