1  //! Curve order comparisons, with caching.
  2  
  3  use rustc_hash::FxHashMap;
  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: FxHashMap<(SegIdx, SegIdx), (CurveOrder, 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: FxHashMap::default(),
 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: FxHashMap::default(),
 48              accuracy,
 49              tolerance,
 50              y_slop: 0.0,
 51          }
 52      }
 53  
 54      /// Compares two segments, returning their order.
 55      pub fn compare_segments(
 56          &mut self,
 57          segments: &Segments,
 58          i: SegIdx,
 59          j: SegIdx,
 60      ) -> &mut CurveOrder {
 61          use std::collections::hash_map::Entry;
 62  
 63          let (i, j, flipped) = if i.0 < j.0 {
 64              (i, j, false)
 65          } else {
 66              (j, i, true)
 67          };
 68  
 69          match self.inner.entry((i, j)) {
 70              Entry::Occupied(o) => {
 71                  if flipped {
 72                      &mut o.into_mut().1
 73                  } else {
 74                      &mut o.into_mut().0
 75                  }
 76              }
 77              Entry::Vacant(v) => {
 78                  let segi = &segments[i];
 79                  let segj = &segments[j];
 80  
 81                  let forward =
 82                      if let (Some(l0), Some(l1)) = (segi.as_kurbo_line(), segj.as_kurbo_line()) {
 83                          curve::line::intersect_lines(l0, l1, self.tolerance)
 84                      } else {
 85                          let c0 = segi.to_kurbo_cubic();
 86                          let c1 = segj.to_kurbo_cubic();
 87                          curve::intersect_cubics(c0, c1, self.tolerance, self.accuracy)
 88                              .with_y_slop(self.y_slop)
 89                      };
 90                  debug_assert_eq!(
 91                      forward.iter().last().unwrap().1,
 92                      segi.end().y.min(segj.end().y)
 93                  );
 94                  let reverse = forward.flip();
 95                  let v = v.insert((forward, reverse));
 96                  if flipped {
 97                      &mut v.1
 98                  } else {
 99                      &mut v.0
100                  }
101              }
102          }
103      }
104  }
105  
106  #[cfg(test)]
107  mod tests {
108      use crate::{curve::Order, SegIdx, Segments};
109  
110      use super::ComparisonCache;
111  
112      #[test]
113      fn slop_regression() {
114          let mut segments = Segments::default();
115          let eps = 0.1;
116          segments.add_points([(-0.5, -0.5), (-0.5, 0.5)]);
117          segments.add_points([(0.0, 0.0), (0.0, 1.0)]);
118          let mut cmp_cache = ComparisonCache::new(eps, eps / 2.0);
119          assert_eq!(
120              cmp_cache
121                  .compare_segments(&segments, SegIdx(0), SegIdx(1))
122                  .iter()
123                  .next()
124                  .unwrap()
125                  .2,
126              Order::Left
127          );
128      }
129  }