1use std::collections::{BTreeMap, BTreeSet};
2
3use crate::{RegularTernaryScalarField, TernaryCoordinate};
4
5use super::{ContourError, ContourInterpolation};
6
7#[derive(Clone, Copy, Debug, PartialEq)]
15pub struct ContourBandOptions {
16 pub interpolation: ContourInterpolation,
19 pub value_tolerance: f64,
21 pub geometry_tolerance: f64,
23 pub include_lower_extreme: bool,
25 pub include_upper_extreme: bool,
27}
28
29impl ContourBandOptions {
30 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#[derive(Clone, Debug, PartialEq)]
71pub struct ContourBand {
72 pub lower: Option<f64>,
74 pub upper: Option<f64>,
76 pub regions: Vec<ContourRegion>,
78 fragments: Vec<ContourFragment>,
79}
80
81impl ContourBand {
82 pub fn fragments(&self) -> &[ContourFragment] {
88 &self.fragments
89 }
90}
91
92#[derive(Clone, Debug, PartialEq)]
97pub struct ContourFragment {
98 vertices: Vec<TernaryCoordinate>,
99}
100
101impl ContourFragment {
102 pub fn vertices(&self) -> &[TernaryCoordinate] {
104 &self.vertices
105 }
106}
107
108#[derive(Clone, Debug, PartialEq)]
114pub struct ContourRegion {
115 pub exterior: Vec<TernaryCoordinate>,
117 pub holes: Vec<Vec<TernaryCoordinate>>,
119}
120
121impl ContourRegion {
122 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#[derive(Clone, Debug, PartialEq)]
135pub struct ContourBandSet {
136 pub bands: Vec<ContourBand>,
138}
139
140impl ContourBandSet {
141 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 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 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 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(¤t) {
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(¤t.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(®ion) = 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 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(®ion.exterior) > 0.0)
863 );
864 assert!(
865 regions
866 .iter()
867 .flat_map(|region| ®ion.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}