1  //! Curve order comparisons, with caching.
 2  
 3  use std::collections::HashMap;
 4  
 5  use crate::{
 6      curve::{self, CurveOrder},
 7      SegIdx, Segments,
 8  };
 9  
10  /// A cache for curve comparisons, so that each pair of curves needs to be compared at most once.
11  #[derive(Clone, Debug)]
12  pub struct ComparisonCache {
13      inner: HashMap<(SegIdx, SegIdx), CurveOrder>,
14      accuracy: f64,
15      tolerance: f64,
16      y_slop: f64,
17  }
18  
19  impl ComparisonCache {
20      /// Creates a new comparison cache.
21      ///
22      /// `tolerance` tells us how close two curves can be to be declared "ish", and
23      /// `accuracy` tells us how closely we need to evaluate the tolerance. For
24      /// example, if `accuracy` is `tolerance / 2.0` then we'll guarantee (up to
25      /// some floating-point error) that if the two curves are further than
26      /// `1.5 * tolerance` apart then we'll give them a strict order, and if they're
27      /// less than `tolerance / 2.0` apart then we'll give then an "ish" order.
28      pub fn new(tolerance: f64, accuracy: f64) -> Self {
29          ComparisonCache {
30              inner: HashMap::new(),
31              accuracy,
32              tolerance,
33              y_slop: tolerance,
34          }
35      }
36  
37      /// Creates a new comparison cache.
38      ///
39      /// `tolerance` tells us how close two curves can be to be declared "ish", and
40      /// `accuracy` tells us how closely we need to evaluate the tolerance. For
41      /// example, if `accuracy` is `tolerance / 2.0` then we'll guarantee (up to
42      /// some floating-point error) that if the two curves are further than
43      /// `1.5 * tolerance` apart then we'll give them a strict order, and if they're
44      /// less than `tolerance / 2.0` apart then we'll give then an "ish" order.
45      pub fn new_without_y_slop(tolerance: f64, accuracy: f64) -> Self {
46          ComparisonCache {
47              inner: HashMap::new(),
48              accuracy,
49              tolerance,
50              y_slop: 0.0,
51          }
52      }
53  
54      /// Compares two segments, returning their order.
55      ///
56      /// TODO: this API will change to something with less cloning
57      pub fn compare_segments(&mut self, segments: &Segments, i: SegIdx, j: SegIdx) -> CurveOrder {
58          if let Some(order) = self.inner.get(&(i, j)) {
59              return order.clone();
60          }
61  
62          let segi = &segments[i];
63          let segj = &segments[j];
64  
65          let c0 = segi.to_kurbo_cubic();
66          let c1 = segj.to_kurbo_cubic();
67          let forward =
68              curve::intersect_cubics(c0, c1, self.tolerance, self.accuracy).with_y_slop(self.y_slop);
69          let reverse = forward.flip();
70          self.inner.insert((j, i), reverse);
71          self.inner.entry((i, j)).insert_entry(forward).get().clone()
72      }
73  }
74  
75  #[cfg(test)]
76  mod tests {
77      use crate::{curve::Order, SegIdx, Segments};
78  
79      use super::ComparisonCache;
80  
81      #[test]
82      fn slop_regression() {
83          let mut segments = Segments::default();
84          let eps = 0.1;
85          segments.add_points([(-0.5, -0.5), (-0.5, 0.5)]);
86          segments.add_points([(0.0, 0.0), (0.0, 1.0)]);
87          let mut cmp_cache = ComparisonCache::new(eps, eps / 2.0);
88          assert_eq!(
89              cmp_cache
90                  .compare_segments(&segments, SegIdx(0), SegIdx(1))
91                  .iter()
92                  .next()
93                  .unwrap()
94                  .2,
95              Order::Left
96          );
97      }
98  }