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

alpha2_geometry/
trim.rs
