projective_grid/lattice/

mod.rs

//! Lattice-family axis: the parameter that the strategies and the shared
//! back-half are written against, rather than a copy per family.
//!
//! This module hosts the family-agnostic coordinate types ([`Coord`],
//! [`GridDimensions`], [`GridTransform`]), the [`LatticeKind`] selector, and
//! the [`Lattice`] trait that captures the per-family geometry a recovery
//! pipeline needs: how a lattice coordinate maps into the model plane, the
//! cardinal neighbour offsets, and the coordinate symmetry group.
//!
//! Today only [`Square`] is implemented; [`Hex`] is a
//! roadmap stub (see `docs/DESIGN.md` "Extending to hex"). Both the strategies
//! and `shared::fit` reach the geometry through [`LatticeKind`] /
//! [`Lattice::model_point`], so adding hex detection is a fill-in-the-trait
//! task rather than a new folder tree.

use nalgebra::{Point2, Vector2};

pub mod hex;
pub mod predict;
pub mod square;

pub use hex::Hex;
pub use predict::{predict_grid_position, PredictedPosition};
pub use square::Square;

/// How the topological pipeline turns Delaunay triangles into lattice cells.
///
/// The axis-driven topological grid finder triangulates the feature cloud and
/// then has to recover the lattice cells from the triangle mesh. The recovery
/// shape differs by family:
///
/// * On a **square** lattice a unit cell is a quad, which the Delaunay
///   triangulation splits into two triangles sharing the cell **diagonal**.
///   The pipeline classifies that diagonal, then merges the triangle pair back
///   into one quad in the internal topological pipeline.
/// * On a **hex** point lattice (one feature per lattice node) the Delaunay
///   triangles **are** the unit cells — three mutually-adjacent nodes form an
///   equilateral-ish triangle, and there is no diagonal class. The triangle-pair
///   merge is bypassed entirely; each kept triangle is walked directly.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum CellTopology {
    /// Merge diagonal-sharing triangle pairs into quads (square lattice).
    TrianglePairToQuad,
    /// Each Delaunay triangle is itself a unit cell (hex point lattice).
    TriangleIsCell,
}

/// Integer coordinate on a lattice.
///
/// For square grids this is `(u, v) = (i, j)`. For hex grids this is axial
/// `(u, v) = (q, r)`.
///
/// This is the canonical integer grid-coordinate type for the whole
/// calibration-target workspace; it serializes as a `{ "u", "v" }` object.
#[derive(
    Clone,
    Copy,
    Debug,
    Default,
    PartialEq,
    Eq,
    Hash,
    PartialOrd,
    Ord,
    serde::Serialize,
    serde::Deserialize,
)]
#[non_exhaustive]
pub struct Coord {
    /// First lattice coordinate: square `i`, or hex axial `q`.
    pub u: i32,
    /// Second lattice coordinate: square `j`, or hex axial `r`.
    pub v: i32,
}

impl Coord {
    /// Construct a coordinate from two integer components.
    pub const fn new(u: i32, v: i32) -> Self {
        Self { u, v }
    }
}

/// Known maximum grid extent, counted in observable feature positions.
///
/// For a square chessboard this is the number of corner intersections, not
/// the number of black/white cells. A partially visible detection may span
/// fewer positions, but a returned coordinate span never exceeds these
/// bounds after canonical orientation is chosen.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub struct GridDimensions {
    /// Maximum number of feature positions along the first lattice axis.
    pub width: usize,
    /// Maximum number of feature positions along the second lattice axis.
    pub height: usize,
}

impl GridDimensions {
    /// Construct maximum feature-position dimensions.
    pub const fn new(width: usize, height: usize) -> Self {
        Self { width, height }
    }
}

/// Supported lattice families.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
#[non_exhaustive]
#[serde(rename_all = "snake_case")]
pub enum LatticeKind {
    /// Orthogonal square lattice.
    Square,
    /// Axial-coordinate hexagonal lattice.
    Hex,
}

impl LatticeKind {
    /// Map an integer lattice coordinate into the model plane.
    ///
    /// Square coordinates map to `(u, v)`. Hex axial coordinates map to
    /// `(q + 0.5*r, sqrt(3)/2*r)`, using unit nearest-neighbour spacing in the
    /// model plane.
    ///
    /// This dispatches to the [`Lattice::model_point`] of the family impl, so
    /// callers holding only a [`LatticeKind`] need not name the concrete family
    /// type.
    pub fn model_point(self, coord: Coord) -> Point2<f32> {
        match self {
            Self::Square => Square.model_point(coord),
            Self::Hex => Hex.model_point(coord),
        }
    }

