Skip to main content

ternary_contours/contour/
bands.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use crate::{RegularTernaryScalarField, TernaryCoordinate};
4
5use super::{ContourError, ContourInterpolation};
6
7/// Backend-independent options for piecewise-linear filled contour bands.
8///
9/// Geometric rings use the same tolerance model as ContourOptions. Bands are
10/// numerically classified as lower-inclusive and upper-exclusive; unbounded
11/// extreme bands own their respective infinities. Polygon boundaries remain
12/// closed geometrically, so adjacent bands may share a boundary without
13/// overlapping in positive area.
14#[derive(Clone, Copy, Debug, PartialEq)]
15pub struct ContourBandOptions {
16    /// Interpolation used to construct the regions. Only linear interpolation
17    /// is currently supported.
18    pub interpolation: ContourInterpolation,
19    /// Finite positive scalar equality tolerance.
20    pub value_tolerance: f64,
21    /// Finite positive composition-space cleanup tolerance.
22    pub geometry_tolerance: f64,
23    /// Include the unbounded band below the first break.
24    pub include_lower_extreme: bool,
25    /// Include the unbounded band above the last break.
26    pub include_upper_extreme: bool,
27}
28
29impl ContourBandOptions {
30    /// Construct options for the always-available piecewise-linear band model.
31    pub const fn linear() -> Self {
32        Self {
33            interpolation: ContourInterpolation::Linear,
34            value_tolerance: 1.0e-10,
35            geometry_tolerance: 1.0e-8,
36            include_lower_extreme: true,
37            include_upper_extreme: true,
38        }
39    }
40
41    fn validate(self) -> Result<(), ContourError> {
42        if !self.value_tolerance.is_finite()
43            || self.value_tolerance <= 0.0
44            || !self.geometry_tolerance.is_finite()
45            || self.geometry_tolerance <= 0.0
46        {
47            return Err(ContourError::InvalidTolerance {
48                value_tolerance: self.value_tolerance,
49                geometry_tolerance: self.geometry_tolerance,
50            });
51        }
52        if !matches!(self.interpolation, ContourInterpolation::Linear) {
53            return Err(ContourError::UnsupportedFilledInterpolation);
54        }
55        Ok(())
56    }
57}
58
59impl Default for ContourBandOptions {
60    fn default() -> Self {
61        Self::linear()
62    }
63}
64
65/// One scalar interval of a ContourBandSet.
66///
67/// None is an unbounded end. The semantic ownership rule is lower-inclusive
68/// and upper-exclusive, with the unbounded upper band retaining its maximum
69/// boundary.
70#[derive(Clone, Debug, PartialEq)]
71pub struct ContourBand {
72    /// Inclusive lower scalar bound, or no lower bound.
73    pub lower: Option<f64>,
74    /// Exclusive upper scalar bound, or no upper bound.
75    pub upper: Option<f64>,
76    /// Deterministically ordered disconnected filled regions.
77    pub regions: Vec<ContourRegion>,
78    fragments: Vec<ContourFragment>,
79}
80
81impl ContourBand {
82    /// Return deterministic, non-overlapping simple fragments for this band.
83    ///
84    /// This representation is useful to render a band without painting its
85    /// holes: draw the fragments and leave all complementary geometry
86    /// untouched. It has the same positive-area coverage as Self::regions.
87    pub fn fragments(&self) -> &[ContourFragment] {
88        &self.fragments
89    }
90}
91
92/// One simple, open polygon fragment of a contour band.
93///
94/// Fragments are in canonical ternary composition coordinates. They have no
95/// holes and do not overlap each other in positive area.
96#[derive(Clone, Debug, PartialEq)]
97pub struct ContourFragment {
98    vertices: Vec<TernaryCoordinate>,
99}
100
101impl ContourFragment {
102    /// Return the open polygon ring. The final edge is implicit.
103    pub fn vertices(&self) -> &[TernaryCoordinate] {
104        &self.vertices
105    }
106}
107
108/// One connected filled-band region.
109///
110/// Rings are open: the final edge back to the first point is implicit.
111/// Exterior rings are counter-clockwise in semantic (a, b) coordinates;
112/// holes are clockwise.
113#[derive(Clone, Debug, PartialEq)]
114pub struct ContourRegion {
115    /// Counter-clockwise exterior ring in semantic A/B/C coordinates.
116    pub exterior: Vec<TernaryCoordinate>,
117    /// Clockwise interior hole rings.
118    pub holes: Vec<Vec<TernaryCoordinate>>,
119}
120
121impl ContourRegion {
122    /// Signed semantic area of this region, excluding holes.
123    pub fn area(&self) -> f64 {
124        ring_area(&self.exterior).abs()
125            - self
126                .holes
127                .iter()
128                .map(|ring| ring_area(ring).abs())
129                .sum::<f64>()
130    }
131}
132
133/// Complete deterministic piecewise-linear isoband geometry.
134#[derive(Clone, Debug, PartialEq)]
135pub struct ContourBandSet {
136    /// Bands in ascending scalar order.
137    pub bands: Vec<ContourBand>,
138}
139
140impl ContourBandSet {
141    /// Compute finite, ordered piecewise-linear scalar bands.
142    ///
143    /// Callers must supply finite, strictly increasing breaks. Semantic scalar
144    /// ownership is f < l0, li <= f < li+1, and f >= lm; closed polygon
145    /// boundaries may still be shared by adjacent bands without a positive-area
146    /// overlap. The field is clipped in composition space before rendering.
147    pub fn compute(
148        field: &RegularTernaryScalarField,
149        breaks: &[f64],
150        options: ContourBandOptions,
151    ) -> Result<Self, ContourError> {
152        options.validate()?;
153        let breaks = validated_breaks(breaks, options.value_tolerance)?;
154        let ranges = band_ranges(&breaks, options);
155        let triangles = field.elementary_triangles()?;
156        let mut bands = Vec::with_capacity(ranges.len());
157        for (lower, upper) in ranges {
158            let mut fragments = Vec::new();
159            for triangle in &triangles {
160                let mut polygon = triangle
161                    .vertices
162                    .map(|vertex| {
163                        Ok(BandVertex {
164                            coordinate: field.composition(vertex)?.into(),
165                            value: field.value(vertex)?,
166                        })
167                    })
168                    .into_iter()
169                    .collect::<Result<Vec<_>, crate::FieldError>>()?;
170                if let Some(value) = lower {
171                    polygon = clip_lower(&polygon, value, options.value_tolerance);
172                }
173                if let Some(value) = upper {
174                    polygon = clip_upper(&polygon, value, options.value_tolerance);
175                }
176                cleanup_ring(&mut polygon, options.geometry_tolerance);
177                if polygon.len() >= 3
178                    && ring_area_vertices(&polygon).abs() > options.geometry_tolerance
179                {
180                    fragments.push(
181                        polygon
182                            .into_iter()
183                            .map(|vertex| vertex.coordinate)
184                            .collect(),
185                    );
186                }
187            }
188            let fragments = fragments
189                .into_iter()
190                .map(|vertices| ContourFragment { vertices })
191                .collect::<Vec<_>>();
192            bands.push(ContourBand {
193                lower,
194                upper,
195                regions: assemble_regions(
196                    fragments
197                        .iter()
198                        .map(|fragment| fragment.vertices.clone())
199                        .collect(),
200                    options.geometry_tolerance,
201                )?,
202                fragments,
203            });
204        }
205        Ok(Self { bands })
206    }
207
208    /// Return the semantically owning band for a finite scalar value.
209    ///
210    /// Unlike geometric clipping this performs no tolerance expansion: a value
211    /// exactly equal to a break belongs to the band starting at that break.
212    pub fn band_index_for(&self, value: f64) -> Option<usize> {
213        if !value.is_finite() {
214            return None;
215        }
216        self.bands.iter().position(|band| {
217            band.lower.is_none_or(|lower| value >= lower)
218                && band.upper.is_none_or(|upper| value < upper)
219        })
220    }
221}
222
223#[derive(Clone, Copy)]
224struct BandVertex {
225    coordinate: TernaryCoordinate,
226    value: f64,
227}
228
229fn validated_breaks(breaks: &[f64], tolerance: f64) -> Result<Vec<f64>, ContourError> {
230    for (index, value) in breaks.iter().copied().enumerate() {
231        if !value.is_finite() {
232            return Err(ContourError::NonFiniteBandBreak { index, value });
233        }
234    }
235    for (index, pair) in breaks.windows(2).enumerate() {
236        let previous = pair[0];
237        let value = pair[1];
238        if value <= previous {
239            if (previous - value).abs() <= tolerance {
240                return Err(ContourError::DuplicateBandBreak {
241                    first: index,
242                    second: index + 1,
243                    value,
244                });
245            }
246            return Err(ContourError::UnorderedBandBreak {
247                previous_index: index,
248                index: index + 1,
249                previous,
250                value,
251            });
252        }
253        if value - previous <= tolerance {
254            return Err(ContourError::DuplicateBandBreak {
255                first: index,
256                second: index + 1,
257                value,
258            });
259        }
260    }
261    Ok(breaks.to_vec())
262}
263
264fn band_ranges(breaks: &[f64], options: ContourBandOptions) -> Vec<(Option<f64>, Option<f64>)> {
265    if breaks.is_empty() {
266        return vec![(None, None)];
267    }
268    let mut ranges = Vec::with_capacity(breaks.len() + 1);
269    if options.include_lower_extreme {
270        ranges.push((None, Some(breaks[0])));
271    }
272    ranges.extend(breaks.windows(2).map(|pair| (Some(pair[0]), Some(pair[1]))));
273    if options.include_upper_extreme {
274        ranges.push((Some(*breaks.last().expect("nonempty breaks")), None));
275    }
276    ranges
277}
278
279fn clip_lower(input: &[BandVertex], threshold: f64, tolerance: f64) -> Vec<BandVertex> {
280    // Closed geometry is intentional: neighbouring bands share only the
281    // threshold curve. Semantic half-open ownership is exposed separately.
282    clip(input, threshold, tolerance, |delta| delta >= 0.0)
283}
284
285fn clip_upper(input: &[BandVertex], threshold: f64, tolerance: f64) -> Vec<BandVertex> {
286    clip(input, threshold, tolerance, |delta| delta <= 0.0)
287}
288
289fn clip(
290    input: &[BandVertex],
291    threshold: f64,
292    tolerance: f64,
293    is_inside: impl Fn(f64) -> bool,
294) -> Vec<BandVertex> {
295    let mut output = Vec::new();
296    let Some(mut previous) = input.last().copied() else {
297        return output;
298    };
299    let mut previous_inside = is_inside(previous.value - threshold);
300    for current in input.iter().copied() {
301        let current_inside = is_inside(current.value - threshold);
302        if current_inside != previous_inside {
303            push_vertex(
304                &mut output,
305                interpolate(previous, current, threshold, tolerance),
306                tolerance,
307            );
308        }
309        if current_inside {
310            push_vertex(&mut output, current, tolerance);
311        }
312        previous = current;
313        previous_inside = current_inside;
314    }
315    output
316}
317
318fn interpolate(start: BandVertex, end: BandVertex, threshold: f64, tolerance: f64) -> BandVertex {
319    let denominator = end.value - start.value;
320    let mut t = if denominator.abs() <= tolerance {
321        0.0
322    } else {
323        (threshold - start.value) / denominator
324    };
325    if t.abs() <= tolerance {
326        t = 0.0;
327    } else if (1.0 - t).abs() <= tolerance {
328        t = 1.0;
329    }
330    let left = start.coordinate.as_array();
331    let right = end.coordinate.as_array();
332    BandVertex {
333        coordinate: TernaryCoordinate::new(
334            left[0] + (right[0] - left[0]) * t,
335            left[1] + (right[1] - left[1]) * t,
336            left[2] + (right[2] - left[2]) * t,
337        ),
338        value: threshold,
339    }
340}
341
342fn cleanup_ring(vertices: &mut Vec<BandVertex>, tolerance: f64) {
343    let mut clean = Vec::with_capacity(vertices.len());
344    for vertex in vertices.drain(..) {
345        push_vertex(&mut clean, vertex, tolerance);
346    }
347    if clean.len() > 1
348        && points_close(
349            clean[0].coordinate,
350            clean[clean.len() - 1].coordinate,
351            tolerance,
352        )
353    {
354        clean.pop();
355    }
356    *vertices = clean;
357}
358
359fn push_vertex(output: &mut Vec<BandVertex>, vertex: BandVertex, tolerance: f64) {
360    if output
361        .last()
362        .is_none_or(|previous| !points_close(previous.coordinate, vertex.coordinate, tolerance))
363    {
364        output.push(vertex);
365    }
366}
367
368#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
369struct NodeKey(i64, i64);
370
371#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
372struct DirectedEdgeKey(usize, usize);
373
374struct NodeCanonicalizer {
375    tolerance: f64,
376    buckets: BTreeMap<NodeKey, Vec<usize>>,
377    points: Vec<TernaryCoordinate>,
378}
379
380impl NodeCanonicalizer {
381    fn new(tolerance: f64) -> Self {
382        Self {
383            // A tolerance below machine-scale cannot identify distinct computed
384            // intersections reliably. This guard only affects node joining.
385            tolerance: tolerance.max(64.0 * f64::EPSILON),
386            buckets: BTreeMap::new(),
387            points: Vec::new(),
388        }
389    }
390
391    fn node_for(&mut self, point: TernaryCoordinate) -> usize {
392        let key = self.key(point);
393        let mut existing: Option<usize> = None;
394        for da in -1..=1 {
395            for db in -1..=1 {
396                let neighbour = NodeKey(key.0.saturating_add(da), key.1.saturating_add(db));
397                if let Some(candidates) = self.buckets.get(&neighbour) {
398                    for &candidate in candidates {
399                        if points_close(self.points[candidate], point, self.tolerance) {
400                            existing = Some(existing.map_or(candidate, |old| old.min(candidate)));
401                        }
402                    }
403                }
404            }
405        }
406        if let Some(node) = existing {
407            return node;
408        }
409        let node = self.points.len();
410        self.points.push(point);
411        self.buckets.entry(key).or_default().push(node);
412        node
413    }
414
415    fn key(&self, point: TernaryCoordinate) -> NodeKey {
416        let [a, b, _] = point.as_array();
417        NodeKey(bucket(a, self.tolerance), bucket(b, self.tolerance))
418    }
419}
420
421fn bucket(value: f64, tolerance: f64) -> i64 {
422    let scaled = (value / tolerance).floor();
423    if scaled <= i64::MIN as f64 {
424        i64::MIN
425    } else if scaled >= i64::MAX as f64 {
426        i64::MAX
427    } else {
428        scaled as i64
429    }
430}
431
432fn assemble_regions(
433    fragments: Vec<Vec<TernaryCoordinate>>,
434    tolerance: f64,
435) -> Result<Vec<ContourRegion>, ContourError> {
436    let mut nodes = NodeCanonicalizer::new(tolerance);
437    let mut edges = BTreeSet::<DirectedEdgeKey>::new();
438    for fragment in fragments {
439        for (start, end) in fragment
440            .iter()
441            .copied()
442            .zip(fragment.iter().copied().cycle().skip(1))
443            .take(fragment.len())
444        {
445            let start = nodes.node_for(start);
446            let end = nodes.node_for(end);
447            if start == end {
448                continue;
449            }
450            let key = DirectedEdgeKey(start, end);
451            let reverse = DirectedEdgeKey(end, start);
452            if !edges.remove(&reverse) {
453                edges.insert(key);
454            }
455        }
456    }
457
458    let mut outgoing = BTreeMap::<usize, BTreeSet<DirectedEdgeKey>>::new();
459    for key in edges.iter().copied() {
460        outgoing.entry(key.0).or_default().insert(key);
461    }
462    let mut unused = edges.clone();
463    let mut rings = Vec::new();
464    while let Some(start) = unused.iter().next().copied() {
465        let mut ring = Vec::new();
466        let mut current = start;
467        let mut guard = 0usize;
468        loop {
469            guard += 1;
470            if guard > edges.len().saturating_add(1) || !unused.remove(&current) {
471                return Err(ContourError::UnclosedBandBoundary);
472            }
473            let from = nodes.points[current.0];
474            let to = nodes.points[current.1];
475            if ring.is_empty() {
476                ring.push(from);
477            }
478            ring.push(to);
479            if current.1 == start.0 {
480                break;
481            }
482            let candidates = outgoing
483                .get(&current.1)
484                .into_iter()
485                .flatten()
486                .copied()
487                .filter(|key| unused.contains(key))
488                .collect::<Vec<_>>();
489            let Some(next) = select_next(current, &candidates, &nodes.points) else {
490                return Err(ContourError::UnclosedBandBoundary);
491            };
492            current = next;
493        }
494        ring.pop();
495        if ring.len() >= 3 && ring_area(&ring).abs() > tolerance {
496            rings.push(ring);
497        }
498    }
499    Ok(build_regions(rings))
500}
501
502fn select_next(
503    incoming: DirectedEdgeKey,
504    candidates: &[DirectedEdgeKey],
505    nodes: &[TernaryCoordinate],
506) -> Option<DirectedEdgeKey> {
507    let from = nodes[incoming.0].as_array();
508    let middle = nodes[incoming.1].as_array();
509    candidates.iter().copied().min_by(|left, right| {
510        let l = turn_angle(from, middle, nodes[left.1].as_array());
511        let r = turn_angle(from, middle, nodes[right.1].as_array());
512        l.total_cmp(&r).then_with(|| left.cmp(right))
513    })
514}
515
516fn turn_angle(from: [f64; 3], middle: [f64; 3], to: [f64; 3]) -> f64 {
517    let incoming = (middle[0] - from[0], middle[1] - from[1]);
518    let outgoing = (to[0] - middle[0], to[1] - middle[1]);
519    let angle = (incoming.0 * outgoing.1 - incoming.1 * outgoing.0)
520        .atan2(incoming.0 * outgoing.0 + incoming.1 * outgoing.1);
521    if angle <= 0.0 {
522        angle + std::f64::consts::TAU
523    } else {
524        angle
525    }
526}
527
528fn build_regions(mut rings: Vec<Vec<TernaryCoordinate>>) -> Vec<ContourRegion> {
529    rings.sort_by(|left, right| compare_ring_keys(ring_sort_key(left), ring_sort_key(right)));
530    let samples = rings
531        .iter()
532        .map(|ring| interior_sample(ring))
533        .collect::<Vec<_>>();
534    let areas = rings
535        .iter()
536        .map(|ring| ring_area(ring).abs())
537        .collect::<Vec<_>>();
538    let parents = (0..rings.len())
539        .map(|child| {
540            (0..rings.len())
541                .filter(|&candidate| candidate != child && areas[candidate] > areas[child])
542                .filter(|&candidate| point_in_ring(samples[child], &rings[candidate]))
543                .min_by(|&left, &right| areas[left].total_cmp(&areas[right]))
544        })
545        .collect::<Vec<_>>();
546    let depths = (0..rings.len())
547        .map(|index| {
548            let mut depth = 0usize;
549            let mut parent = parents[index];
550            while let Some(next) = parent {
551                depth += 1;
552                parent = parents[next];
553            }
554            depth
555        })
556        .collect::<Vec<_>>();
557
558    let mut exterior_result = BTreeMap::<usize, usize>::new();
559    let mut regions = Vec::new();
560    for index in 0..rings.len() {
561        if depths[index] % 2 == 0 {
562            let mut exterior = rings[index].clone();
563            if ring_area(&exterior) < 0.0 {
564                exterior.reverse();
565            }
566            exterior_result.insert(index, regions.len());
567            regions.push(ContourRegion {
568                exterior,
569                holes: Vec::new(),
570            });
571        }
572    }
573    for index in 0..rings.len() {
574        if depths[index] % 2 == 1 {
575            let mut hole = rings[index].clone();
576            if ring_area(&hole) > 0.0 {
577                hole.reverse();
578            }
579            let mut owner = parents[index];
580            while let Some(parent) = owner {
581                if depths[parent] % 2 == 0 {
582                    if let Some(&region) = exterior_result.get(&parent) {
583                        regions[region].holes.push(hole);
584                    }
585                    break;
586                }
587                owner = parents[parent];
588            }
589        }
590    }
591    for region in &mut regions {
592        region
593            .holes
594            .sort_by(|left, right| compare_ring_keys(ring_sort_key(left), ring_sort_key(right)));
595    }
596    regions.sort_by(|left, right| {
597        compare_ring_keys(
598            ring_sort_key(&left.exterior),
599            ring_sort_key(&right.exterior),
600        )
601    });
602    regions
603}
604
605fn interior_sample(ring: &[TernaryCoordinate]) -> TernaryCoordinate {
606    let signed_area = ring_area(ring);
607    if signed_area.abs() > f64::EPSILON {
608        let (a, b) = ring
609            .iter()
610            .zip(ring.iter().cycle().skip(1))
611            .take(ring.len())
612            .fold((0.0, 0.0), |(a_sum, b_sum), (left, right)| {
613                let [x0, y0, _] = left.as_array();
614                let [x1, y1, _] = right.as_array();
615                let cross = x0 * y1 - x1 * y0;
616                (a_sum + (x0 + x1) * cross, b_sum + (y0 + y1) * cross)
617            });
618        let sample = TernaryCoordinate::new(a / (6.0 * signed_area), b / (6.0 * signed_area), 0.0);
619        if point_in_ring(sample, ring) {
620            return sample;
621        }
622    }
623    let origin = ring[0].as_array();
624    for pair in ring[1..].windows(2) {
625        let left = pair[0].as_array();
626        let right = pair[1].as_array();
627        let sample = TernaryCoordinate::new(
628            (origin[0] + left[0] + right[0]) / 3.0,
629            (origin[1] + left[1] + right[1]) / 3.0,
630            0.0,
631        );
632        if point_in_ring(sample, ring) {
633            return sample;
634        }
635    }
636    // Only reached for malformed rings, which are filtered before assembly.
637    ring[0]
638}
639
640fn compare_ring_keys(left: (f64, f64, usize), right: (f64, f64, usize)) -> std::cmp::Ordering {
641    left.0
642        .total_cmp(&right.0)
643        .then_with(|| left.1.total_cmp(&right.1))
644        .then_with(|| left.2.cmp(&right.2))
645}
646
647fn ring_sort_key(ring: &[TernaryCoordinate]) -> (f64, f64, usize) {
648    let point = ring
649        .iter()
650        .map(|point| point.as_array())
651        .min_by(|left, right| {
652            left[0]
653                .total_cmp(&right[0])
654                .then_with(|| left[1].total_cmp(&right[1]))
655        })
656        .expect("nonempty ring");
657    (point[0], point[1], ring.len())
658}
659
660fn point_in_ring(point: TernaryCoordinate, ring: &[TernaryCoordinate]) -> bool {
661    let [x, y, _] = point.as_array();
662    ring.iter()
663        .zip(ring.iter().cycle().skip(1))
664        .take(ring.len())
665        .fold(false, |inside, (left, right)| {
666            let [x0, y0, _] = left.as_array();
667            let [x1, y1, _] = right.as_array();
668            if (y0 > y) != (y1 > y) && x < (x1 - x0) * (y - y0) / (y1 - y0) + x0 {
669                !inside
670            } else {
671                inside
672            }
673        })
674}
675
676fn ring_area_vertices(vertices: &[BandVertex]) -> f64 {
677    let coordinates = vertices
678        .iter()
679        .map(|vertex| vertex.coordinate)
680        .collect::<Vec<_>>();
681    ring_area(&coordinates)
682}
683
684fn ring_area(vertices: &[TernaryCoordinate]) -> f64 {
685    vertices
686        .iter()
687        .zip(vertices.iter().cycle().skip(1))
688        .take(vertices.len())
689        .map(|(left, right)| {
690            let left = left.as_array();
691            let right = right.as_array();
692            left[0] * right[1] - left[1] * right[0]
693        })
694        .sum::<f64>()
695        * 0.5
696}
697
698fn points_close(left: TernaryCoordinate, right: TernaryCoordinate, tolerance: f64) -> bool {
699    left.as_array()
700        .into_iter()
701        .zip(right.as_array())
702        .all(|(a, b)| (a - b).abs() <= tolerance)
703}
704
705#[cfg(test)]
706mod tests {
707    use super::*;
708
709    fn field(n: usize, value: impl Fn(f64, f64, f64) -> f64) -> RegularTernaryScalarField {
710        RegularTernaryScalarField::from_fn(n, |[a, b, c]| value(a, b, c)).unwrap()
711    }
712    fn area(bands: &ContourBandSet) -> f64 {
713        bands
714            .bands
715            .iter()
716            .flat_map(|band| &band.regions)
717            .map(ContourRegion::area)
718            .sum()
719    }
720
721    #[test]
722    fn one_triangle_cut_by_threshold_conserves_simplex_area() {
723        let field = field(1, |a, _, _| a);
724        let bands = ContourBandSet::compute(&field, &[0.5], ContourBandOptions::linear()).unwrap();
725        assert_eq!(bands.bands.len(), 2);
726        assert!((area(&bands) - 0.5).abs() < 1e-10);
727        assert!(bands.bands.iter().all(|band| !band.regions.is_empty()));
728    }
729
730    #[test]
731    fn two_thresholds_and_extremes_are_ordered() {
732        let field = field(1, |a, _, _| a);
733        let bands =
734            ContourBandSet::compute(&field, &[0.25, 0.75], ContourBandOptions::linear()).unwrap();
735        assert_eq!(
736            bands
737                .bands
738                .iter()
739                .map(|band| (band.lower, band.upper))
740                .collect::<Vec<_>>(),
741            vec![
742                (None, Some(0.25)),
743                (Some(0.25), Some(0.75)),
744                (Some(0.75), None)
745            ]
746        );
747        assert!((area(&bands) - 0.5).abs() < 1e-10);
748    }
749
750    #[test]
751    fn exact_vertex_and_edge_breaks_are_deterministic() {
752        let field = field(2, |a, _, _| a);
753        let first = ContourBandSet::compute(&field, &[0.5], ContourBandOptions::linear()).unwrap();
754        let second = ContourBandSet::compute(&field, &[0.5], ContourBandOptions::linear()).unwrap();
755        assert_eq!(first, second);
756        assert!((area(&first) - 0.5).abs() < 1e-9);
757    }
758
759    #[test]
760    fn outer_band_can_retain_an_interior_hole() {
761        let field = field(18, |a, b, c| {
762            (a - 1.0 / 3.0).powi(2) + (b - 1.0 / 3.0).powi(2) + (c - 1.0 / 3.0).powi(2)
763        });
764        let bands =
765            ContourBandSet::compute(&field, &[0.025, 0.10], ContourBandOptions::linear()).unwrap();
766        assert!(
767            bands.bands[2]
768                .regions
769                .iter()
770                .any(|region| !region.holes.is_empty())
771        );
772        assert!((area(&bands) - 0.5).abs() < 1.0e-7);
773    }
774    #[test]
775    fn invalid_breaks_and_cubic_mode_are_explicit() {
776        let field = field(1, |a, _, _| a);
777        assert!(matches!(
778            ContourBandSet::compute(&field, &[f64::NAN], ContourBandOptions::linear()),
779            Err(ContourError::NonFiniteBandBreak { .. })
780        ));
781        assert!(matches!(
782            ContourBandSet::compute(&field, &[0.5, 0.5], ContourBandOptions::linear()),
783            Err(ContourError::DuplicateBandBreak { .. })
784        ));
785        let mut options = ContourBandOptions::linear();
786        options.interpolation = ContourInterpolation::CubicAlpha(Default::default());
787        assert!(matches!(
788            ContourBandSet::compute(&field, &[0.5], options),
789            Err(ContourError::UnsupportedFilledInterpolation)
790        ));
791    }
792
793    #[test]
794    fn all_bands_cover_disconnected_linear_regions_without_zero_area_rings() {
795        let field = field(8, |a, b, c| {
796            (a - 0.2).powi(2) + (b - 0.25).powi(2) + (c - 0.55).powi(2)
797        });
798        let bands =
799            ContourBandSet::compute(&field, &[0.04, 0.12], ContourBandOptions::linear()).unwrap();
800        assert!((area(&bands) - 0.5).abs() < 1e-7);
801        assert!(
802            bands
803                .bands
804                .iter()
805                .flat_map(|band| &band.regions)
806                .all(|region| region.area() > 1e-10)
807        );
808    }
809    #[test]
810    fn breaks_are_strictly_increasing_and_scalar_ownership_is_half_open() {
811        let field = field(1, |a, _, _| a);
812        let options = ContourBandOptions::linear();
813        let bands = ContourBandSet::compute(&field, &[0.25, 0.75], options).unwrap();
814        assert_eq!(bands.band_index_for(0.249_999_999), Some(0));
815        assert_eq!(bands.band_index_for(0.25), Some(1));
816        assert_eq!(bands.band_index_for(0.75), Some(2));
817        assert_eq!(bands.band_index_for(f64::NAN), None);
818        assert!(matches!(
819            ContourBandSet::compute(&field, &[0.75, 0.25], options),
820            Err(ContourError::UnorderedBandBreak { .. })
821        ));
822        assert!(matches!(
823            ContourBandSet::compute(&field, &[0.25, 0.25 + 1.0e-12], options),
824            Err(ContourError::DuplicateBandBreak { .. })
825        ));
826        assert!(ContourBandSet::compute(&field, &[], options).is_ok());
827    }
828
829    #[test]
830    fn containment_assigns_holes_and_nested_islands_without_orientation_assumptions() {
831        let coordinate = |a, b| TernaryCoordinate::new(a, b, 1.0 - a - b);
832        let outer = vec![
833            coordinate(0.05, 0.05),
834            coordinate(0.85, 0.05),
835            coordinate(0.85, 0.85),
836            coordinate(0.05, 0.85),
837        ];
838        let hole = vec![
839            coordinate(0.25, 0.25),
840            coordinate(0.65, 0.25),
841            coordinate(0.65, 0.65),
842            coordinate(0.25, 0.65),
843        ];
844        let island = vec![
845            coordinate(0.35, 0.35),
846            coordinate(0.55, 0.35),
847            coordinate(0.55, 0.55),
848            coordinate(0.35, 0.55),
849        ];
850        let regions = build_regions(vec![outer, hole, island]);
851        assert_eq!(regions.len(), 2);
852        assert_eq!(
853            regions
854                .iter()
855                .filter(|region| !region.holes.is_empty())
856                .count(),
857            1
858        );
859        assert!(
860            regions
861                .iter()
862                .all(|region| ring_area(&region.exterior) > 0.0)
863        );
864        assert!(
865            regions
866                .iter()
867                .flat_map(|region| &region.holes)
868                .all(|ring| ring_area(ring) < 0.0)
869        );
870    }
871
872    #[test]
873    fn neighbour_cell_canonicalisation_cancels_shared_fragment_edges_once() {
874        let coordinate = |a, b| TernaryCoordinate::new(a, b, 1.0 - a - b);
875        let epsilon = 0.25e-8;
876        let regions = assemble_regions(
877            vec![
878                vec![
879                    coordinate(0.0, 0.0),
880                    coordinate(0.5, 0.0),
881                    coordinate(0.5, 0.5),
882                ],
883                vec![
884                    coordinate(0.5 + epsilon, 0.0),
885                    coordinate(1.0, 0.0),
886                    coordinate(0.5 + epsilon, 0.5),
887                ],
888            ],
889            1.0e-8,
890        )
891        .unwrap();
892        assert_eq!(regions.len(), 1);
893        assert!(regions[0].area() > 0.2);
894    }
895
896    #[test]
897    fn assembled_regions_and_fragments_have_matching_coverage() {
898        let field = field(9, |a, b, c| 0.4 * a - 0.3 * b + 0.8 * c);
899        let bands =
900            ContourBandSet::compute(&field, &[0.05, 0.25, 0.45], ContourBandOptions::linear())
901                .unwrap();
902        let fragment_area = bands
903            .bands
904            .iter()
905            .flat_map(|band| band.fragments())
906            .map(|fragment| ring_area(fragment.vertices()).abs())
907            .sum::<f64>();
908        assert!((fragment_area - area(&bands)).abs() < 1.0e-8);
909        for i in 1..20 {
910            for j in 1..(20 - i) {
911                let a = i as f64 / 20.0;
912                let b = j as f64 / 20.0;
913                let value = 0.4 * a - 0.3 * b + 0.8 * (1.0 - a - b);
914                if [0.05_f64, 0.25, 0.45]
915                    .iter()
916                    .any(|break_value| (value - break_value).abs() < 1.0e-9)
917                {
918                    continue;
919                }
920                let expected = bands.band_index_for(value).unwrap();
921                let point = TernaryCoordinate::new(a, b, 1.0 - a - b);
922                let covered = bands
923                    .bands
924                    .iter()
925                    .enumerate()
926                    .filter(|(_, band)| {
927                        band.fragments()
928                            .iter()
929                            .any(|fragment| point_in_ring(point, fragment.vertices()))
930                    })
931                    .map(|(index, _)| index)
932                    .collect::<Vec<_>>();
933                assert_eq!(covered, vec![expected]);
934            }
935        }
936    }
937}