lyon_algorithms/
measure.rs

1//! Perform cached measurements and split operations on a path.
2//!
3use crate::geom::{CubicBezierSegment, LineSegment, QuadraticBezierSegment, Segment};
4use crate::math::*;
5use crate::path::{
6    builder::PathBuilder, AttributeStore, Attributes, EndpointId, IdEvent, Path, PathSlice,
7    PositionStore,
8};
9use core::ops::Range;
10
11use alloc::vec::Vec;
12
13/// Whether to measure real or normalized (between 0 and 1) distances.
14#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
15pub enum SampleType {
16    Distance,
17    Normalized,
18}
19
20type EndpointPair = (EndpointId, EndpointId);
21
22enum SegmentWrapper {
23    Empty,
24    Line(LineSegment<f32>, EndpointPair),
25    Quadratic(QuadraticBezierSegment<f32>, EndpointPair),
26    Cubic(CubicBezierSegment<f32>, EndpointPair),
27}
28
29impl SegmentWrapper {
30    fn split(&self, range: Range<f32>) -> Self {
31        match self {
32            Self::Empty => Self::Empty,
33            Self::Line(segment, pair) => Self::Line(segment.split_range(range), *pair),
34            Self::Quadratic(segment, pair) => Self::Quadratic(segment.split_range(range), *pair),
35            Self::Cubic(segment, pair) => Self::Cubic(segment.split_range(range), *pair),
36        }
37    }
38}
39
40struct Edge {
41    // distance from the beginning of the path
42    distance: f32,
43    // which segment this edge is on
44    index: usize,
45    // t-value of the endpoint on the segment
46    t: f32,
47}
48
49/// The result of sampling a path.
50#[derive(PartialEq, Debug)]
51pub struct PathSample<'l> {
52    position: Point,
53    tangent: Vector,
54    attributes: Attributes<'l>,
55}
56
57impl<'l> PathSample<'l> {
58    #[inline]
59    pub fn position(&self) -> Point {
60        self.position
61    }
62
63    #[inline]
64    pub fn tangent(&self) -> Vector {
65        self.tangent
66    }
67
68    // Takes &mut self to allow interpolating attributes lazily (like the stroke tessellator) without changing
69    // the API.
70    #[inline]
71    pub fn attributes(&mut self) -> Attributes<'l> {
72        self.attributes
73    }
74}
75
76/// An acceleration structure for sampling distances along a specific path.
77///
78/// Building the path measurements can be an expensive operation depending on the complexity of the
79/// measured path, so it is usually a good idea to cache and reuse it whenever possible.
80///
81/// Queries on path measurements are made via a sampler object (see `PathSampler`) which can be configured
82/// to measure real distance or normalized ones (values between 0 and 1 with zero indicating the start
83/// of the path and 1 indicating the end).
84///
85/// ## Differences with the `PathWalker`
86///
87/// The `walker` module provides a similar functionality via the `PathWalker`. The main differences are:
88///  - The path walker does all of its computation on the fly without storing any information for later use.
89///  - `PathMeasurements` stores potentially large amounts of data to speed up sample queries.
90///  - The cost of creating `PathMeasurements` is similar to that of walking the entire path once.
91///  - Once the `PathMeasurements` have been created, random samples on the path are much faster than path walking.
92///  - The PathWalker does not handle normalized distances since the length of the path cannot be known without
93///    traversing the entire path at least once.
94///
95/// Prefer `PathMeasurements` over `PathWalker` if the measurements can be cached and reused for a large number of
96/// queries.
97///
98/// ## Example
99///
100/// ```
101/// use lyon_algorithms::{
102///     math::point,
103///     path::Path,
104///     length::approximate_length,
105///     measure::{PathMeasurements, SampleType},
106/// };
107///
108/// let mut path = Path::builder();
109/// path.begin(point(0.0, 0.0));
110/// path.quadratic_bezier_to(point(1.0, 1.0), point(2.0, 0.0));
111/// path.end(false);
112/// let path = path.build();
113///
114/// // Build the acceleration structure.
115/// let measurements = PathMeasurements::from_path(&path, 1e-3);
116/// let mut sampler = measurements.create_sampler(&path, SampleType::Normalized);
117///
118/// let sample  = sampler.sample(0.5);
119/// println!("Mid-point position: {:?}, tangent: {:?}", sample.position(), sample.tangent());
120///
121/// let mut second_half = Path::builder();
122/// sampler.split_range(0.5..1.0, &mut second_half);
123/// let second_half = second_half.build();
124/// assert!((sampler.length() / 2.0 - approximate_length(&second_half, 1e-3)).abs() < 1e-3);
125/// ```
126///
127pub struct PathMeasurements {
128    events: Vec<IdEvent>,
129    edges: Vec<Edge>,
130}
131
132impl PathMeasurements {
133    /// Create empty path measurements.
134    ///
135    /// The measurements cannot be used until it has been initialized.
136    pub fn empty() -> Self {
137        PathMeasurements {
138            events: Vec::new(),
139            edges: Vec::new(),
140        }
141    }
142
143    /// Create path measurements initialized with a `Path`.
144    pub fn from_path(path: &Path, tolerance: f32) -> Self {
145        let mut m = Self::empty();
146        m.initialize(path.id_iter(), path, tolerance);
147
148        m
149    }
150
151    /// Create path measurements initialized with a `PathSlice`.
152    pub fn from_path_slice(path: &PathSlice, tolerance: f32) -> Self {
153        let mut m = Self::empty();
154        m.initialize(path.id_iter(), path, tolerance);
155
156        m
157    }
158
159    /// Create path measurements initialized with a generic iterator and position store.
160    pub fn from_iter<Iter, PS>(path: Iter, positions: &PS, tolerance: f32) -> Self
161    where
162        Iter: IntoIterator<Item = IdEvent>,
163        PS: PositionStore,
164    {
165        let mut m = Self::empty();
166        m.initialize(path, positions, tolerance);
167
168        m
169    }
170
171    /// Initialize the path measurements with a path.
172    pub fn initialize<Iter, PS>(&mut self, path: Iter, position_store: &PS, tolerance: f32)
173    where
174        Iter: IntoIterator<Item = IdEvent>,
175        PS: PositionStore,
176    {
177        let tolerance = tolerance.max(1e-4);
178        let mut events = core::mem::take(&mut self.events);
179        events.clear();
180        events.extend(path.into_iter());
181        let mut edges = core::mem::take(&mut self.edges);
182        edges.clear();
183
184        let mut distance = 0.0;
185        for (index, event) in events.iter().cloned().enumerate() {
186            match event {
187                IdEvent::Begin { .. } => {
188                    edges.push(Edge {
189                        distance,
190                        index,
191                        t: 1.0,
192                    });
193                }
194                IdEvent::Line { from, to } => {
195                    let from = position_store.get_endpoint(from);
196                    let to = position_store.get_endpoint(to);
197                    distance += (from - to).length();
198                    edges.push(Edge {
199                        distance,
200                        index,
201                        t: 1.0,
202                    })
203                }
204                IdEvent::Quadratic { from, ctrl, to } => {
205                    let from = position_store.get_endpoint(from);
206                    let to = position_store.get_endpoint(to);
207                    let ctrl = position_store.get_control_point(ctrl);
208                    let segment = QuadraticBezierSegment { from, ctrl, to };
209                    segment.for_each_flattened_with_t(tolerance, &mut |line, t| {
210                        distance += line.length();
211                        edges.push(Edge {
212                            distance,
213                            index,
214                            t: t.end,
215                        });
216                    });
217                }
218                IdEvent::Cubic {
219                    from,
220                    ctrl1,
221                    ctrl2,
222                    to,
223                } => {
224                    let from = position_store.get_endpoint(from);
225                    let to = position_store.get_endpoint(to);
226                    let ctrl1 = position_store.get_control_point(ctrl1);
227                    let ctrl2 = position_store.get_control_point(ctrl2);
228                    let segment = CubicBezierSegment {
229                        from,
230                        ctrl1,
231                        ctrl2,
232                        to,
233                    };
234                    segment.for_each_flattened_with_t(tolerance, &mut |line, t| {
235                        distance += line.length();
236                        edges.push(Edge {
237                            distance,
238                            index,
239                            t: t.end,
240                        });
241                    });
242                }
243                IdEvent::End {
244                    last,
245                    first,
246                    close: true,
247                } => {
248                    let last = position_store.get_endpoint(last);
249                    let first = position_store.get_endpoint(first);
250                    distance += (last - first).length();
251                    edges.push(Edge {
252                        distance,
253                        index,
254                        t: 1.0,
255                    })
256                }
257                _ => {}
258            }
259        }
260
261        if !edges.is_empty() {
262            debug_assert_eq!(edges.first().unwrap().distance, 0.0);
263        }
264
265        self.events = events;
266        self.edges = edges;
267    }
268
269    /// Initialize the path measurements with a path.
270    pub fn initialize_with_path(&mut self, path: &Path, tolerance: f32) {
271        self.initialize_with_path_slice(path.as_slice(), tolerance)
272    }
273
274    /// Initialize the path measurements with a path.
275    pub fn initialize_with_path_slice(&mut self, path: PathSlice, tolerance: f32) {
276        self.initialize(path.id_iter(), &path, tolerance)
277    }
278
279    /// Returns the approximate length of the path.
280    pub fn length(&self) -> f32 {
281        if self.edges.is_empty() {
282            0.0
283        } else {
284            self.edges.last().unwrap().distance
285        }
286    }
287
288    /// Create an object that can perform fast sample queries on a path using the cached measurements.
289    ///
290    /// The returned sampler does not compute interpolated attributes.
291    pub fn create_sampler<'l, PS: PositionStore>(
292        &'l self,
293        positions: &'l PS,
294        ty: SampleType,
295    ) -> PathSampler<'l, PS, ()> {
296        let attr: &'static () = &();
297        PathSampler::new(self, positions, attr, ty)
298    }
299
300    /// Create an object that can perform fast sample queries on a path using the cached measurements.
301    ///
302    /// The returned sampler computes interpolated attributes.
303    pub fn create_sampler_with_attributes<'l, PS, AS>(
304        &'l self,
305        positions: &'l PS,
306        attributes: &'l AS,
307        ty: SampleType,
308    ) -> PathSampler<'l, PS, AS>
309    where
310        PS: PositionStore,
311        AS: AttributeStore,
312    {
313        PathSampler::new(self, positions, attributes, ty)
314    }
315}
316
317/// Performs fast sample queries on a path with cached measurements.
318///
319/// This object contains the mutable state necessary for speeding up the queries, this allows the
320/// path measurements to be immutable and accessible concurrently from multiple threads if needed.
321///
322/// Reusing a sampler over multiple queries saves a memory allocation if there are custom attributes,
323/// And speeds up queries if they are sequentially ordered along the path.
324pub struct PathSampler<'l, PS, AS> {
325    events: &'l [IdEvent],
326    edges: &'l [Edge],
327    positions: &'l PS,
328    attributes: &'l AS,
329    attribute_buffer: Vec<f32>,
330    cursor: usize,
331    sample_type: SampleType,
332}
333
334impl<'l, PS: PositionStore, AS: AttributeStore> PathSampler<'l, PS, AS> {
335    /// Create a sampler.
336    ///
337    /// The provided positions must be the ones used when initializing the path measurements.
338    pub fn new(
339        measurements: &'l PathMeasurements,
340        positions: &'l PS,
341        attributes: &'l AS,
342        sample_type: SampleType,
343    ) -> Self {
344        PathSampler {
345            events: &measurements.events,
346            edges: &measurements.edges,
347            positions,
348            attributes,
349            attribute_buffer: alloc::vec![0.0; attributes.num_attributes()],
350            cursor: 0,
351            sample_type,
352        }
353    }
354
355    /// Sample at a given distance along the path.
356    ///
357    /// If the path is empty, the produced sample will contain NaNs.
358    pub fn sample(&mut self, dist: f32) -> PathSample {
359        self.sample_impl(dist, self.sample_type)
360    }
361
362    /// Construct a path for a specific sub-range of the measured path.
363    ///
364    /// The path measurements must have been initialized with the same path.
365    /// The distance is clamped to the beginning and end of the path.
366    /// Panics if the path is empty.
367    pub fn split_range(&mut self, mut range: Range<f32>, output: &mut dyn PathBuilder) {
368        let length = self.length();
369        if self.sample_type == SampleType::Normalized {
370            range.start *= length;
371            range.end *= length;
372        }
373        range.start = range.start.max(0.0);
374        range.end = range.end.max(range.start);
375        range.start = range.start.min(length);
376        range.end = range.end.min(length);
377
378        if range.is_empty() {
379            return;
380        }
381
382        let result = self.sample_impl(range.start, SampleType::Distance);
383        output.begin(result.position, result.attributes);
384        let (ptr1, seg1) = (self.cursor, self.edges[self.cursor].index);
385        self.move_cursor(range.end);
386        let (ptr2, seg2) = (self.cursor, self.edges[self.cursor].index);
387
388        let mut is_in_subpath = true;
389        if seg1 == seg2 {
390            self.cursor = ptr1;
391            let t_begin = self.t(range.start);
392            self.cursor = ptr2;
393            let t_end = self.t(range.end);
394            self.add_segment(seg1, Some(t_begin..t_end), output, &mut is_in_subpath);
395        } else {
396            self.cursor = ptr1;
397            self.add_segment(
398                seg1,
399                Some(self.t(range.start)..1.0),
400                output,
401                &mut is_in_subpath,
402            );
403            for seg in (seg1 + 1)..seg2 {
404                self.add_segment(seg, None, output, &mut is_in_subpath);
405            }
406            self.cursor = ptr2;
407            self.add_segment(
408                seg2,
409                Some(0.0..self.t(range.end)),
410                output,
411                &mut is_in_subpath,
412            );
413        }
414
415        output.end(false);
416    }
417
418    /// Returns the approximate length of the path.
419    pub fn length(&self) -> f32 {
420        if self.edges.is_empty() {
421            0.0
422        } else {
423            self.edges.last().unwrap().distance
424        }
425    }
426
427    fn to_segment(&self, event: IdEvent) -> SegmentWrapper {
428        match event {
429            IdEvent::Line { from, to } => SegmentWrapper::Line(
430                LineSegment {
431                    from: self.positions.get_endpoint(from),
432                    to: self.positions.get_endpoint(to),
433                },
434                (from, to),
435            ),
436            IdEvent::Quadratic { from, ctrl, to } => SegmentWrapper::Quadratic(
437                QuadraticBezierSegment {
438                    from: self.positions.get_endpoint(from),
439                    to: self.positions.get_endpoint(to),
440                    ctrl: self.positions.get_control_point(ctrl),
441                },
442                (from, to),
443            ),
444            IdEvent::Cubic {
445                from,
446                ctrl1,
447                ctrl2,
448                to,
449            } => SegmentWrapper::Cubic(
450                CubicBezierSegment {
451                    from: self.positions.get_endpoint(from),
452                    to: self.positions.get_endpoint(to),
453                    ctrl1: self.positions.get_control_point(ctrl1),
454                    ctrl2: self.positions.get_control_point(ctrl2),
455                },
456                (from, to),
457            ),
458            IdEvent::End {
459                last,
460                first,
461                close: true,
462            } => SegmentWrapper::Line(
463                LineSegment {
464                    from: self.positions.get_endpoint(last),
465                    to: self.positions.get_endpoint(first),
466                },
467                (last, first),
468            ),
469            _ => SegmentWrapper::Empty,
470        }
471    }
472
473    fn in_bounds(&self, dist: f32) -> bool {
474        self.cursor != 0
475            && self.edges[self.cursor - 1].distance <= dist
476            && dist <= self.edges[self.cursor].distance
477    }
478
479    /// Move the pointer so the given point is on the current segment.
480    fn move_cursor(&mut self, dist: f32) {
481        if dist == 0.0 {
482            self.cursor = 1;
483            return;
484        }
485        if self.in_bounds(dist) {
486            // No need to move
487            return;
488        }
489
490        // Performs on [first, last)
491        // ...TTFFF...
492        //      ^
493        //      sample this point
494        fn partition_point(first: usize, last: usize, pred: impl Fn(usize) -> bool) -> usize {
495            let mut l = first;
496            let mut r = last;
497            while l < r {
498                let mid = (l + r) / 2;
499                if pred(mid) {
500                    l = mid + 1;
501                } else {
502                    r = mid;
503                }
504            }
505            debug_assert_eq!(l, r);
506            debug_assert_ne!(l, last);
507            l
508        }
509
510        fn floor_log2(num: usize) -> u32 {
511            core::mem::size_of::<usize>() as u32 * 8 - num.leading_zeros() - 1
512        }
513
514        // Here we use a heuristic method combining method 1 & 2
515        // Method 1:        Move step by step until we found the corresponding segment, works well on short paths and near queries
516        // Time complexity: (expected) (dist - start).abs() / len * num
517        // Method 2.        Binary search on lengths, works well on long paths and random calls
518        // Time complexity: (exact) floor(log2(num))
519        // where `len` and `num` are given as follow
520        //
521        // According to the benchmark, this method works well in both cases and has low overhead in relative to Method 1 & 2.
522        // Benchmark code: https://gist.github.com/Mivik/5f67ae5a72eae3884b2f386370554966
523        let start = self.edges[self.cursor].distance;
524        if start < dist {
525            let (len, num) = (self.length() - start, self.edges.len() - self.cursor - 1);
526            debug_assert_ne!(num, 0);
527            if (dist - start) / len * (num as f32) < floor_log2(num) as f32 {
528                loop {
529                    self.cursor += 1;
530                    if dist <= self.edges[self.cursor].distance {
531                        break;
532                    }
533                }
534            } else {
535                self.cursor = partition_point(self.cursor + 1, self.edges.len(), |p| {
536                    self.edges[p].distance < dist
537                });
538            }
539        } else {
540            let (len, num) = (start, self.cursor + 1);
541            debug_assert_ne!(num, 0);
542            if (start - dist) / len * (num as f32) < floor_log2(num) as f32 {
543                loop {
544                    self.cursor -= 1;
545                    if self.cursor == 0 || self.edges[self.cursor - 1].distance < dist {
546                        break;
547                    }
548                }
549            } else {
550                self.cursor = partition_point(0, self.cursor, |p| self.edges[p].distance < dist);
551            }
552        }
553
554        debug_assert!(self.in_bounds(dist));
555    }
556
557    /// Interpolate the custom attributes.
558    fn interpolate_attributes(&mut self, from: EndpointId, to: EndpointId, t: f32) {
559        let from = self.attributes.get(from);
560        let to = self.attributes.get(to);
561        for i in 0..self.attribute_buffer.len() {
562            self.attribute_buffer[i] = from[i] * (1.0 - t) + to[i] * t;
563        }
564    }
565
566    /// Returns the relative position (0 ~ 1) of the given point on the current segment.
567    fn t(&self, dist: f32) -> f32 {
568        debug_assert!(self.in_bounds(dist));
569        let prev = &self.edges[self.cursor - 1];
570        let cur = &self.edges[self.cursor];
571        let t_begin = if prev.index == cur.index { prev.t } else { 0.0 };
572        let t_end = cur.t;
573        t_begin + (t_end - t_begin) * ((dist - prev.distance) / (cur.distance - prev.distance))
574    }
575
576    fn sample_impl(&mut self, mut dist: f32, sample_type: SampleType) -> PathSample {
577        let length = self.length();
578        if length == 0.0 {
579            return self.sample_zero_length();
580        }
581        if sample_type == SampleType::Normalized {
582            dist *= length;
583        }
584        dist = dist.max(0.0);
585        dist = dist.min(length);
586
587        self.move_cursor(dist);
588        let t = self.t(dist);
589        macro_rules! dispatched_call {
590            ([$v:expr] ($seg:ident, $pair:ident) => $code:block) => {
591                #[allow(unused_parens)]
592                match $v {
593                    SegmentWrapper::Line($seg, $pair) => $code,
594                    SegmentWrapper::Quadratic($seg, $pair) => $code,
595                    SegmentWrapper::Cubic($seg, $pair) => $code,
596                    _ => {}
597                }
598            };
599        }
600
601        dispatched_call!([self.to_segment(self.events[self.edges[self.cursor].index])] (segment, pair) => {
602            self.interpolate_attributes(pair.0, pair.1, t);
603            return PathSample {
604                position: segment.sample(t),
605                tangent: segment.derivative(t).normalize(),
606                attributes: &self.attribute_buffer,
607            }
608        });
609
610        unreachable!();
611    }
612
613    #[cold]
614    fn sample_zero_length(&mut self) -> PathSample {
615        if let Some(IdEvent::Begin { at }) = self.events.first() {
616            return PathSample {
617                position: self.positions.get_endpoint(*at),
618                tangent: vector(0.0, 0.0),
619                attributes: self.attributes.get(*at),
620            };
621        }
622
623        for value in &mut self.attribute_buffer {
624            *value = f32::NAN;
625        }
626
627        PathSample {
628            position: point(f32::NAN, f32::NAN),
629            tangent: vector(f32::NAN, f32::NAN),
630            attributes: &self.attribute_buffer,
631        }
632    }
633
634    /// Caller needs to hold a parameter to keep track of whether we're in a subpath or not, as this would be determined
635    /// by prior segments. This function will update `is_in_subpath` based on the segment it adds.
636    fn add_segment(
637        &mut self,
638        ptr: usize,
639        range: Option<Range<f32>>,
640        dest: &mut dyn PathBuilder,
641        is_in_subpath: &mut bool,
642    ) {
643        let segment = self.to_segment(self.events[ptr]);
644        let segment = match range.clone() {
645            Some(range) => segment.split(range),
646            None => segment,
647        };
648        macro_rules! obtain_attrs {
649            ($p:ident, $index:tt) => {
650                match range.clone() {
651                    Some(range) => {
652                        if range.end == 1.0 {
653                            self.attributes.get($p.$index)
654                        } else {
655                            self.interpolate_attributes($p.0, $p.1, range.end);
656                            &mut self.attribute_buffer
657                        }
658                    }
659                    None => self.attributes.get($p.$index),
660                }
661            };
662        }
663
664        match segment {
665            SegmentWrapper::Line(LineSegment { from, to }, pair) => {
666                if !*is_in_subpath {
667                    dest.end(false);
668                    dest.begin(from, obtain_attrs!(pair, 0));
669                }
670                dest.line_to(to, obtain_attrs!(pair, 1));
671            }
672            SegmentWrapper::Quadratic(QuadraticBezierSegment { from, ctrl, to }, pair) => {
673                if !*is_in_subpath {
674                    dest.end(false);
675                    dest.begin(from, obtain_attrs!(pair, 0));
676                }
677                dest.quadratic_bezier_to(ctrl, to, obtain_attrs!(pair, 1));
678            }
679            SegmentWrapper::Cubic(
680                CubicBezierSegment {
681                    from,
682                    ctrl1,
683                    ctrl2,
684                    to,
685                },
686                pair,
687            ) => {
688                if !*is_in_subpath {
689                    dest.end(false);
690                    dest.begin(from, obtain_attrs!(pair, 0));
691                }
692                dest.cubic_bezier_to(ctrl1, ctrl2, to, obtain_attrs!(pair, 1));
693            }
694            _ => {}
695        }
696
697        *is_in_subpath = !matches!(
698            self.events[ptr],
699            IdEvent::End { .. } | IdEvent::Begin { .. }
700        );
701    }
702}
703
704#[cfg(test)]
705fn slice(a: &[f32]) -> &[f32] {
706    a
707}
708
709#[test]
710fn measure_line() {
711    let mut path = Path::builder();
712    path.begin(point(1.0, 1.0));
713    path.line_to(point(0.0, 0.0));
714    path.end(false);
715    let path = path.build();
716    let measure = PathMeasurements::from_path(&path, 0.01);
717    let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
718    for t in [0.0, 0.2, 0.3, 0.5, 1.0] {
719        let result = sampler.sample(t);
720        assert!((result.position - point(1.0 - t, 1.0 - t)).length() < 1e-5);
721        assert_eq!(result.tangent, vector(-1.0, -1.0).normalize());
722    }
723}
724
725#[test]
726fn measure_square() {
727    let mut path = Path::builder();
728    path.begin(point(0.0, 0.0));
729    path.line_to(point(1.0, 0.0));
730    path.line_to(point(1.0, 1.0));
731    path.line_to(point(0.0, 1.0));
732    path.close();
733    let path = path.build();
734    let measure = PathMeasurements::from_path(&path, 0.01);
735    let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
736    for (t, position, tangent) in [
737        (0.125, point(0.5, 0.0), vector(1.0, 0.0)),
738        (0.375, point(1.0, 0.5), vector(0.0, 1.0)),
739        (0.625, point(0.5, 1.0), vector(-1.0, 0.0)),
740        (0.875, point(0.0, 0.5), vector(0.0, -1.0)),
741    ] {
742        let result = sampler.sample(t);
743        assert!((result.position - position).length() < 1e-5);
744        assert_eq!(result.tangent, tangent);
745    }
746}
747
748#[test]
749fn measure_attributes() {
750    let mut path = Path::builder_with_attributes(2);
751    path.begin(point(0.0, 0.0), &[1.0, 2.0]);
752    path.line_to(point(1.0, 0.0), &[2.0, 3.0]);
753    path.line_to(point(1.0, 1.0), &[0.0, 0.0]);
754    path.end(false);
755    let path = path.build();
756    let measure = PathMeasurements::from_path(&path, 0.01);
757    let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
758
759    for (t, position, attrs) in [
760        (0.25, point(0.5, 0.0), &[1.5, 2.5]),
761        (0.5, point(1.0, 0.0), &[2.0, 3.0]),
762        (0.75, point(1.0, 0.5), &[1.0, 1.5]),
763    ] {
764        let result = sampler.sample(t);
765        assert!((result.position - position).length() < 1e-5);
766        for i in 0..2 {
767            assert!((result.attributes[i] - attrs[i]).abs() < 1e-5);
768        }
769    }
770}
771
772#[test]
773fn measure_bezier_curve() {
774    let mut path = Path::builder();
775    path.begin(point(0.0, 0.0));
776    path.quadratic_bezier_to(point(0.5, 0.7), point(1.0, 0.0));
777    path.quadratic_bezier_to(point(1.5, -0.7), point(2.0, 0.0));
778    path.end(false);
779    let path = path.build();
780
781    let measure = PathMeasurements::from_path(&path, 0.01);
782    let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
783
784    for t in [0.25, 0.75] {
785        let result = sampler.sample(t);
786        assert_eq!(result.tangent, vector(1.0, 0.0));
787    }
788    for (t, position) in [
789        (0.0, point(0.0, 0.0)),
790        (0.5, point(1.0, 0.0)),
791        (1.0, point(2.0, 0.0)),
792    ] {
793        let result = sampler.sample(t);
794        assert_eq!(result.position, position);
795    }
796}
797
798#[test]
799fn split_square() {
800    use crate::path::Event;
801
802    let mut path = Path::builder();
803    path.begin(point(0.0, 0.0));
804    path.line_to(point(1.0, 0.0));
805    path.line_to(point(1.0, 1.0));
806    path.line_to(point(0.0, 1.0));
807    path.close();
808    let path = path.build();
809    let measure = PathMeasurements::from_path(&path, 0.01);
810    let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
811    let mut path2 = Path::builder();
812    sampler.split_range(0.125..0.625, &mut path2);
813    let path2 = path2.build();
814    assert_eq!(
815        path2.iter().collect::<Vec<_>>(),
816        alloc::vec![
817            Event::Begin {
818                at: point(0.5, 0.0)
819            },
820            Event::Line {
821                from: point(0.5, 0.0),
822                to: point(1.0, 0.0)
823            },
824            Event::Line {
825                from: point(1.0, 0.0),
826                to: point(1.0, 1.0)
827            },
828            Event::Line {
829                from: point(1.0, 1.0),
830                to: point(0.5, 1.0)
831            },
832            Event::End {
833                last: point(0.5, 1.0),
834                first: point(0.5, 0.0),
835                close: false
836            },
837        ]
838    );
839}
840
841#[test]
842fn split_bezier_curve() {
843    use crate::path::Event;
844
845    let mut path = Path::builder();
846    path.begin(point(0.0, 0.0));
847    path.quadratic_bezier_to(point(1.0, 1.0), point(2.0, 0.0));
848    path.end(false);
849    let path = path.build();
850    let measure = PathMeasurements::from_path(&path, 0.01);
851    let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
852
853    let mut path2 = Path::builder();
854    sampler.split_range(0.5..1.0, &mut path2);
855    let path2 = path2.build();
856
857    assert_eq!(
858        path2.iter().collect::<Vec<_>>(),
859        alloc::vec![
860            Event::Begin {
861                at: point(1.0, 0.5)
862            },
863            Event::Quadratic {
864                from: point(1.0, 0.5),
865                ctrl: point(1.5, 0.5),
866                to: point(2.0, 0.0),
867            },
868            Event::End {
869                last: point(2.0, 0.0),
870                first: point(1.0, 0.5),
871                close: false
872            }
873        ]
874    );
875}
876
877#[test]
878fn split_attributes() {
879    use crate::path::Event;
880
881    let mut path = Path::builder_with_attributes(2);
882    path.begin(point(0.0, 0.0), &[1.0, 2.0]);
883    path.line_to(point(1.0, 0.0), &[2.0, 3.0]);
884    path.line_to(point(1.0, 1.0), &[0.0, 0.0]);
885    path.end(false);
886    let path = path.build();
887    let measure = PathMeasurements::from_path(&path, 0.01);
888    let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
889
890    let mut path2 = Path::builder_with_attributes(2);
891    sampler.split_range(0.0..1.0, &mut path2);
892    let path2 = path2.build();
893
894    assert_eq!(
895        path2.iter_with_attributes().collect::<Vec<_>>(),
896        path.iter_with_attributes().collect::<Vec<_>>()
897    );
898
899    let mut path3 = Path::builder_with_attributes(2);
900    sampler.split_range(0.25..0.75, &mut path3);
901    let path3 = path3.build();
902
903    assert_eq!(
904        path3.iter_with_attributes().collect::<Vec<_>>(),
905        alloc::vec![
906            Event::Begin {
907                at: (point(0.5, 0.0), slice(&[1.5, 2.5]))
908            },
909            Event::Line {
910                from: (point(0.5, 0.0), slice(&[1.5, 2.5])),
911                to: (point(1.0, 0.0), slice(&[2.0, 3.0])),
912            },
913            Event::Line {
914                from: (point(1.0, 0.0), slice(&[2.0, 3.0])),
915                to: (point(1.0, 0.5), slice(&[1.0, 1.5])),
916            },
917            Event::End {
918                last: (point(1.0, 0.5), slice(&[1.0, 1.5])),
919                first: (point(0.5, 0.0), slice(&[1.5, 2.5])),
920                close: false
921            }
922        ]
923    );
924}
925
926#[test]
927fn zero_length() {
928    fn expect_nans(sample: PathSample, num_attribs: usize) {
929        assert!(sample.position.x.is_nan());
930        assert!(sample.position.y.is_nan());
931        assert!(sample.tangent.x.is_nan());
932        assert!(sample.tangent.y.is_nan());
933        for attr in sample.attributes {
934            assert!(attr.is_nan());
935        }
936        assert_eq!(sample.attributes.len(), num_attribs);
937    }
938
939    let mut path = Path::builder_with_attributes(2);
940    path.begin(point(1.0, 2.0), &[3.0, 4.0]);
941    path.end(false);
942    let path = path.build();
943    let measure = PathMeasurements::from_path(&path, 0.01);
944    let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
945    let expected = PathSample {
946        position: point(1.0, 2.0),
947        tangent: vector(0.0, 0.0),
948        attributes: &[3.0, 4.0],
949    };
950    assert_eq!(sampler.sample(0.0), expected);
951    assert_eq!(sampler.sample(0.5), expected);
952    assert_eq!(sampler.sample(1.0), expected);
953
954    let mut path = Path::builder_with_attributes(2);
955    path.begin(point(1.0, 2.0), &[3.0, 4.0]);
956    path.end(false);
957    let path = path.build();
958    let measure = PathMeasurements::from_path(&path, 0.01);
959    let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Distance);
960    let expected = PathSample {
961        position: point(1.0, 2.0),
962        tangent: vector(0.0, 0.0),
963        attributes: &[3.0, 4.0],
964    };
965    assert_eq!(sampler.sample(0.0), expected);
966    assert_eq!(sampler.sample(0.5), expected);
967    assert_eq!(sampler.sample(1.0), expected);
968
969    let path = Path::builder_with_attributes(2).build();
970    let measure = PathMeasurements::from_path(&path, 0.01);
971    let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
972    expect_nans(sampler.sample(0.0), 2);
973    expect_nans(sampler.sample(0.5), 2);
974    expect_nans(sampler.sample(1.0), 2);
975
976    let path = Path::builder_with_attributes(2).build();
977    let measure = PathMeasurements::from_path(&path, 0.01);
978    let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Distance);
979    expect_nans(sampler.sample(0.0), 2);
980    expect_nans(sampler.sample(0.5), 2);
981    expect_nans(sampler.sample(1.0), 2);
982}
983
984
985#[test]
986fn multiple_sub_paths() {
987    let mut path = Path::builder();
988
989    path.begin(point(0.0, 0.0));
990    path.line_to(point(10.0, 0.0));
991    path.end(false);
992
993    path.begin(point(10.0, 10.0));
994    path.line_to(point(20.0, 10.0));
995    path.end(false);
996
997    let path = path.build();
998    let measure = PathMeasurements::from_path(&path, 0.01);
999    let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
1000
1001    let mut dashes = Path::builder();
1002    sampler.split_range(0.0 .. 0.25, &mut dashes);
1003    sampler.split_range(0.25 .. 0.5, &mut dashes);
1004    // Avoid starting subpaths exactly on the join as we may begin with a zero-length subpath
1005    sampler.split_range(0.6 .. 0.75, &mut dashes);
1006    sampler.split_range(0.75 .. 1.0, &mut dashes);
1007    let dashes = dashes.build();
1008
1009    let mut iter = dashes.iter();
1010
1011    use crate::path::geom::euclid::approxeq::ApproxEq;
1012    fn expect_begin(event: Option<path::PathEvent>, pos: Point) {
1013        std::eprintln!("- {:?}", event);
1014        if let Some(path::PathEvent::Begin { at }) = event {
1015            assert!(at.approx_eq(&pos), "Expected Begin {:?}, got {:?}", pos, at);
1016        } else {
1017            panic!("Expected begin, got {:?}", event);
1018        }    
1019    }
1020
1021    fn expect_end(event: Option<path::PathEvent>, pos: Point) {
1022        std::eprintln!("- {:?}", event);
1023        if let Some(path::PathEvent::End { last, .. }) = event {
1024            assert!(last.approx_eq(&pos), "Expected End {:?}, got {:?}", pos, last);
1025        } else {
1026            panic!("Expected end, got {:?}", event);
1027        }    
1028    }
1029    fn expect_line(event: Option<path::PathEvent>, expect_from: Point, expect_to: Point) {
1030        std::eprintln!("- {:?}", event);
1031        if let Some(path::PathEvent::Line { from, to }) = event {
1032            assert!(from.approx_eq(&expect_from), "Expected line {:?} {:?}, got {:?} {:?}", expect_from, expect_to, from, to);
1033            assert!(to.approx_eq(&expect_to), "Expected line {:?} {:?}, got {:?} {:?}", expect_from, expect_to, from, to);
1034        } else {
1035            panic!("Expected a line {:?} {:?}, got {:?}", expect_from, expect_to, event);
1036        }    
1037    }
1038
1039    expect_begin(iter.next(), point(0.0, 0.0));
1040    expect_line(iter.next(), point(0.0, 0.0), point(5.0, 0.0));
1041    expect_end(iter.next(), point(5.0, 0.0));
1042
1043    expect_begin(iter.next(), point(5.0, 0.0));
1044    expect_line(iter.next(), point(5.0, 0.0), point(10.0, 0.0));
1045    expect_end(iter.next(), point(10.0, 0.0));
1046
1047    expect_begin(iter.next(), point(12.0, 10.0));
1048    expect_line(iter.next(), point(12.0, 10.0), point(15.0, 10.0));
1049    expect_end(iter.next(), point(15.0, 10.0));
1050
1051    expect_begin(iter.next(), point(15.0, 10.0));
1052    expect_line(iter.next(), point(15.0, 10.0), point(20.0, 10.0));
1053    expect_end(iter.next(), point(20.0, 10.0));
1054}