Skip to main content

ternary_contours/
grid.rs

1#[cfg(test)]
2use std::collections::BTreeSet;
3
4use crate::{FieldError, GridEvaluationError};
5
6/// Stable identifier in the field's canonical value ordering.
7#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
8pub struct GridVertexId(pub usize);
9
10/// Integer ternary lattice coordinate satisfying `i+j+k=n`.
11#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
12pub struct LatticeCoordinate {
13    pub i: usize,
14    pub j: usize,
15    pub k: usize,
16}
17
18/// A reusable view of the canonical regular ternary composition lattice.
19///
20/// The grid visits lattice coordinates in the exact order used by
21/// RegularTernaryScalarField: i increases first, then j, with
22/// k = subdivisions - i - j. Its iterators are lazy and do not allocate.
23///
24/// Example:
25///
26///     use ternary_contours::{LatticeCoordinate, RegularTernaryGrid};
27///
28///     let grid = RegularTernaryGrid::new(2)?;
29///     let coordinates: Vec<_> = grid.lattice_coordinates().collect();
30///     assert_eq!(coordinates[0], LatticeCoordinate { i: 0, j: 0, k: 2 });
31///     # Ok::<(), ternary_contours::FieldError>(())
32#[derive(Clone, Copy, Debug, Eq, PartialEq)]
33pub struct RegularTernaryGrid {
34    subdivisions: usize,
35    vertex_count: usize,
36}
37
38impl RegularTernaryGrid {
39    /// Create a regular ternary lattice with subdivisions intervals per edge.
40    ///
41    /// The subdivision count must be positive. Its vertex count is
42    /// (n + 1) * (n + 2) / 2 and is checked for overflow.
43    pub fn new(subdivisions: usize) -> Result<Self, FieldError> {
44        if subdivisions == 0 {
45            return Err(FieldError::ZeroSubdivisions);
46        }
47        Ok(Self {
48            subdivisions,
49            vertex_count: canonical_vertex_count(subdivisions)?,
50        })
51    }
52
53    /// Number of intervals on each binary edge.
54    pub const fn subdivisions(&self) -> usize {
55        self.subdivisions
56    }
57
58    /// Number of vertices in canonical scalar-field order.
59    pub const fn vertex_count(&self) -> usize {
60        self.vertex_count
61    }
62
63    /// Lazily iterate canonical integer lattice coordinates.
64    ///
65    /// The iterator is exact-sized and yields i = 0..=n, j = 0..=n-i,
66    /// and k = n-i-j.
67    pub fn lattice_coordinates(&self) -> impl ExactSizeIterator<Item = LatticeCoordinate> + Clone {
68        CanonicalLatticeCoordinates {
69            subdivisions: self.subdivisions,
70            i: 0,
71            j: 0,
72            remaining: self.vertex_count,
73        }
74    }
75
76    /// Lazily iterate normalized semantic compositions in canonical field order.
77    ///
78    /// Each item is [i/n, j/n, k/n] in A/B/C component order.
79    ///
80    /// Example:
81    ///
82    ///     use ternary_contours::RegularTernaryGrid;
83    ///
84    ///     let grid = RegularTernaryGrid::new(2)?;
85    ///     assert_eq!(grid.compositions().next(), Some([0.0, 0.0, 1.0]));
86    ///     # Ok::<(), ternary_contours::FieldError>(())
87    pub fn compositions(&self) -> impl ExactSizeIterator<Item = [f64; 3]> + Clone {
88        let denominator = self.subdivisions as f64;
89        self.lattice_coordinates()
90            .map(move |coordinate| composition_from_coordinate(coordinate, denominator))
91    }
92
93    /// Lazily iterate scalar-field vertex identifiers and normalized compositions.
94    ///
95    /// Every identifier matches the canonical order expected by
96    /// RegularTernaryScalarField::new.
97    pub fn indexed_compositions(
98        &self,
99    ) -> impl ExactSizeIterator<Item = (GridVertexId, [f64; 3])> + Clone {
100        self.compositions()
101            .enumerate()
102            .map(|(index, composition)| (GridVertexId(index), composition))
103    }
104}
105
106#[derive(Clone, Debug)]
107struct CanonicalLatticeCoordinates {
108    subdivisions: usize,
109    i: usize,
110    j: usize,
111    remaining: usize,
112}
113
114impl Iterator for CanonicalLatticeCoordinates {
115    type Item = LatticeCoordinate;
116
117    fn next(&mut self) -> Option<Self::Item> {
118        if self.remaining == 0 {
119            return None;
120        }
121
122        let coordinate = LatticeCoordinate {
123            i: self.i,
124            j: self.j,
125            k: self.subdivisions - self.i - self.j,
126        };
127        self.remaining -= 1;
128
129        if self.j == self.subdivisions - self.i {
130            self.i += 1;
131            self.j = 0;
132        } else {
133            self.j += 1;
134        }
135
136        Some(coordinate)
137    }
138
139    fn size_hint(&self) -> (usize, Option<usize>) {
140        (self.remaining, Some(self.remaining))
141    }
142}
143
144impl ExactSizeIterator for CanonicalLatticeCoordinates {}
145
146/// A scalar field sampled on the regular ternary lattice `i+j+k=n`.
147///
148/// Values use row-major `(i,j)` ordering: `i` increases from zero to `n`, and
149/// for each `i`, `j` increases from zero to `n-i`; `k=n-i-j`.
150#[derive(Clone, Debug, PartialEq)]
151pub struct RegularTernaryScalarField {
152    subdivisions: usize,
153    values: Vec<f64>,
154}
155
156#[derive(Clone, Copy, Debug, Eq, PartialEq)]
157pub struct GridTriangle {
158    pub id: usize,
159    pub vertices: [GridVertexId; 3],
160}
161
162#[cfg(feature = "cubic-alpha")]
163#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
164pub(crate) struct GridEdgeKey {
165    pub start: GridVertexId,
166    pub end: GridVertexId,
167}
168
169#[cfg(feature = "cubic-alpha")]
170impl GridEdgeKey {
171    pub const fn new(left: GridVertexId, right: GridVertexId) -> Self {
172        if left.0 < right.0 {
173            Self {
174                start: left,
175                end: right,
176            }
177        } else {
178            Self {
179                start: right,
180                end: left,
181            }
182        }
183    }
184}
185
186impl RegularTernaryScalarField {
187    /// Construct a field by evaluating one scalar value at every canonical grid
188    /// composition.
189    ///
190    /// The callback receives normalized [a, b, c] compositions in the same
191    /// order as RegularTernaryGrid::compositions. The produced values are
192    /// validated exactly as they are by Self::new.
193    ///
194    /// Example:
195    ///
196    ///     use ternary_contours::RegularTernaryScalarField;
197    ///
198    ///     let field = RegularTernaryScalarField::from_fn(2, |[a, b, c]| {
199    ///         2.0 * a - 3.0 * b + 5.0 * c
200    ///     })?;
201    ///     assert_eq!(field.vertex_count(), 6);
202    ///     # Ok::<(), ternary_contours::FieldError>(())
203    pub fn from_fn<F>(subdivisions: usize, value_at: F) -> Result<Self, FieldError>
204    where
205        F: FnMut([f64; 3]) -> f64,
206    {
207        let grid = RegularTernaryGrid::new(subdivisions)?;
208        let values = grid.compositions().map(value_at).collect();
209        Self::new(subdivisions, values)
210    }
211
212    /// Fallibly construct a field by evaluating canonical grid compositions.
213    ///
214    /// Callback failures retain their source error, stable vertex identifier,
215    /// and normalized composition in GridEvaluationError::Evaluation. Grid and
216    /// field validation failures are returned as GridEvaluationError::Grid.
217    ///
218    /// Example:
219    ///
220    ///     use ternary_contours::{
221    ///         GridEvaluationError, GridVertexId, RegularTernaryScalarField,
222    ///     };
223    ///
224    ///     let error = RegularTernaryScalarField::try_from_fn(2, |composition| {
225    ///         if composition == [0.0, 0.5, 0.5] {
226    ///             Err("sample unavailable")
227    ///         } else {
228    ///             Ok(composition[0])
229    ///         }
230    ///     })
231    ///     .unwrap_err();
232    ///     assert!(matches!(
233    ///         error,
234    ///         GridEvaluationError::Evaluation {
235    ///             index: GridVertexId(1),
236    ///             source: "sample unavailable",
237    ///             ..
238    ///         }
239    ///     ));
240    pub fn try_from_fn<F, E>(
241        subdivisions: usize,
242        mut value_at: F,
243    ) -> Result<Self, GridEvaluationError<E>>
244    where
245        F: FnMut([f64; 3]) -> Result<f64, E>,
246    {
247        let grid = RegularTernaryGrid::new(subdivisions).map_err(GridEvaluationError::Grid)?;
248        let mut values = Vec::with_capacity(grid.vertex_count());
249        for (index, composition) in grid.indexed_compositions() {
250            let value =
251                value_at(composition).map_err(|source| GridEvaluationError::Evaluation {
252                    index,
253                    composition,
254                    source,
255                })?;
256            values.push(value);
257        }
258        Self::new(subdivisions, values).map_err(GridEvaluationError::Grid)
259    }
260
261    pub fn new(subdivisions: usize, values: Vec<f64>) -> Result<Self, FieldError> {
262        if subdivisions == 0 {
263            return Err(FieldError::ZeroSubdivisions);
264        }
265        let expected = canonical_vertex_count(subdivisions)?;
266        if values.len() != expected {
267            return Err(FieldError::IncorrectValueCount {
268                expected,
269                actual: values.len(),
270            });
271        }
272        if let Some((index, value)) = values
273            .iter()
274            .copied()
275            .enumerate()
276            .find(|(_, value)| !value.is_finite())
277        {
278            return Err(FieldError::NonFiniteValue { index, value });
279        }
280        Ok(Self {
281            subdivisions,
282            values,
283        })
284    }
285
286    pub const fn subdivisions(&self) -> usize {
287        self.subdivisions
288    }
289    pub fn values(&self) -> &[f64] {
290        &self.values
291    }
292    pub const fn vertex_count(&self) -> usize {
293        self.values.len()
294    }
295    pub fn triangle_count(&self) -> Result<usize, FieldError> {
296        self.subdivisions
297            .checked_mul(self.subdivisions)
298            .ok_or(FieldError::AllocationOverflow)
299    }
300    pub fn edge_count(&self) -> Result<usize, FieldError> {
301        self.subdivisions
302            .checked_mul(self.subdivisions + 1)
303            .and_then(|value| value.checked_mul(3))
304            .map(|value| value / 2)
305            .ok_or(FieldError::AllocationOverflow)
306    }
307
308    pub fn value(&self, id: GridVertexId) -> Result<f64, FieldError> {
309        self.values
310            .get(id.0)
311            .copied()
312            .ok_or(FieldError::InvalidVertexIndex {
313                index: id.0,
314                vertex_count: self.values.len(),
315            })
316    }
317
318    pub fn vertex_id(&self, coordinate: LatticeCoordinate) -> Result<GridVertexId, FieldError> {
319        if coordinate
320            .i
321            .checked_add(coordinate.j)
322            .and_then(|v| v.checked_add(coordinate.k))
323            != Some(self.subdivisions)
324        {
325            return Err(FieldError::InvalidLatticeCoordinate {
326                i: coordinate.i,
327                j: coordinate.j,
328                k: coordinate.k,
329                subdivisions: self.subdivisions,
330            });
331        }
332        let i = coordinate.i;
333        let prefix = i
334            .checked_mul(self.subdivisions + 1)
335            .and_then(|v| i.checked_mul(i.saturating_sub(1)).map(|tri| v - tri / 2))
336            .ok_or(FieldError::AllocationOverflow)?;
337        Ok(GridVertexId(prefix + coordinate.j))
338    }
339
340    pub fn lattice_coordinate(&self, id: GridVertexId) -> Result<LatticeCoordinate, FieldError> {
341        if id.0 >= self.values.len() {
342            return Err(FieldError::InvalidVertexIndex {
343                index: id.0,
344                vertex_count: self.values.len(),
345            });
346        }
347        let mut offset = 0;
348        for i in 0..=self.subdivisions {
349            let row = self.subdivisions - i + 1;
350            if id.0 < offset + row {
351                let j = id.0 - offset;
352                return Ok(LatticeCoordinate {
353                    i,
354                    j,
355                    k: self.subdivisions - i - j,
356                });
357            }
358            offset += row;
359        }
360        unreachable!("validated vertex id must occur in one row")
361    }
362
363    pub fn composition(&self, id: GridVertexId) -> Result<[f64; 3], FieldError> {
364        let coordinate = self.lattice_coordinate(id)?;
365        Ok(composition_from_coordinate(
366            coordinate,
367            self.subdivisions as f64,
368        ))
369    }
370
371    pub fn index_of(&self, i: usize, j: usize, k: usize) -> Result<usize, FieldError> {
372        Ok(self.vertex_id(LatticeCoordinate { i, j, k })?.0)
373    }
374
375    pub fn coordinate_of(&self, index: usize) -> Result<LatticeCoordinate, FieldError> {
376        self.lattice_coordinate(GridVertexId(index))
377    }
378
379    pub fn composition_at(&self, index: usize) -> Result<[f64; 3], FieldError> {
380        self.composition(GridVertexId(index))
381    }
382
383    pub fn elementary_triangles(&self) -> Result<Vec<GridTriangle>, FieldError> {
384        let capacity = self.triangle_count()?;
385        let mut triangles = Vec::with_capacity(capacity);
386        for i in 0..self.subdivisions {
387            for j in 0..(self.subdivisions - i) {
388                let k = self.subdivisions - i - j;
389                let p = self.vertex_id(LatticeCoordinate { i, j, k })?;
390                let q = self.vertex_id(LatticeCoordinate {
391                    i: i + 1,
392                    j,
393                    k: k - 1,
394                })?;
395                let r = self.vertex_id(LatticeCoordinate {
396                    i,
397                    j: j + 1,
398                    k: k - 1,
399                })?;
400                triangles.push(GridTriangle {
401                    id: triangles.len(),
402                    vertices: [p, q, r],
403                });
404                if k >= 2 {
405                    let s = self.vertex_id(LatticeCoordinate {
406                        i: i + 1,
407                        j: j + 1,
408                        k: k - 2,
409                    })?;
410                    triangles.push(GridTriangle {
411                        id: triangles.len(),
412                        vertices: [q, s, r],
413                    });
414                }
415            }
416        }
417        debug_assert_eq!(triangles.len(), capacity);
418        Ok(triangles)
419    }
420
421    #[cfg(test)]
422    pub(crate) fn unique_edges(
423        &self,
424    ) -> Result<BTreeSet<(GridVertexId, GridVertexId)>, FieldError> {
425        let mut edges = BTreeSet::new();
426        for triangle in self.elementary_triangles()? {
427            for [left, right] in [[0, 1], [1, 2], [2, 0]] {
428                let a = triangle.vertices[left];
429                let b = triangle.vertices[right];
430                edges.insert(if a < b { (a, b) } else { (b, a) });
431            }
432        }
433        Ok(edges)
434    }
435}
436
437fn canonical_vertex_count(subdivisions: usize) -> Result<usize, FieldError> {
438    subdivisions
439        .checked_add(1)
440        .and_then(|left| {
441            subdivisions
442                .checked_add(2)
443                .and_then(|right| left.checked_mul(right))
444        })
445        .map(|value| value / 2)
446        .ok_or(FieldError::AllocationOverflow)
447}
448
449fn composition_from_coordinate(coordinate: LatticeCoordinate, denominator: f64) -> [f64; 3] {
450    [
451        coordinate.i as f64 / denominator,
452        coordinate.j as f64 / denominator,
453        coordinate.k as f64 / denominator,
454    ]
455}
456
457#[cfg(test)]
458mod tests {
459    use super::*;
460
461    fn field(n: usize) -> RegularTernaryScalarField {
462        let count = (n + 1) * (n + 2) / 2;
463        RegularTernaryScalarField::new(n, (0..count).map(|value| value as f64).collect()).unwrap()
464    }
465
466    fn requires_exact_size<I: ExactSizeIterator>(_iterator: I) {}
467
468    #[test]
469    fn grid_iterators_match_field_order_and_accessors() {
470        for subdivisions in [1, 2, 3, 5] {
471            let grid = RegularTernaryGrid::new(subdivisions).unwrap();
472            assert_eq!(grid.subdivisions(), subdivisions);
473            assert_eq!(
474                grid.vertex_count(),
475                (subdivisions + 1) * (subdivisions + 2) / 2
476            );
477            requires_exact_size(grid.lattice_coordinates());
478            requires_exact_size(grid.compositions());
479            requires_exact_size(grid.indexed_compositions());
480
481            let mut coordinates = grid.lattice_coordinates();
482            assert_eq!(coordinates.len(), grid.vertex_count());
483            let first = coordinates.next().unwrap();
484            assert_eq!(
485                first,
486                LatticeCoordinate {
487                    i: 0,
488                    j: 0,
489                    k: subdivisions
490                }
491            );
492            assert_eq!(coordinates.len(), grid.vertex_count() - 1);
493
494            let expected_coordinates: Vec<_> = (0..=subdivisions)
495                .flat_map(|i| {
496                    (0..=subdivisions - i).map(move |j| LatticeCoordinate {
497                        i,
498                        j,
499                        k: subdivisions - i - j,
500                    })
501                })
502                .collect();
503            assert_eq!(
504                grid.lattice_coordinates().collect::<Vec<_>>(),
505                expected_coordinates
506            );
507
508            let values: Vec<_> = grid
509                .compositions()
510                .map(|[a, b, c]| 2.0 * a - 3.0 * b + 5.0 * c)
511                .collect();
512            let field = RegularTernaryScalarField::new(subdivisions, values.clone()).unwrap();
513            assert_eq!(field.vertex_count(), grid.vertex_count());
514
515            for ((id, composition), coordinate) in
516                grid.indexed_compositions().zip(grid.lattice_coordinates())
517            {
518                let index = id.0;
519                assert_eq!(
520                    field
521                        .index_of(coordinate.i, coordinate.j, coordinate.k)
522                        .unwrap(),
523                    index
524                );
525                assert_eq!(field.coordinate_of(index).unwrap(), coordinate);
526                assert_eq!(field.composition_at(index).unwrap(), composition);
527                assert_eq!(
528                    composition,
529                    [
530                        coordinate.i as f64 / subdivisions as f64,
531                        coordinate.j as f64 / subdivisions as f64,
532                        coordinate.k as f64 / subdivisions as f64,
533                    ]
534                );
535            }
536
537            let generated = RegularTernaryScalarField::from_fn(subdivisions, |[a, b, c]| {
538                2.0 * a - 3.0 * b + 5.0 * c
539            })
540            .unwrap();
541            assert_eq!(generated.values(), values);
542
543            let fallible = RegularTernaryScalarField::try_from_fn(subdivisions, |[a, b, c]| {
544                Ok::<f64, &'static str>(2.0 * a - 3.0 * b + 5.0 * c)
545            })
546            .unwrap();
547            assert_eq!(fallible, generated);
548        }
549    }
550
551    #[test]
552    fn grid_and_function_constructors_preserve_typed_errors() {
553        assert!(matches!(
554            RegularTernaryGrid::new(0),
555            Err(FieldError::ZeroSubdivisions)
556        ));
557        assert!(matches!(
558            RegularTernaryScalarField::from_fn(0, |_| 0.0),
559            Err(FieldError::ZeroSubdivisions)
560        ));
561        assert!(matches!(
562            RegularTernaryScalarField::try_from_fn(0, |_| Ok::<f64, &'static str>(0.0)),
563            Err(GridEvaluationError::Grid(FieldError::ZeroSubdivisions))
564        ));
565        assert!(matches!(
566            RegularTernaryScalarField::from_fn(2, |_| f64::NAN),
567            Err(FieldError::NonFiniteValue { index: 0, .. })
568        ));
569        assert!(matches!(
570            RegularTernaryScalarField::try_from_fn(2, |_| { Ok::<f64, &'static str>(f64::NAN) }),
571            Err(GridEvaluationError::Grid(FieldError::NonFiniteValue {
572                index: 0,
573                ..
574            }))
575        ));
576    }
577
578    #[test]
579    fn fallible_evaluation_preserves_source_vertex_and_composition() {
580        #[derive(Debug, PartialEq)]
581        struct SampleUnavailable {
582            reason: &'static str,
583        }
584
585        let mut calls = 0;
586        let error = RegularTernaryScalarField::try_from_fn(3, |composition| {
587            let index = calls;
588            calls += 1;
589            if index == 2 {
590                Err(SampleUnavailable {
591                    reason: "missing sample",
592                })
593            } else {
594                Ok(composition[0] + composition[1])
595            }
596        })
597        .unwrap_err();
598
599        assert_eq!(calls, 3);
600        assert_eq!(
601            error,
602            GridEvaluationError::Evaluation {
603                index: GridVertexId(2),
604                composition: [0.0, 2.0 / 3.0, 1.0 / 3.0],
605                source: SampleUnavailable {
606                    reason: "missing sample",
607                },
608            }
609        );
610    }
611
612    #[test]
613    fn canonical_order_and_index_round_trips_are_stable() {
614        let field = field(4);
615        assert_eq!(field.vertex_count(), 15);
616        let expected = [
617            (0, 0, 4),
618            (0, 1, 3),
619            (0, 2, 2),
620            (0, 3, 1),
621            (0, 4, 0),
622            (1, 0, 3),
623            (1, 1, 2),
624            (1, 2, 1),
625            (1, 3, 0),
626            (2, 0, 2),
627            (2, 1, 1),
628            (2, 2, 0),
629            (3, 0, 1),
630            (3, 1, 0),
631            (4, 0, 0),
632        ];
633        for (index, &(i, j, k)) in expected.iter().enumerate() {
634            assert_eq!(
635                field.coordinate_of(index).unwrap(),
636                LatticeCoordinate { i, j, k }
637            );
638            assert_eq!(field.index_of(i, j, k).unwrap(), index);
639            let point = field.composition_at(index).unwrap();
640            assert!((point.into_iter().sum::<f64>() - 1.0).abs() < 1.0e-12);
641        }
642    }
643
644    #[test]
645    fn triangle_and_unique_edge_counts_match_regular_lattice_formulae() {
646        for n in 1..=12 {
647            let field = field(n);
648            assert_eq!(field.elementary_triangles().unwrap().len(), n * n);
649            assert_eq!(field.unique_edges().unwrap().len(), 3 * n * (n + 1) / 2);
650            assert_eq!(field.edge_count().unwrap(), 3 * n * (n + 1) / 2);
651        }
652    }
653
654    #[test]
655    fn construction_rejects_invalid_sizes_values_and_overflow() {
656        assert!(matches!(
657            RegularTernaryScalarField::new(0, vec![]),
658            Err(FieldError::ZeroSubdivisions)
659        ));
660        assert!(matches!(
661            RegularTernaryScalarField::new(2, vec![0.0; 5]),
662            Err(FieldError::IncorrectValueCount {
663                expected: 6,
664                actual: 5
665            })
666        ));
667        let mut values = vec![0.0; 6];
668        values[3] = f64::NAN;
669        assert!(matches!(
670            RegularTernaryScalarField::new(2, values),
671            Err(FieldError::NonFiniteValue { index: 3, .. })
672        ));
673        assert!(matches!(
674            RegularTernaryScalarField::new(usize::MAX, Vec::new()),
675            Err(FieldError::AllocationOverflow)
676        ));
677    }
678}