projective-grid

Generic 2D projective grid graph construction, traversal, and homography tools for square and hexagonal grids.

This crate provides reusable algorithms for building grid graphs from detected 2D corners, assigning grid coordinates via BFS traversal, and computing projective mappings (homographies) for grid rectification. It supports both 4-connected square grids and 6-connected hexagonal grids (pointy-top, axial coordinates). It is pattern-agnostic and has no dependency on image types or calibration-specific logic.

Quickstart

Square grid

use projective_grid::{
    GridGraph, GridGraphParams, GridIndex, NeighborCandidate, NeighborDirection,
    NeighborValidator,
};
use nalgebra::Point2;

/// Trivial validator: accepts any neighbor within range, classifies by quadrant.
struct QuadrantValidator;

impl NeighborValidator for QuadrantValidator {
    type PointData = ();

    fn validate(
        &self,
        _source_index: usize,
        _source_data: &(),
        candidate: &NeighborCandidate,
        _candidate_data: &(),
    ) -> Option<(NeighborDirection, f32)> {
        let dir = if candidate.offset.x.abs() > candidate.offset.y.abs() {
            if candidate.offset.x > 0.0 { NeighborDirection::Right }
            else { NeighborDirection::Left }
        } else {
            if candidate.offset.y > 0.0 { NeighborDirection::Down }
            else { NeighborDirection::Up }
        };
        Some((dir, candidate.distance))
    }
}

fn main() {
    let positions = vec![
        Point2::new(0.0f32, 0.0), Point2::new(10.0, 0.0),
        Point2::new(0.0, 10.0),   Point2::new(10.0, 10.0),
    ];
    let data = vec![(); 4];

    let graph = GridGraph::build(
        &positions, &data, &QuadrantValidator, &GridGraphParams::default(),
    );

    let components = projective_grid::connected_components(&graph);
    assert_eq!(components.len(), 1);

    let coords = projective_grid::assign_grid_coordinates(&graph, &components[0]);
    println!("assigned {} grid coordinates", coords.len());
}

Hex grid

use projective_grid::hex::{
    HexDirection, HexGridGraph, HexNeighborValidator, HexNodeNeighbor,
    hex_connected_components, hex_assign_grid_coordinates,
};
use projective_grid::{GridGraphParams, NeighborCandidate};
use nalgebra::Point2;

/// Classify neighbors into hex sextants by angle.
struct SextantValidator;

impl HexNeighborValidator for SextantValidator {
    type PointData = ();

    fn validate(
        &self,
        _source_index: usize,
        _source_data: &(),
        candidate: &NeighborCandidate,
        _candidate_data: &(),
    ) -> Option<(HexDirection, f32)> {
        let deg = candidate.offset.y.atan2(candidate.offset.x).to_degrees();
        let dir = if (-30.0..30.0).contains(&deg) { HexDirection::East }
            else if (30.0..90.0).contains(&deg) { HexDirection::SouthEast }
            else if (90.0..150.0).contains(&deg) { HexDirection::SouthWest }
            else if !(-150.0..150.0).contains(&deg) { HexDirection::West }
            else if (-150.0..-90.0).contains(&deg) { HexDirection::NorthWest }
            else { HexDirection::NorthEast };
        Some((dir, candidate.distance))
    }
}

fn main() {
    // Build a small hex lattice (pointy-top, axial coordinates)
    let spacing = 10.0f32;
    let sqrt3 = 3.0f32.sqrt();
    let mut positions = Vec::new();
    for q in -1..=1i32 {
        for r in -1..=1i32 {
            if (q + r).abs() > 1 { continue; }
            let x = spacing * (q as f32 + r as f32 * 0.5);
            let y = spacing * (r as f32 * sqrt3 / 2.0);
            positions.push(Point2::new(x, y));
        }
    }
    let data = vec![(); positions.len()];

    let graph = HexGridGraph::build(
        &positions, &data, &SextantValidator, &GridGraphParams::default(),
    );

    let components = hex_connected_components(&graph);
    let coords = hex_assign_grid_coordinates(&graph, &components[0]);
    println!("assigned {} hex grid coordinates", coords.len());
}

Modules

Square grid (4-connected)

Hexagonal grid (6-connected)

Shared

Design

The validator traits (NeighborValidator for square, HexNeighborValidator for hex) are the main extension points. Implementors decide which spatially close points qualify as grid neighbors and assign them a direction and quality score. This lets the same graph construction algorithm work for chessboards (orientation-based validation), ChArUco grids (marker-anchored validation), ring calibration targets on hex lattices, or any other 2D grid pattern.

Hex coordinate convention

Hex grids use pointy-top orientation with axial coordinates (q, r), stored in GridIndex as i = q, j = r:

• q increases eastward
• r increases south-eastward
• Six directions: E (+1, 0), W (-1, 0), NE (+1, -1), SW (-1, +1), NW (0, -1), SE (0, +1)
• Rectified mapping: x = s * (q + r/2), y = s * (r * sqrt(3)/2) where s = pixels per cell

Hex mesh triangulation

The hex mesh (HexGridHomographyMesh) decomposes the axial grid into parallelogram cells, each split into two triangles. Each triangle stores both an AffineTransform2D (exact 3-point mapping) and a Homography (4-point, using the centroid), giving callers the choice between speed and projective accuracy.

The crate is standalone: it depends only on nalgebra, kiddo, serde, and thiserror. No image types, no calibration-specific logic.

Features

• tracing: enables tracing instrumentation (currently reserved for future use).

Links

• Repository: https://github.com/VitalyVorobyev/calib-targets-rs