zeno/
traversal.rs

Help
1//! Path traversal algorithms.
2
3use super::command::{Command, TransformCommands};
4use super::geometry::*;
5use super::path_data::PathData;
6use super::segment::{segments, Segment, Segments};
7
8use core::borrow::Borrow;
9use core::cell::RefCell;
10
11/// A vertex of a path.
12#[derive(Copy, Clone, PartialEq, Debug)]
13pub enum Vertex {
14    /// The start point and direction of a subpath.
15    Start(Point, Vector),
16    /// The incoming direction, location, and outgoing direction of an
17    /// intermediate vertex in a subpath.
18    Middle(Vector, Point, Vector),
19    /// The incoming direction and location of the final vertex in a subpath.
20    /// The boolean value is true if the subpath is closed.
21    End(Vector, Point, bool),
22}
23
24/// An iterator over the vertices of a path.
25#[derive(Clone)]
26pub struct Vertices<D> {
27    segments: Segments<D>,
28    prev_point: Point,
29    prev_dir: Vector,
30    is_first: bool,
31}
32
33impl<D> Vertices<D>
34where
35    D: Iterator<Item = Command> + Clone,
36{
37    /// Creates a new iterator over the vertices of a path.
38    pub fn new(data: impl PathData<Commands = D>) -> Self {
39        Self {
40            segments: segments(data.commands(), false),
41            prev_point: Point::ZERO,
42            prev_dir: Vector::new(1., 0.),
43            is_first: true,
44        }
45    }
46}
47
48impl<D> Vertices<TransformCommands<D>>
49where
50    D: Iterator<Item = Command> + Clone,
51{
52    /// Creates a new iterator over the vertices of a transformed path.
53    pub fn with_transform(data: impl PathData<Commands = D>, transform: Transform) -> Self {
54        let data = TransformCommands {
55            data: data.commands(),
56            transform,
57        };
58        Self {
59            segments: segments(data, false),
60            prev_point: Point::ZERO,
61            prev_dir: Vector::new(1., 0.),
62            is_first: true,
63        }
64    }
65}
66
67impl<D> Iterator for Vertices<D>
68where
69    D: Iterator + Clone,
70    D::Item: Borrow<Command>,
71{
72    type Item = Vertex;
73
74    fn next(&mut self) -> Option<Self::Item> {
75        use Segment::*;
76        if self.is_first {
77            self.is_first = false;
78            match self.segments.next()?.borrow() {
79                End(closed) => {
80                    self.is_first = true;
81                    Some(Vertex::End(self.prev_dir, self.prev_point, *closed))
82                }
83                segment => {
84                    let (start, in_dir, out_dir, end) = get_components(segment);
85                    self.prev_dir = out_dir;
86                    self.prev_point = end;
87                    Some(Vertex::Start(start, in_dir))
88                }
89            }
90        } else {
91            match self.segments.next()?.borrow() {
92                End(closed) => {
93                    self.is_first = true;
94                    Some(Vertex::End(self.prev_dir, self.prev_point, *closed))
95                }
96                segment => {
97                    let (start, in_dir, out_dir, end) = get_components(segment);
98                    let prev_dir = self.prev_dir;
99                    self.prev_dir = out_dir;
100                    self.prev_point = end;
101                    Some(Vertex::Middle(prev_dir, start, in_dir))
102                }
103            }
104        }
105    }
106}
107
108fn get_components(segment: &Segment) -> (Point, Vector, Vector, Point) {
109    match segment {
110        Segment::Curve(_, curve) => {
111            let a = curve.evaluate(0.05);
112            let b = curve.evaluate(0.95);
113            let a_dir = (a - curve.a).normalize();
114            let b_dir = (curve.d - b).normalize();
115            (curve.a, a_dir, b_dir, curve.d)
116        }
117        Segment::Line(_, line) => {
118            let dir = (line.b - line.a).normalize();
119            (line.a, dir, dir, line.b)
120        }
121        Segment::End(..) => (Point::ZERO, Vector::ZERO, Vector::ZERO, Point::ZERO),
122    }
123}
124
125/// An iterator like type that walks along a path by arbitrary steps.
126pub struct Walk<D> {
127    init: Segments<D>,
128    iter: Segments<D>,
129    segment: Segment,
130    segment_offset: f32,
131    first: bool,
132    length: RefCell<Option<f32>>,
133    walked: f32,
134}
135
136impl<D> Walk<D>
137where
138    D: Iterator<Item = Command> + Clone,
139{
140    /// Creates a new iterator like type that steps along a path by arbitrary distances.
141    pub fn new(data: impl PathData<Commands = D>) -> Self {
142        let data = data.commands();
143        Self {
144            init: segments(data.clone(), false),
145            iter: segments(data, false),
146            segment: Segment::default(),
147            segment_offset: 0.,
148            first: true,
149            length: RefCell::new(None),
150            walked: 0.,
151        }
152    }
153}
154
155impl<D> Walk<TransformCommands<D>>
156where
157    D: Iterator<Item = Command> + Clone,
158{
159    /// Creates a new iterator like type that steps along a transformed path by arbitrary distances.
160    pub fn with_transform(data: impl PathData<Commands = D>, transform: Transform) -> Self {
161        let data = data.commands();
162        let data = TransformCommands { data, transform };
163        Self {
164            init: segments(data.clone(), false),
165            iter: segments(data, false),
166            segment: Segment::default(),
167            segment_offset: 0.,
168            first: true,
169            length: RefCell::new(None),
170            walked: 0.,
171        }
172    }
173}
174
175impl<D> Walk<D>
176where
177    D: Iterator + Clone,
178    D::Item: Borrow<Command>,
179{
180    /// Steps by the specified distance and returns the point at the new
181    /// location and the normal vector describing the left-ward direction at
182    /// that point. Returns `None` if the distance steps beyond the end
183    /// of the path.
184    pub fn step(&mut self, distance: f32) -> Option<(Point, Vector)> {
185        if self.first {
186            self.segment = self.next_segment()?;
187            self.segment_offset = 0.;
188            self.first = false;
189        }
190        let mut t;
191        let mut offset = self.segment_offset;
192        let mut segment = self.segment;
193        let mut remaining = distance;
194        loop {
195            let dt = segment.time(offset + remaining, 1.);
196            remaining -= dt.distance - offset;
197            t = dt.time;
198            offset = dt.distance;
199            if remaining <= 0. {
200                break;
201            }
202            segment = self.next_segment()?;
203            offset = 0.;
204        }
205        self.segment = segment;
206        self.segment_offset = offset;
207        self.walked += distance;
208        let (p, n) = segment.point_normal(t);
209        Some((p, n))
210    }
211
212    /// Returns the remaining distance available to walk on the path.
213    pub fn remaining(&self) -> f32 {
214        let mut l = self.length.borrow_mut();
215        if l.is_none() {
216            let iter = self.init.clone();
217            let mut sum = 0.;
218            for s in iter {
219                sum += s.length();
220            }
221            *l = Some(sum);
222        }
223        l.unwrap() - self.walked
224    }
225
226    fn next_segment(&mut self) -> Option<Segment> {
227        for s in self.iter.by_ref() {
228            match s {
229                Segment::End(..) => continue,
230                _ => return Some(s),
231            }
232        }
233        None
234    }
235}
zeno/traversal.rs

zeno/
traversal.rs