    /// Cardinal neighbour offsets for this family (4 for square, 6 for hex).
    pub fn neighbour_offsets(self) -> &'static [Coord] {
        match self {
            Self::Square => Square.neighbour_offsets(),
            Self::Hex => Hex.neighbour_offsets(),
        }
    }

    /// The coordinate symmetry group for this family (D4 for square,
    /// D6 for hex).
    pub fn symmetry_transforms(self) -> &'static [GridTransform] {
        match self {
            Self::Square => Square.symmetry_transforms(),
            Self::Hex => Hex.symmetry_transforms(),
        }
    }

    /// Number of distinct axis families: 2 for square (`±u`, `±v`), 3 for hex
    /// (the three axial directions). This is the `k` the topological
    /// classifier matches each edge against.
    pub fn axis_family_count(self) -> usize {
        match self {
            Self::Square => Square.axis_family_count(),
            Self::Hex => Hex.axis_family_count(),
        }
    }

    /// Unit model-plane directions of the `k` primitive axis families.
    ///
    /// Returns one direction per family (`axis_family_count()` of them), each a
    /// unit vector in the model plane. For square these are `(1,0)` and `(0,1)`;
    /// for hex they are the three axial step directions folded into the upper
    /// half-plane. The topological pipeline uses these as the canonical
    /// orientation targets when synthesizing per-corner axes.
    pub fn model_axis_directions(self) -> &'static [Vector2<f32>] {
        match self {
            Self::Square => Square.model_axis_directions(),
            Self::Hex => Hex.model_axis_directions(),
        }
    }

    /// How Delaunay triangles map to lattice cells for this family.
    pub fn cell_topology(self) -> CellTopology {
        match self {
            Self::Square => Square.cell_topology(),
            Self::Hex => Hex.cell_topology(),
        }
    }
}

/// Crate-private sealing for [`Lattice`].
///
/// External crates can *name* and *use* [`Lattice`] (it appears in the public
/// API of the shared back-half) but cannot *implement* it. This lets the
/// trait grow new required methods in later phases — the hex-detection axes,
/// the cell-type discriminant, etc. (see `docs/DESIGN.md` "Extending to hex")
/// — without those additions being a breaking change for downstream impls,
/// because the only impls are the two zero-sized markers in this crate.
mod private {
    /// Sealed-trait marker. Implemented only for the in-crate lattice markers.
    pub trait Sealed {}

    impl Sealed for super::Square {}
    impl Sealed for super::Hex {}
}

/// Per-family lattice geometry.
///
/// A [`Lattice`] impl supplies the geometry a recovery pipeline needs without
/// hard-coding the family: how a coordinate maps into the model plane, the
/// cardinal neighbour offsets used to walk the graph, and the coordinate
/// symmetry group used by component merge. The shared back-half and (in the
/// hex roadmap) the strategy skeletons are written against this trait so a new
/// family is added by implementing the trait, not by copying machinery.
///
/// Implementations are zero-sized markers ([`Square`], [`Hex`]); the
/// [`LatticeKind`] enum is the runtime selector that dispatches to them.
///
/// # Sealed
///
/// This trait is **sealed**: it has a crate-private supertrait
/// (`private::Sealed`) so only the two in-crate markers can implement it.
/// The seal is deliberate — extending hex detection adds new required methods
/// (axis-family count, model-plane axis directions, cell-type discriminant).
/// Because no external crate can implement `Lattice`, those additions are
/// non-breaking. External callers depend on `Lattice` only as a
/// bound / through [`LatticeKind`] dispatch, never as an impl target.
pub trait Lattice: Copy + private::Sealed {
    /// The [`LatticeKind`] this impl corresponds to.
    const KIND: LatticeKind;

    /// Map an integer lattice coordinate into the model plane (unit
    /// nearest-neighbour spacing).
    fn model_point(self, coord: Coord) -> Point2<f32>;

    /// Cardinal neighbour offsets used to walk between adjacent lattice
    /// coordinates.
    fn neighbour_offsets(self) -> &'static [Coord];

    /// The coordinate symmetry group (dihedral) for this family.
    fn symmetry_transforms(self) -> &'static [GridTransform];

    /// Number of distinct axis families (`k`): 2 for square, 3 for hex.
    fn axis_family_count(self) -> usize;

    /// Unit model-plane directions of the `k` primitive axis families.
    fn model_axis_directions(self) -> &'static [Vector2<f32>];

