1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//! Curve order comparisons, with caching.
use rustc_hash::FxHashMap;
use crate::{
curve::{self, CurveOrder},
SegIdx, Segments,
};
/// A cache for curve comparisons, so that each pair of curves needs to be compared at most once.
#[derive(Clone, Debug)]
pub struct ComparisonCache {
inner: FxHashMap<(SegIdx, SegIdx), (CurveOrder, CurveOrder)>,
accuracy: f64,
tolerance: f64,
y_slop: f64,
}
impl ComparisonCache {
/// Creates a new comparison cache.
///
/// `tolerance` tells us how close two curves can be to be declared "ish", and
/// `accuracy` tells us how closely we need to evaluate the tolerance. For
/// example, if `accuracy` is `tolerance / 2.0` then we'll guarantee (up to
/// some floating-point error) that if the two curves are further than
/// `1.5 * tolerance` apart then we'll give them a strict order, and if they're
/// less than `tolerance / 2.0` apart then we'll give then an "ish" order.
pub fn new(tolerance: f64, accuracy: f64) -> Self {
ComparisonCache {
inner: FxHashMap::default(),
accuracy,
tolerance,
y_slop: tolerance,
}
}
/// Creates a new comparison cache.
///
/// `tolerance` tells us how close two curves can be to be declared "ish", and
/// `accuracy` tells us how closely we need to evaluate the tolerance. For
/// example, if `accuracy` is `tolerance / 2.0` then we'll guarantee (up to
/// some floating-point error) that if the two curves are further than
/// `1.5 * tolerance` apart then we'll give them a strict order, and if they're
/// less than `tolerance / 2.0` apart then we'll give then an "ish" order.
pub fn new_without_y_slop(tolerance: f64, accuracy: f64) -> Self {
ComparisonCache {
inner: FxHashMap::default(),
accuracy,
tolerance,
y_slop: 0.0,
}
}
/// Compares two segments, returning their order.
pub fn compare_segments(
&mut self,
segments: &Segments,
i: SegIdx,
j: SegIdx,
) -> &mut CurveOrder {
use std::collections::hash_map::Entry;
let (i, j, flipped) = if i.0 < j.0 {
(i, j, false)
} else {
(j, i, true)
};
match self.inner.entry((i, j)) {
Entry::Occupied(o) => {
if flipped {
&mut o.into_mut().1
} else {
&mut o.into_mut().0
}
}
Entry::Vacant(v) => {
let segi = &segments[i];
let segj = &segments[j];
let forward =
if let (Some(l0), Some(l1)) = (segi.as_kurbo_line(), segj.as_kurbo_line()) {
curve::line::intersect_lines(l0, l1, self.tolerance)
} else {
let c0 = segi.to_kurbo_cubic();
let c1 = segj.to_kurbo_cubic();
curve::intersect_cubics(c0, c1, self.tolerance, self.accuracy)
.with_y_slop(self.y_slop)
};
debug_assert_eq!(
forward.iter().last().unwrap().1,
segi.end().y.min(segj.end().y)
);
let reverse = forward.flip();
let v = v.insert((forward, reverse));
if flipped {
&mut v.1
} else {
&mut v.0
}
}
}
}
}
#[cfg(test)]
mod tests {
use crate::{curve::Order, SegIdx, Segments};
use super::ComparisonCache;
#[test]
fn slop_regression() {
let mut segments = Segments::default();
let eps = 0.1;
segments.add_points([(-0.5, -0.5), (-0.5, 0.5)]);
segments.add_points([(0.0, 0.0), (0.0, 1.0)]);
let mut cmp_cache = ComparisonCache::new(eps, eps / 2.0);
assert_eq!(
cmp_cache
.compare_segments(&segments, SegIdx(0), SegIdx(1))
.iter()
.next()
.unwrap()
.2,
Order::Left
);
}
}