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: &LineSegment, pair: &(EndpointId, EndpointId)) => Self::Line(segment.split_range(t_range:range), *pair),
34 Self::Quadratic(segment: &QuadraticBezierSegment, pair: &(EndpointId, EndpointId)) => Self::Quadratic(segment.split_range(t_range:range), *pair),
35 Self::Cubic(segment: &CubicBezierSegment, pair: &(EndpointId, EndpointId)) => Self::Cubic(segment.split_range(t_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 if seg1 == seg2 {
389 self.cursor = ptr1;
390 let t_begin = self.t(range.start);
391 self.cursor = ptr2;
392 let t_end = self.t(range.end);
393 self.add_segment(seg1, Some(t_begin..t_end), output);
394 } else {
395 self.cursor = ptr1;
396 self.add_segment(seg1, Some(self.t(range.start)..1.0), output);
397 for seg in (seg1 + 1)..seg2 {
398 self.add_segment(seg, None, output);
399 }
400 self.cursor = ptr2;
401 self.add_segment(seg2, Some(0.0..self.t(range.end)), output);
402 }
403
404 output.end(false);
405 }
406
407 /// Returns the approximate length of the path.
408 pub fn length(&self) -> f32 {
409 if self.edges.is_empty() {
410 0.0
411 } else {
412 self.edges.last().unwrap().distance
413 }
414 }
415
416 fn to_segment(&self, event: IdEvent) -> SegmentWrapper {
417 match event {
418 IdEvent::Line { from, to } => SegmentWrapper::Line(
419 LineSegment {
420 from: self.positions.get_endpoint(from),
421 to: self.positions.get_endpoint(to),
422 },
423 (from, to),
424 ),
425 IdEvent::Quadratic { from, ctrl, to } => SegmentWrapper::Quadratic(
426 QuadraticBezierSegment {
427 from: self.positions.get_endpoint(from),
428 to: self.positions.get_endpoint(to),
429 ctrl: self.positions.get_control_point(ctrl),
430 },
431 (from, to),
432 ),
433 IdEvent::Cubic {
434 from,
435 ctrl1,
436 ctrl2,
437 to,
438 } => SegmentWrapper::Cubic(
439 CubicBezierSegment {
440 from: self.positions.get_endpoint(from),
441 to: self.positions.get_endpoint(to),
442 ctrl1: self.positions.get_control_point(ctrl1),
443 ctrl2: self.positions.get_control_point(ctrl2),
444 },
445 (from, to),
446 ),
447 IdEvent::End {
448 last,
449 first,
450 close: true,
451 } => SegmentWrapper::Line(
452 LineSegment {
453 from: self.positions.get_endpoint(last),
454 to: self.positions.get_endpoint(first),
455 },
456 (last, first),
457 ),
458 _ => SegmentWrapper::Empty,
459 }
460 }
461
462 fn in_bounds(&self, dist: f32) -> bool {
463 self.cursor != 0
464 && self.edges[self.cursor - 1].distance <= dist
465 && dist <= self.edges[self.cursor].distance
466 }
467
468 /// Move the pointer so the given point is on the current segment.
469 fn move_cursor(&mut self, dist: f32) {
470 if dist == 0.0 {
471 self.cursor = 1;
472 return;
473 }
474 if self.in_bounds(dist) {
475 // No need to move
476 return;
477 }
478
479 // Performs on [first, last)
480 // ...TTFFF...
481 // ^
482 // sample this point
483 fn partition_point(first: usize, last: usize, pred: impl Fn(usize) -> bool) -> usize {
484 let mut l = first;
485 let mut r = last;
486 while l < r {
487 let mid = (l + r) / 2;
488 if pred(mid) {
489 l = mid + 1;
490 } else {
491 r = mid;
492 }
493 }
494 debug_assert_eq!(l, r);
495 debug_assert_ne!(l, last);
496 l
497 }
498
499 fn floor_log2(num: usize) -> u32 {
500 core::mem::size_of::<usize>() as u32 * 8 - num.leading_zeros() - 1
501 }
502
503 // Here we use a heuristic method combining method 1 & 2
504 // Method 1: Move step by step until we found the corresponding segment, works well on short paths and near queries
505 // Time complexity: (expected) (dist - start).abs() / len * num
506 // Method 2. Binary search on lengths, works well on long paths and random calls
507 // Time complexity: (exact) floor(log2(num))
508 // where `len` and `num` are given as follow
509 //
510 // According to the benchmark, this method works well in both cases and has low overhead in relative to Method 1 & 2.
511 // Benchmark code: https://gist.github.com/Mivik/5f67ae5a72eae3884b2f386370554966
512 let start = self.edges[self.cursor].distance;
513 if start < dist {
514 let (len, num) = (self.length() - start, self.edges.len() - self.cursor - 1);
515 debug_assert_ne!(num, 0);
516 if (dist - start) / len * (num as f32) < floor_log2(num) as f32 {
517 loop {
518 self.cursor += 1;
519 if dist <= self.edges[self.cursor].distance {
520 break;
521 }
522 }
523 } else {
524 self.cursor = partition_point(self.cursor + 1, self.edges.len(), |p| {
525 self.edges[p].distance < dist
526 });
527 }
528 } else {
529 let (len, num) = (start, self.cursor + 1);
530 debug_assert_ne!(num, 0);
531 if (start - dist) / len * (num as f32) < floor_log2(num) as f32 {
532 loop {
533 self.cursor -= 1;
534 if self.cursor == 0 || self.edges[self.cursor - 1].distance < dist {
535 break;
536 }
537 }
538 } else {
539 self.cursor = partition_point(0, self.cursor, |p| self.edges[p].distance < dist);
540 }
541 }
542
543 debug_assert!(self.in_bounds(dist));
544 }
545
546 /// Interpolate the custom attributes.
547 fn interpolate_attributes(&mut self, from: EndpointId, to: EndpointId, t: f32) {
548 let from = self.attributes.get(from);
549 let to = self.attributes.get(to);
550 for i in 0..self.attribute_buffer.len() {
551 self.attribute_buffer[i] = from[i] * (1.0 - t) + to[i] * t;
552 }
553 }
554
555 /// Returns the relative position (0 ~ 1) of the given point on the current segment.
556 fn t(&self, dist: f32) -> f32 {
557 debug_assert!(self.in_bounds(dist));
558 let prev = &self.edges[self.cursor - 1];
559 let cur = &self.edges[self.cursor];
560 let t_begin = if prev.index == cur.index { prev.t } else { 0.0 };
561 let t_end = cur.t;
562 t_begin + (t_end - t_begin) * ((dist - prev.distance) / (cur.distance - prev.distance))
563 }
564
565 fn sample_impl(&mut self, mut dist: f32, sample_type: SampleType) -> PathSample {
566 let length = self.length();
567 if length == 0.0 {
568 return self.sample_zero_length();
569 }
570 if sample_type == SampleType::Normalized {
571 dist *= length;
572 }
573 dist = dist.max(0.0);
574 dist = dist.min(length);
575
576 self.move_cursor(dist);
577 let t = self.t(dist);
578 macro_rules! dispatched_call {
579 ([$v:expr] ($seg:ident, $pair:ident) => $code:block) => {
580 #[allow(unused_parens)]
581 match $v {
582 SegmentWrapper::Line($seg, $pair) => $code,
583 SegmentWrapper::Quadratic($seg, $pair) => $code,
584 SegmentWrapper::Cubic($seg, $pair) => $code,
585 _ => {}
586 }
587 };
588 }
589
590 dispatched_call!([self.to_segment(self.events[self.edges[self.cursor].index])] (segment, pair) => {
591 self.interpolate_attributes(pair.0, pair.1, t);
592 return PathSample {
593 position: segment.sample(t),
594 tangent: segment.derivative(t).normalize(),
595 attributes: &self.attribute_buffer,
596 }
597 });
598
599 unreachable!();
600 }
601
602 #[cold]
603 fn sample_zero_length(&mut self) -> PathSample {
604 if let Some(IdEvent::Begin { at }) = self.events.first() {
605 return PathSample {
606 position: self.positions.get_endpoint(*at),
607 tangent: vector(0.0, 0.0),
608 attributes: self.attributes.get(*at),
609 };
610 }
611
612 for value in &mut self.attribute_buffer {
613 *value = f32::NAN;
614 }
615
616 PathSample {
617 position: point(f32::NAN, f32::NAN),
618 tangent: vector(f32::NAN, f32::NAN),
619 attributes: &self.attribute_buffer,
620 }
621 }
622
623 fn add_segment(&mut self, ptr: usize, range: Option<Range<f32>>, dest: &mut dyn PathBuilder) {
624 let segment = self.to_segment(self.events[ptr]);
625 let segment = match range.clone() {
626 Some(range) => segment.split(range),
627 None => segment,
628 };
629 macro_rules! obtain_attrs {
630 ($p:ident) => {
631 match range {
632 Some(range) => {
633 if range.end == 1.0 {
634 self.attributes.get($p.1)
635 } else {
636 self.interpolate_attributes($p.0, $p.1, range.end);
637 &mut self.attribute_buffer
638 }
639 }
640 None => self.attributes.get($p.1),
641 }
642 };
643 }
644
645 match segment {
646 SegmentWrapper::Line(LineSegment { to, .. }, pair) => {
647 dest.line_to(to, obtain_attrs!(pair));
648 }
649 SegmentWrapper::Quadratic(QuadraticBezierSegment { ctrl, to, .. }, pair) => {
650 dest.quadratic_bezier_to(ctrl, to, obtain_attrs!(pair));
651 }
652 SegmentWrapper::Cubic(
653 CubicBezierSegment {
654 ctrl1, ctrl2, to, ..
655 },
656 pair,
657 ) => {
658 dest.cubic_bezier_to(ctrl1, ctrl2, to, obtain_attrs!(pair));
659 }
660 _ => {}
661 }
662 }
663}
664
665#[cfg(test)]
666fn slice(a: &[f32]) -> &[f32] {
667 a
668}
669
670#[test]
671fn measure_line() {
672 let mut path: NoAttributes = Path::builder();
673 path.begin(at:point(x:1.0, y:1.0));
674 path.line_to(point(x:0.0, y:0.0));
675 path.end(close:false);
676 let path: Path = path.build();
677 let measure: PathMeasurements = PathMeasurements::from_path(&path, tolerance:0.01);
678 let mut sampler: PathSampler<'_, Path, ()> = measure.create_sampler(&path, ty:SampleType::Normalized);
679 for t: f32 in [0.0, 0.2, 0.3, 0.5, 1.0] {
680 let result: PathSample<'_> = sampler.sample(dist:t);
681 assert!((result.position - point(1.0 - t, 1.0 - t)).length() < 1e-5);
682 assert_eq!(result.tangent, vector(-1.0, -1.0).normalize());
683 }
684}
685
686#[test]
687fn measure_square() {
688 let mut path: NoAttributes = Path::builder();
689 path.begin(at:point(x:0.0, y:0.0));
690 path.line_to(point(x:1.0, y:0.0));
691 path.line_to(point(x:1.0, y:1.0));
692 path.line_to(point(x:0.0, y:1.0));
693 path.close();
694 let path: Path = path.build();
695 let measure: PathMeasurements = PathMeasurements::from_path(&path, tolerance:0.01);
696 let mut sampler: PathSampler<'_, Path, ()> = measure.create_sampler(&path, ty:SampleType::Normalized);
697 for (t: f32, position: Point2D, tangent: Vector2D) in [
698 (0.125, point(x:0.5, y:0.0), vector(x:1.0, y:0.0)),
699 (0.375, point(x:1.0, y:0.5), vector(x:0.0, y:1.0)),
700 (0.625, point(x:0.5, y:1.0), vector(x:-1.0, y:0.0)),
701 (0.875, point(x:0.0, y:0.5), vector(x:0.0, y:-1.0)),
702 ] {
703 let result: PathSample<'_> = sampler.sample(dist:t);
704 assert!((result.position - position).length() < 1e-5);
705 assert_eq!(result.tangent, tangent);
706 }
707}
708
709#[test]
710fn measure_attributes() {
711 let mut path: BuilderWithAttributes = Path::builder_with_attributes(num_attributes:2);
712 path.begin(at:point(0.0, 0.0), &[1.0, 2.0]);
713 path.line_to(to:point(1.0, 0.0), &[2.0, 3.0]);
714 path.line_to(to:point(1.0, 1.0), &[0.0, 0.0]);
715 path.end(close:false);
716 let path: Path = path.build();
717 let measure: PathMeasurements = PathMeasurements::from_path(&path, tolerance:0.01);
718 let mut sampler: PathSampler<'_, Path, Path> = measure.create_sampler_with_attributes(&path, &path, ty:SampleType::Normalized);
719
720 for (t: f32, position: Point2D, attrs: &[f32; 2]) in [
721 (0.25, point(x:0.5, y:0.0), &[1.5, 2.5]),
722 (0.5, point(x:1.0, y:0.0), &[2.0, 3.0]),
723 (0.75, point(x:1.0, y:0.5), &[1.0, 1.5]),
724 ] {
725 let result: PathSample<'_> = sampler.sample(dist:t);
726 assert!((result.position - position).length() < 1e-5);
727 for i: usize in 0..2 {
728 assert!((result.attributes[i] - attrs[i]).abs() < 1e-5);
729 }
730 }
731}
732
733#[test]
734fn measure_bezier_curve() {
735 let mut path: NoAttributes = Path::builder();
736 path.begin(at:point(x:0.0, y:0.0));
737 path.quadratic_bezier_to(ctrl:point(0.5, 0.7), to:point(x:1.0, y:0.0));
738 path.quadratic_bezier_to(ctrl:point(1.5, -0.7), to:point(x:2.0, y:0.0));
739 path.end(close:false);
740 let path: Path = path.build();
741
742 let measure: PathMeasurements = PathMeasurements::from_path(&path, tolerance:0.01);
743 let mut sampler: PathSampler<'_, Path, ()> = measure.create_sampler(&path, ty:SampleType::Normalized);
744
745 for t: f32 in [0.25, 0.75] {
746 let result: PathSample<'_> = sampler.sample(dist:t);
747 assert_eq!(result.tangent, vector(1.0, 0.0));
748 }
749 for (t: f32, position: Point2D) in [
750 (0.0, point(x:0.0, y:0.0)),
751 (0.5, point(x:1.0, y:0.0)),
752 (1.0, point(x:2.0, y:0.0)),
753 ] {
754 let result: PathSample<'_> = sampler.sample(dist:t);
755 assert_eq!(result.position, position);
756 }
757}
758
759#[test]
760fn split_square() {
761 use crate::path::Event;
762
763 let mut path = Path::builder();
764 path.begin(point(0.0, 0.0));
765 path.line_to(point(1.0, 0.0));
766 path.line_to(point(1.0, 1.0));
767 path.line_to(point(0.0, 1.0));
768 path.close();
769 let path = path.build();
770 let measure = PathMeasurements::from_path(&path, 0.01);
771 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
772 let mut path2 = Path::builder();
773 sampler.split_range(0.125..0.625, &mut path2);
774 let path2 = path2.build();
775 assert_eq!(
776 path2.iter().collect::<Vec<_>>(),
777 alloc::vec![
778 Event::Begin {
779 at: point(0.5, 0.0)
780 },
781 Event::Line {
782 from: point(0.5, 0.0),
783 to: point(1.0, 0.0)
784 },
785 Event::Line {
786 from: point(1.0, 0.0),
787 to: point(1.0, 1.0)
788 },
789 Event::Line {
790 from: point(1.0, 1.0),
791 to: point(0.5, 1.0)
792 },
793 Event::End {
794 last: point(0.5, 1.0),
795 first: point(0.5, 0.0),
796 close: false
797 },
798 ]
799 );
800}
801
802#[test]
803fn split_bezier_curve() {
804 use crate::path::Event;
805
806 let mut path = Path::builder();
807 path.begin(point(0.0, 0.0));
808 path.quadratic_bezier_to(point(1.0, 1.0), point(2.0, 0.0));
809 path.end(false);
810 let path = path.build();
811 let measure = PathMeasurements::from_path(&path, 0.01);
812 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
813
814 let mut path2 = Path::builder();
815 sampler.split_range(0.5..1.0, &mut path2);
816 let path2 = path2.build();
817
818 assert_eq!(
819 path2.iter().collect::<Vec<_>>(),
820 alloc::vec![
821 Event::Begin {
822 at: point(1.0, 0.5)
823 },
824 Event::Quadratic {
825 from: point(1.0, 0.5),
826 ctrl: point(1.5, 0.5),
827 to: point(2.0, 0.0),
828 },
829 Event::End {
830 last: point(2.0, 0.0),
831 first: point(1.0, 0.5),
832 close: false
833 }
834 ]
835 );
836}
837
838#[test]
839fn split_attributes() {
840 use crate::path::Event;
841
842 let mut path = Path::builder_with_attributes(2);
843 path.begin(point(0.0, 0.0), &[1.0, 2.0]);
844 path.line_to(point(1.0, 0.0), &[2.0, 3.0]);
845 path.line_to(point(1.0, 1.0), &[0.0, 0.0]);
846 path.end(false);
847 let path = path.build();
848 let measure = PathMeasurements::from_path(&path, 0.01);
849 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
850
851 let mut path2 = Path::builder_with_attributes(2);
852 sampler.split_range(0.0..1.0, &mut path2);
853 let path2 = path2.build();
854
855 assert_eq!(
856 path2.iter_with_attributes().collect::<Vec<_>>(),
857 path.iter_with_attributes().collect::<Vec<_>>()
858 );
859
860 let mut path3 = Path::builder_with_attributes(2);
861 sampler.split_range(0.25..0.75, &mut path3);
862 let path3 = path3.build();
863
864 assert_eq!(
865 path3.iter_with_attributes().collect::<Vec<_>>(),
866 alloc::vec![
867 Event::Begin {
868 at: (point(0.5, 0.0), slice(&[1.5, 2.5]))
869 },
870 Event::Line {
871 from: (point(0.5, 0.0), slice(&[1.5, 2.5])),
872 to: (point(1.0, 0.0), slice(&[2.0, 3.0])),
873 },
874 Event::Line {
875 from: (point(1.0, 0.0), slice(&[2.0, 3.0])),
876 to: (point(1.0, 0.5), slice(&[1.0, 1.5])),
877 },
878 Event::End {
879 last: (point(1.0, 0.5), slice(&[1.0, 1.5])),
880 first: (point(0.5, 0.0), slice(&[1.5, 2.5])),
881 close: false
882 }
883 ]
884 );
885}
886
887#[test]
888fn zero_length() {
889 fn expect_nans(sample: PathSample, num_attribs: usize) {
890 assert!(sample.position.x.is_nan());
891 assert!(sample.position.y.is_nan());
892 assert!(sample.tangent.x.is_nan());
893 assert!(sample.tangent.y.is_nan());
894 for attr in sample.attributes {
895 assert!(attr.is_nan());
896 }
897 assert_eq!(sample.attributes.len(), num_attribs);
898 }
899
900 let mut path = Path::builder_with_attributes(2);
901 path.begin(point(1.0, 2.0), &[3.0, 4.0]);
902 path.end(false);
903 let path = path.build();
904 let measure = PathMeasurements::from_path(&path, 0.01);
905 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
906 let expected = PathSample {
907 position: point(1.0, 2.0),
908 tangent: vector(0.0, 0.0),
909 attributes: &[3.0, 4.0],
910 };
911 assert_eq!(sampler.sample(0.0), expected);
912 assert_eq!(sampler.sample(0.5), expected);
913 assert_eq!(sampler.sample(1.0), expected);
914
915 let mut path = Path::builder_with_attributes(2);
916 path.begin(point(1.0, 2.0), &[3.0, 4.0]);
917 path.end(false);
918 let path = path.build();
919 let measure = PathMeasurements::from_path(&path, 0.01);
920 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Distance);
921 let expected = PathSample {
922 position: point(1.0, 2.0),
923 tangent: vector(0.0, 0.0),
924 attributes: &[3.0, 4.0],
925 };
926 assert_eq!(sampler.sample(0.0), expected);
927 assert_eq!(sampler.sample(0.5), expected);
928 assert_eq!(sampler.sample(1.0), expected);
929
930 let path = Path::builder_with_attributes(2).build();
931 let measure = PathMeasurements::from_path(&path, 0.01);
932 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
933 expect_nans(sampler.sample(0.0), 2);
934 expect_nans(sampler.sample(0.5), 2);
935 expect_nans(sampler.sample(1.0), 2);
936
937 let path = Path::builder_with_attributes(2).build();
938 let measure = PathMeasurements::from_path(&path, 0.01);
939 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Distance);
940 expect_nans(sampler.sample(0.0), 2);
941 expect_nans(sampler.sample(0.5), 2);
942 expect_nans(sampler.sample(1.0), 2);
943}
944