    /// How Delaunay triangles map to lattice cells for this family.
    fn cell_topology(self) -> CellTopology;
}

/// An affine integer lattice-coordinate transform:
/// `destination = matrix * source + translation`.
///
/// The source and destination coordinates belong to the same [`LatticeKind`].
/// Pure D4/D6 symmetry transforms have zero translation; target-detector
/// alignments use the same type with a board-frame translation. This type
/// contains no image-space or pixel-space coordinates.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
#[non_exhaustive]
pub struct GridTransform {
    lattice: LatticeKind,
    matrix: [[i32; 2]; 2],
    translation: [i32; 2],
}

impl GridTransform {
    /// The identity transform for a square lattice.
    ///
    /// Prefer [`Self::identity`] when the lattice family is dynamic. This
    /// constant exists for the workspace's square-target result defaults.
    pub const IDENTITY: Self = Self::identity(LatticeKind::Square);

    /// Construct a lattice transform from its family, row-major linear part,
    /// and destination-frame translation.
    pub const fn new(lattice: LatticeKind, matrix: [[i32; 2]; 2], translation: [i32; 2]) -> Self {
        Self {
            lattice,
            matrix,
            translation,
        }
    }

    /// Construct the identity transform for `lattice`.
    pub const fn identity(lattice: LatticeKind) -> Self {
        Self::new(lattice, [[1, 0], [0, 1]], [0, 0])
    }

    /// Lattice family of both the source and destination coordinates.
    pub const fn lattice(self) -> LatticeKind {
        self.lattice
    }

    /// Row-major 2x2 integer linear part.
    pub const fn matrix(self) -> [[i32; 2]; 2] {
        self.matrix
    }

    /// Destination-frame translation applied after the linear part.
    pub const fn translation(self) -> [i32; 2] {
        self.translation
    }

    /// Return this transform with a replacement destination-frame translation.
    pub const fn with_translation(self, translation: [i32; 2]) -> Self {
        Self {
            translation,
            ..self
        }
    }

    /// Apply this transform to a coordinate.
    pub fn apply(self, coord: Coord) -> Coord {
        Coord {
            u: self.matrix[0][0] * coord.u + self.matrix[0][1] * coord.v + self.translation[0],
            v: self.matrix[1][0] * coord.u + self.matrix[1][1] * coord.v + self.translation[1],
        }
    }

    /// Determinant of the linear part.
    pub const fn determinant(self) -> i32 {
        self.matrix[0][0] * self.matrix[1][1] - self.matrix[0][1] * self.matrix[1][0]
    }

    /// Invert this transform when its linear part is unimodular
    /// (`determinant == ±1`).
    ///
    /// Returns `None` for a non-bijective integer transform. The inverse maps
    /// destination-frame coordinates back into the original source frame.
    pub fn inverse(self) -> Option<Self> {
        let det = self.determinant();
        if det != 1 && det != -1 {
            return None;
        }
        let matrix = [
            [self.matrix[1][1] / det, -self.matrix[0][1] / det],
            [-self.matrix[1][0] / det, self.matrix[0][0] / det],
        ];
        let translation = [
            -(matrix[0][0] * self.translation[0] + matrix[0][1] * self.translation[1]),
            -(matrix[1][0] * self.translation[0] + matrix[1][1] * self.translation[1]),
        ];
        Some(Self::new(self.lattice, matrix, translation))
    }
}

/// Four cardinal neighbour offsets on a square grid.
pub const SQUARE_CARDINAL_OFFSETS: [Coord; 4] = square::SQUARE_CARDINAL_OFFSETS;

/// Six axial neighbour offsets on a hex grid.
pub const HEX_AXIAL_OFFSETS: [Coord; 6] = hex::HEX_AXIAL_OFFSETS;

/// Dihedral group D4 acting on square lattice coordinates.
pub const D4_TRANSFORMS: [GridTransform; 8] = square::D4_TRANSFORMS;

/// Dihedral group D6 acting on hex axial coordinates.
pub const D6_TRANSFORMS: [GridTransform; 12] = hex::D6_TRANSFORMS;

#[cfg(test)]
mod tests {
    use std::collections::HashSet;

    use super::*;

    #[test]
    fn square_model_mapping_is_cartesian() {
        let p = LatticeKind::Square.model_point(Coord::new(2, -3));
        assert_eq!(p, Point2::new(2.0, -3.0));
    }

