alpha2_geometry/
trim.rs

1//! Trim paths: keeping a span of geometry's length.
2
3use crate::arclen;
4use kurbo::{Affine, BezPath, ParamCurve, PathEl, PathSeg, Point};
5
6/// A subpath as its segments, closed ones including the segment back to the
7/// start.
8#[derive(Clone, Debug, PartialEq)]
9pub struct Subpath {
10    /// The segments, in order.
11    pub segments: Vec<PathSeg>,
12    /// Whether the last segment ends where the first starts, joined.
13    pub closed: bool,
14    /// Where it starts, for a subpath of no segments.
15    pub start: Point,
16}
17
18/// The subpaths of `path`, each closed one with its closing segment.
19#[must_use]
20pub fn subpaths(path: &BezPath) -> Vec<Subpath> {
21    let mut found: Vec<Subpath> = Vec::new();
22    let mut current: Option<Subpath> = None;
23    let mut last = Point::ZERO;
24    for element in path.elements() {
25        match *element {
26            PathEl::MoveTo(p) => {
27                found.extend(current.take());
28                current = Some(Subpath {
29                    segments: Vec::new(),
30                    closed: false,
31                    start: p,
32                });
33                last = p;
34            }
35            PathEl::LineTo(p) => {
36                let subpath = current.get_or_insert_with(|| open_at(last));
37                subpath
38                    .segments
39                    .push(PathSeg::Line(kurbo::Line::new(last, p)));
40                last = p;
41            }
42            PathEl::QuadTo(a, b) => {
43                let subpath = current.get_or_insert_with(|| open_at(last));
44                subpath
45                    .segments
46                    .push(PathSeg::Quad(kurbo::QuadBez::new(last, a, b)));
47                last = b;
48            }
49            PathEl::CurveTo(a, b, c) => {
50                let subpath = current.get_or_insert_with(|| open_at(last));
51                subpath
52                    .segments
53                    .push(PathSeg::Cubic(kurbo::CubicBez::new(last, a, b, c)));
54                last = c;
55            }
56            PathEl::ClosePath => {
57                if let Some(mut subpath) = current.take() {
58                    if last != subpath.start {
59                        subpath
60                            .segments
61                            .push(PathSeg::Line(kurbo::Line::new(last, subpath.start)));
62                    }
63                    subpath.closed = true;
64                    last = subpath.start;
65                    found.push(subpath);
66                }
67            }
68        }
69    }
70    found.extend(current);
71    found
72}
73
74fn open_at(point: Point) -> Subpath {
75    Subpath {
76        segments: Vec::new(),
77        closed: false,
78        start: point,
79    }
80}
81
82/// Appends `subpath` to `path`.
83pub fn append(path: &mut BezPath, subpath: &Subpath) {
84    let Some(first) = subpath.segments.first() else {
85        return;
86    };
87    path.move_to(first.start());
88    for segment in &subpath.segments {
89        match *segment {
90            PathSeg::Line(line) => path.line_to(line.p1),
91            PathSeg::Quad(quad) => path.quad_to(quad.p1, quad.p2),
92            PathSeg::Cubic(cubic) => path.curve_to(cubic.p1, cubic.p2, cubic.p3),
93        }
94    }
95    if subpath.closed {
96        path.close_path();
97    }
98}
99
100/// What a trim keeps.
101#[derive(Copy, Clone, Debug, PartialEq)]
102pub struct TrimSpan {
103    /// Start, as a fraction of the length, in `0..=1`.
104    pub start: f64,
105    /// End, as a fraction of the length, in `0..=1`.
106    pub end: f64,
107    /// Turns the span is shifted by.
108    pub offset: f64,
109}
110
111impl TrimSpan {
112    /// The kept fractions of a length, in order along it: none when the span
113    /// is empty, the whole when it covers it, two when it wraps past the end.
114    fn ranges(self) -> Ranges {
115        if self.start.is_nan() || self.end.is_nan() || self.start >= self.end {
116            return Ranges::None;
117        }
118        if self.end - self.start >= 1.0 {
119            return Ranges::Whole;
120        }
121        let shift = self.offset - self.offset.floor();
122        let mut start = self.start + shift;
123        let mut end = self.end + shift;
124        if start >= 1.0 {
125            start -= 1.0;
126            end -= 1.0;
127        }
128        if end > 1.0 {
129            Ranges::Wrapped(start, end - 1.0)
130        } else {
131            Ranges::One(start, end)
132        }
133    }
134}
135
136enum Ranges {
137    None,
138    Whole,
139    One(f64, f64),
140    /// `start..1` and then `0..end`.
141    Wrapped(f64, f64),
142}
143
144/// One subpath and the transform its lengths are measured through.
145#[derive(Clone, Debug)]
146pub struct Measured {
147    /// The subpath, in its own space.
148    pub subpath: Subpath,
149    /// Maps the subpath's points into the space its lengths are measured in.
150    pub measure: Affine,
151}
152
153/// Each segment's length through `measure`.
154fn segment_lengths(subpath: &Subpath, measure: Affine) -> Vec<f64> {
155    subpath
156        .segments
157        .iter()
158        .map(|segment| arclen::length(&transformed(*segment, measure)))
159        .collect()
160}
161
162fn transformed(segment: PathSeg, affine: Affine) -> PathSeg {
163    affine * segment
164}
165
166/// The shortest piece of a segment a cut keeps, in measured pixels. A span
167/// that ends on a segment boundary can reach past it by rounding; the
168/// sliver that leaves has no usable tangent, and stroking it puts NaN in
169/// the outline.
170const MIN_PIECE_LENGTH: f64 = 1e-6;
171
172/// The part of `subpath` between `from` and `to` (lengths along it, in the
173/// measured space), as an open subpath in its own space.
174fn cut(subpath: &Subpath, lengths: &[f64], measure: Affine, from: f64, to: f64) -> Subpath {
175    let mut segments = Vec::new();
176    let mut run = 0.0;
177    for (segment, &length) in subpath.segments.iter().zip(lengths) {
178        let (start, end) = (run, run + length);
179        run = end;
180        if to.min(end) - from.max(start) < MIN_PIECE_LENGTH {
181            continue;
182        }
183        let measured = transformed(*segment, measure);
184        let t0 = if from > start {
185            arclen::parameter_at(&measured, from - start, length)
186        } else {
187            0.0
188        };
189        let t1 = if to < end {
190            arclen::parameter_at(&measured, to - start, length)
191        } else {
192            1.0
193        };
194        if t1 > t0 {
195            let whole = t0 <= 0.0 && t1 >= 1.0;
196            segments.push(if whole {
197                *segment
198            } else {
199                segment.subsegment(t0..t1)
200            });
201        }
202    }
203    let start = segments.first().map_or(subpath.start, PathSeg::start);
204    Subpath {
205        segments,
206        closed: false,
207        start,
208    }
209}
210
211/// Keeps `span` of `parts` together: of their lengths laid end to end in
212/// order. A span that wraps past the end continues from the start; around a
213/// single closed subpath the two pieces join into one. Each piece comes with
214/// the index of the part it was cut from.
215#[must_use]
216pub fn trim_together(parts: &[Measured], span: TrimSpan) -> Vec<(usize, Subpath)> {
217    let lengths: Vec<Vec<f64>> = parts
218        .iter()
219        .map(|part| segment_lengths(&part.subpath, part.measure))
220        .collect();
221    let totals: Vec<f64> = lengths.iter().map(|list| list.iter().sum()).collect();
222    let total: f64 = totals.iter().sum();
223    let pieces = |from: f64, to: f64| -> Vec<(usize, Subpath)> {
224        let mut kept = Vec::new();
225        let mut offset = 0.0;
226        for (index, part) in parts.iter().enumerate() {
227            let (start, end) = (offset, offset + totals[index]);
228            offset = end;
229            if end <= from || start >= to {
230                continue;
231            }
232            if from <= start && to >= end {
233                kept.push((index, part.subpath.clone()));
234            } else {
235                kept.push((
236                    index,
237                    cut(
238                        &part.subpath,
239                        &lengths[index],
240                        part.measure,
241                        from - start,
242                        to - start,
243                    ),
244                ));
245            }
246        }
247        kept
248    };
249    match span.ranges() {
250        Ranges::None => Vec::new(),
251        Ranges::Whole => parts
252            .iter()
253            .enumerate()
254            .map(|(index, part)| (index, part.subpath.clone()))
255            .collect(),
256        Ranges::One(start, end) => pieces(start * total, end * total),
257        Ranges::Wrapped(start, end) => {
258            let mut tail = pieces(start * total, total);
259            let head = pieces(0.0, end * total);
260            let joined = parts.len() == 1 && parts[0].subpath.closed;
261            if joined && let (Some((_, last)), Some((_, first))) = (tail.last_mut(), head.first()) {
262                last.segments.extend(first.segments.iter().copied());
263                return tail;
264            }
265            tail.into_iter().chain(head).collect()
266        }
267    }
268}
269
270/// Keeps `span` of each of `parts` by its own length, each piece with the
271/// index of its part.
272#[must_use]
273pub fn trim_individually(parts: &[Measured], span: TrimSpan) -> Vec<(usize, Subpath)> {
274    parts
275        .iter()
276        .enumerate()
277        .flat_map(|(index, part)| {
278            trim_together(std::slice::from_ref(part), span)
279                .into_iter()
280                .map(move |(_, piece)| (index, piece))
281        })
282        .collect()
283}
284
285/// The length of `subpath` through `measure`.
286#[must_use]
287pub fn subpath_length(subpath: &Subpath, measure: Affine) -> f64 {
288    segment_lengths(subpath, measure).iter().sum()
289}
290
291/// The point `distance` along `subpath` (in its own space; lengths through
292/// `measure`), clamped to its ends.
293#[must_use]
294pub fn point_at_length(subpath: &Subpath, measure: Affine, distance: f64) -> Point {
295    let mut run = 0.0;
296    for segment in &subpath.segments {
297        let measured = transformed(*segment, measure);
298        let length = arclen::length(&measured);
299        if distance <= run + length && length > 0.0 {
300            let t = arclen::parameter_at(&measured, distance - run, length);
301            return segment.eval(t);
302        }
303        run += length;
304    }
305    subpath.segments.last().map_or(subpath.start, PathSeg::end)
306}
alpha2_geometry/trim.rs

alpha2_geometry/
trim.rs
