# projective-grid
[](https://docs.rs/projective-grid)
[](https://crates.io/crates/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
| `Positions` | ✅ (synthesize 2 axes) | ✅ (synthesize 3 axes, topological) |
| `Oriented1` | ✅ (synthesize 2nd axis) | ✅ (keep measured family, synthesize 2) |
| `Oriented2` | ✅ (native, topological) | ❌ `UnsupportedCombination` |
| `Oriented3` | ❌ `UnsupportedCombination` | ✅ (native, topological) |
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`](examples/hello_grid.rs) —
`cargo run -p projective-grid --example hello_grid`.)
```rust
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:
| `grid()` | Canonically ordered labelled features. Each [`GridEntry`] carries `coord`, `source_index`, `image_position`, and its fit residual. |
| `fit()` | The mandatory model-plane-to-image projective transform plus `count`, `mean_px`, and `max_px`. |
## Learn more
Algorithm deep-dive and conceptual background:
[book chapter](https://vitalyvorobyev.github.io/calib-targets-rs/projective_grid.html).
Release posture and remaining stabilization work: [road to 1.0](ROADMAP-1.0.md).
Version history and release notes: [changelog](CHANGELOG.md).
## License
Licensed under either of MIT or Apache-2.0 at your option.
[`PointFeature`]: https://docs.rs/projective-grid/latest/projective_grid/struct.PointFeature.html
[`OrientedFeature`]: https://docs.rs/projective-grid/latest/projective_grid/struct.OrientedFeature.html
[`LocalAxis`]: https://docs.rs/projective-grid/latest/projective_grid/struct.LocalAxis.html
[`Evidence`]: https://docs.rs/projective-grid/latest/projective_grid/enum.Evidence.html
[`Evidence::Positions`]: https://docs.rs/projective-grid/latest/projective_grid/enum.Evidence.html
[`Evidence::Oriented1`]: https://docs.rs/projective-grid/latest/projective_grid/enum.Evidence.html
[`Evidence::Oriented2`]: https://docs.rs/projective-grid/latest/projective_grid/enum.Evidence.html
[`detect_grid`]: https://docs.rs/projective-grid/latest/projective_grid/fn.detect_grid.html
[`detect_grid_all`]: https://docs.rs/projective-grid/latest/projective_grid/fn.detect_grid_all.html
[`check_consistency`]: https://docs.rs/projective-grid/latest/projective_grid/fn.check_consistency.html
[`GridDetection`]: https://docs.rs/projective-grid/latest/projective_grid/struct.GridDetection.html
[`GridEntry`]: https://docs.rs/projective-grid/latest/projective_grid/struct.GridEntry.html