    #[test]
    fn hex_model_mapping_is_axial() {
        let p = LatticeKind::Hex.model_point(Coord::new(1, 2));
        assert!((p.x - 2.0).abs() < 1e-6);
        assert!((p.y - 3.0_f32.sqrt()).abs() < 1e-6);
    }

    #[test]
    fn kind_dispatch_matches_trait_impls() {
        let c = Coord::new(3, -1);
        assert_eq!(LatticeKind::Square.model_point(c), Square.model_point(c));
        assert_eq!(LatticeKind::Hex.model_point(c), Hex.model_point(c));
        assert_eq!(
            LatticeKind::Square.neighbour_offsets(),
            Square.neighbour_offsets()
        );
        assert_eq!(
            LatticeKind::Square.symmetry_transforms().len(),
            D4_TRANSFORMS.len()
        );
        assert_eq!(
            LatticeKind::Hex.symmetry_transforms().len(),
            D6_TRANSFORMS.len()
        );
    }

    #[test]
    fn d4_table_is_complete() {
        let set: HashSet<_> = D4_TRANSFORMS.iter().map(|t| t.matrix()).collect();
        assert_eq!(set.len(), 8);
        assert!(D4_TRANSFORMS
            .iter()
            .all(|t| t.lattice() == LatticeKind::Square && t.determinant().abs() == 1));
    }

    #[test]
    fn affine_inverse_round_trips_coordinates() {
        let transform = D4_TRANSFORMS[3].with_translation([7, -11]);
        let inverse = transform.inverse().expect("D4 transform is unimodular");
        let source = Coord::new(-5, 13);
        assert_eq!(inverse.apply(transform.apply(source)), source);
        assert_eq!(transform.apply(inverse.apply(source)), source);
        assert_eq!(inverse.lattice(), LatticeKind::Square);
    }

    #[test]
    fn non_unimodular_transform_has_no_integer_inverse() {
        let transform = GridTransform::new(LatticeKind::Square, [[2, 0], [0, 1]], [0, 0]);
        assert_eq!(transform.inverse(), None);
    }

    #[test]
    fn affine_transform_has_one_canonical_serde_shape() {
        let transform = D4_TRANSFORMS[1].with_translation([3, -4]);
        let json = serde_json::to_value(transform).expect("serialize transform");
        assert_eq!(
            json,
            serde_json::json!({
                "lattice": "square",
                "matrix": [[0, -1], [1, 0]],
                "translation": [3, -4]
            })
        );
        assert_eq!(
            serde_json::from_value::<GridTransform>(json).expect("deserialize transform"),
            transform
        );
    }

    #[test]
    fn axis_family_counts() {
        assert_eq!(LatticeKind::Square.axis_family_count(), 2);
        assert_eq!(LatticeKind::Hex.axis_family_count(), 3);
    }

    #[test]
    fn cell_topology_by_family() {
        assert_eq!(
            LatticeKind::Square.cell_topology(),
            CellTopology::TrianglePairToQuad
        );
        assert_eq!(
            LatticeKind::Hex.cell_topology(),
            CellTopology::TriangleIsCell
        );
    }

    #[test]
    fn model_axis_directions_are_unit_and_match_offsets() {
        // Square: the two axis directions are the +u/+v unit vectors.
        let sq = LatticeKind::Square.model_axis_directions();
        assert_eq!(sq.len(), 2);
        for v in sq {
            assert!((v.norm() - 1.0).abs() < 1e-6);
        }
        // Hex: three unit directions at 0°, 60°, 120° (mod π).
        let hx = LatticeKind::Hex.model_axis_directions();
        assert_eq!(hx.len(), 3);
        for v in hx {
            assert!((v.norm() - 1.0).abs() < 1e-6);
        }
        // The first hex axis direction must equal the folded model direction
        // of the (1,0) axial offset.
        let d_q = LatticeKind::Hex.model_point(Coord::new(1, 0))
            - LatticeKind::Hex.model_point(Coord::new(0, 0));
        let ang_offset = d_q.y.atan2(d_q.x);
        let ang_dir = hx[0].y.atan2(hx[0].x);
        let diff = (ang_offset - ang_dir).abs() % std::f32::consts::PI;
        assert!(diff < 1e-5 || (std::f32::consts::PI - diff) < 1e-5);
    }

    #[test]
    fn d6_table_is_complete() {
        let set: HashSet<_> = D6_TRANSFORMS.iter().map(|t| t.matrix()).collect();
        assert_eq!(set.len(), 12);
        assert!(D6_TRANSFORMS
            .iter()
            .all(|t| t.lattice() == LatticeKind::Hex && t.determinant().abs() == 1));
    }
}