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 square;

pub use hex::Hex;
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 ([`crate::topological`] `quads.rs`).
/// * 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 }
    }
}

/// Optional known grid dimensions.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub struct GridDimensions {
    /// Number of cells or feature positions along the first lattice axis.
    pub width: usize,
    /// Number of cells or feature positions along the second lattice axis.
    pub height: usize,
}

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

/// Supported lattice families.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
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`] (e.g. `shared::fit`,
    /// [`crate::check`]) 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;
}

/// A lattice-coordinate symmetry transform: `out = matrix * coord + offset`.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub struct GridTransform {
    /// Lattice family this transform belongs to.
    pub source_kind: LatticeKind,
    /// Row-major 2x2 integer linear part.
    pub matrix: [[i32; 2]; 2],
    /// Integer offset applied after the linear part.
    pub offset: [i32; 2],
}

impl GridTransform {
    /// Construct a lattice transform from raw components.
    pub const fn new(source_kind: LatticeKind, matrix: [[i32; 2]; 2], offset: [i32; 2]) -> Self {
        Self {
            source_kind,
            matrix,
            offset,
        }
    }

    /// 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.offset[0],
            v: self.matrix[1][0] * coord.u + self.matrix[1][1] * coord.v + self.offset[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]
    }
}

/// 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.source_kind == LatticeKind::Square && t.determinant().abs() == 1));
    }

    #[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.source_kind == LatticeKind::Hex && t.determinant().abs() == 1));
    }
}