charred_path/
piecewise_linear.rs

1use bevy::prelude::*;
2use std::{cmp::Ordering, sync::Arc, time::Duration};
3
4/// Adds systems for updating the path timer and updating the position of entities along the path.
5pub struct PathPlugin;
6
7impl Plugin for PathPlugin {
8    fn build(&self, app: &mut App) {
9        app.add_systems(Update, (tick_path_timer, update_entity_position))
10            .insert_resource(PathTimer::default());
11    }
12}
13
14/// Plugin for debugging paths.
15/// Adds a system for rendering paths to the screen using Bevy's 2d primitives.
16pub struct PathDebugPlugin;
17
18impl Plugin for PathDebugPlugin {
19    fn build(&self, app: &mut App) {
20        app.add_systems(Update, debug_render_paths);
21    }
22}
23
24/// Checks if the prior node should be removed. Returns true if it should be removed.
25fn should_remove(p1: &Vec2, p2: &Vec2, p3: &Vec2, puncture_points: &[PuncturePoint]) -> bool {
26    puncture_points.iter().all(|p| p.should_remove(p1, p2, p3))
27}
28
29/// Resource struct representing a timer for path updates.
30#[derive(Resource)]
31pub struct PathTimer {
32    pub timer: Timer,
33}
34
35impl Default for PathTimer {
36    fn default() -> Self {
37        Self {
38            timer: Timer::new(Duration::from_millis(250), TimerMode::Repeating),
39        }
40    }
41}
42
43/// Updates the path timer.
44fn tick_path_timer(mut path_timer: ResMut<PathTimer>, time: Res<Time>) {
45    path_timer.timer.tick(time.delta());
46}
47
48/// Updates the position of entities along the path.
49fn update_entity_position(
50    mut path_query: Query<(&mut PathType, &Transform)>,
51    // path_timer: Res<PathTimer>,
52) {
53    // if path_timer.timer.just_finished() {
54    for (mut path_type, transform) in path_query.iter_mut() {
55        let current_position = transform.translation.truncate();
56        if &current_position != path_type.current_path.end() {
57            path_type.push(&current_position);
58        }
59    }
60    // }
61}
62
63/// `PuncturePoint` represents a hole in the plane from the perspective of homotopy.
64///
65/// A `PuncturePoint` is a point in the plane that acts as a puncture or hole, affecting the homotopy type
66/// of paths traveling around it.
67///
68/// Each `PuncturePoint` contains a `position` which is a `Vec2` representing the position of the point,
69/// and a `name` which is a `char` that uniquely identifies the puncture point. It is used to represent
70/// the traversal around the puncture point when writing the homotopy type of a path. `name.to_ascii_lowercase()`
71/// is used to represent clockwise traversal around the puncture point, and `name.to_ascii_uppercase()` is used
72/// to represent counterclockwise traversal.
73///
74/// Note that the name character is made uppercase upon instantiation.
75///
76/// # Examples
77///
78/// ```
79/// use bevy::prelude::*;
80/// use charred_path::piecewise_linear::PuncturePoint;
81///
82/// let position = Vec2::new(1.0, 2.0);
83/// let puncture_point = PuncturePoint::new(position, 'a');
84/// assert_eq!(puncture_point.position(), &position);
85/// assert_eq!(puncture_point.name(), 'A');
86/// ```
87#[derive(Debug, Clone, Copy, PartialEq, Component)]
88pub struct PuncturePoint {
89    position: Vec2,
90    name: char,
91}
92
93impl PuncturePoint {
94    /// Represents a puncture point in the plane.
95    pub const fn new(position: Vec2, name: char) -> Self {
96        Self {
97            position,
98            name: name.to_ascii_uppercase(),
99        }
100    }
101
102    /// Returns the position of the puncture point in 2D.
103    pub const fn position(&self) -> &Vec2 {
104        &self.position
105    }
106
107    /// Returns the label associated to the puncture point.
108    pub const fn name(&self) -> char {
109        self.name
110    }
111
112    /// Checks if the puncture point is inside a triangle defined by three points.
113    fn is_in_triangle(&self, p1: &Vec2, p2: &Vec2, p3: &Vec2) -> bool {
114        let p = self.position();
115        let denom = (p2.y - p3.y).mul_add(p1.x - p3.x, (p3.x - p2.x) * (p1.y - p3.y));
116        if denom.abs() <= f32::EPSILON {
117            return false;
118        }
119        let a = (p2.y - p3.y).mul_add(p.x - p3.x, (p3.x - p2.x) * (p.y - p3.y)) / denom;
120        let b = (p3.y - p1.y).mul_add(p.x - p3.x, (p1.x - p3.x) * (p.y - p3.y)) / denom;
121        let c = 1.0 - a - b;
122        [a, b, c].iter().all(|x| (0.0..1.0).contains(x))
123    }
124
125    /// Checks if the puncture point should be removed based on its position relative to a triangle.
126    fn should_remove(&self, p1: &Vec2, p2: &Vec2, p3: &Vec2) -> bool {
127        let x = self.position().x;
128        !(self.is_in_triangle(p1, p2, p3)
129            || ((p1.x..p2.x).contains(&x) && p2.x < p3.x && (x - p2.x).abs() < 1e-3)
130            || ((p2.x..p1.x).contains(&x) && p3.x < p2.x && (x - p2.x).abs() < 1e-3))
131        // || (*self.position() - *p2).length_squared() < 5.0 && (*self.position() - *p3).length_squared() < 20.0
132    }
133
134    /// Updates the winding of the puncture point based on its position relative to a line segment.
135    ///
136    /// Returns `Some(1)` if the line passes left -> right above the point,
137    /// `Some(-1)` if the line passes right -> left above the point, and
138    /// `None` otherwise.
139    fn winding_update(&self, start: &Vec2, end: &Vec2) -> Option<i32> {
140        let position = self.position();
141        let cross_product = (end.y - start.y).mul_add(
142            position.x - start.x,
143            -((position.y - start.y) * (end.x - start.x)),
144        );
145        // Check if position is below the line segment
146        if cross_product > 0. && (start.x..end.x).contains(&position.x) {
147            return Some(1);
148        }
149        if cross_product < 0. && (end.x..start.x).contains(&position.x) {
150            return Some(-1);
151        }
152        None
153    }
154}
155
156#[derive(Debug, Clone, PartialEq, Component)]
157pub struct PLPath {
158    nodes: Vec<Vec2>,
159}
160
161impl PLPath {
162    /// Gets the first node, if there is one.
163    ///
164    /// ## Panics
165    /// This will panic if `nodes` is empty.
166    fn start(&self) -> &Vec2 {
167        self.nodes.first().expect("Couldn't get the start point")
168    }
169
170    /// Gets the last node, if there is one.
171    ///
172    /// ## Panics
173    /// This will panic if `nodes` is empty.
174    fn end(&self) -> &Vec2 {
175        self.nodes.last().expect("Couldn't get the end point")
176    }
177
178    ///
179    fn push(&mut self, position: &Vec2) {
180        self.nodes.push(*position);
181    }
182    /// Appends the XY-position of a Transform
183    pub fn push_transform(&mut self, transform: Transform) {
184        self.nodes.push(transform.translation.truncate());
185    }
186
187    /// A new path from a list of nodes.
188    pub fn new(nodes: impl Into<Vec<Vec2>>) -> Self {
189        Self {
190            nodes: nodes.into(),
191        }
192    }
193
194    /// A straight line path from start to end.
195    pub fn line(start: Vec2, end: Vec2) -> Self {
196        Self {
197            nodes: vec![start, end],
198        }
199    }
200
201    /// Path whose nodes are reversed from `self.nodes`.
202    pub fn reverse(&self) -> Self {
203        let mut reversed_nodes = self.nodes.clone();
204        reversed_nodes.reverse();
205        Self {
206            nodes: reversed_nodes,
207        }
208    }
209
210    /// Returns a PLPath whose nodes are `self.nodes` concatenated by `other.nodes`.
211    pub fn concatenate(&self, other: &Self) -> Self {
212        let mut nodes = self.nodes.clone();
213        nodes.extend(other.nodes.clone());
214        Self { nodes }
215    }
216
217    /// An iterable containing each linear component of the path as a Segment2d.
218    /// Used to display the PL path as a loop for debugging purposes.
219    fn to_segment2d_iter(&self) -> impl Iterator<Item = (Segment2d, Vec2)> + '_ {
220        let last = if self.start() != self.end() {
221            Some(Segment2d::from_points(*self.end(), *self.start()))
222        } else {
223            None
224        };
225        self.nodes
226            .windows(2)
227            .filter_map(|pair| {
228                let point1 = pair[0];
229                let point2 = pair[1];
230                if point1 == point2 {
231                    None
232                } else {
233                    let segment = Segment2d::from_points(point1, point2);
234                    Some(segment)
235                }
236            })
237            .chain(last)
238    }
239}
240
241/// Represents the homotopy type of a path in a punctured plane.
242///
243/// The `PathType` struct encapsulates the current path, puncture points, and the word representation
244/// of the homotopy type. It provides methods to update the path and retrieve the word representation.
245///
246/// # Fields
247///
248/// - `current_path`: The current path represented as a `PLPath` (piecewise linear path).
249/// - `puncture_points`: A shared reference to an array of `PuncturePoint` objects representing the puncture points in the plane.
250/// - `word`: The word representation of the homotopy type, which is automatically updated whenever the path is modified.
251///
252/// # Examples
253///
254/// ```
255/// use your_library::{PathType, PLPath, PuncturePoint};
256/// use std::sync::Arc;
257///
258/// let puncture_points = vec![
259///     PuncturePoint { position: (0.0, 0.0), name: 'A' },
260///     PuncturePoint { position: (1.0, 1.0), name: 'B' },
261/// ];
262/// let puncture_points = Arc::new(puncture_points);
263///
264/// let initial_path = PLPath::new();
265/// let mut path_type = PathType {
266///     current_path: initial_path,
267///     puncture_points,
268///     word: String::new(),
269/// };
270///
271/// // Update the path
272/// let new_path = PLPath::from_points(&[(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)]);
273/// path_type.update_path(new_path);
274///
275/// // Get the updated word representation
276/// println!("Word representation: {}", path_type.word());
277/// ```
278#[derive(Debug, Clone, Component)]
279pub struct PathType {
280    current_path: PLPath,
281    puncture_points: Arc<[PuncturePoint]>,
282    word: String,
283}
284
285impl PathType {
286    pub fn word_as_str(&self) -> &str {
287        &self.word
288    }
289    pub fn word(&self) -> String {
290        self.word.clone()
291    }
292
293    pub fn new(start: Vec2, puncture_points: Vec<PuncturePoint>) -> Self {
294        Self {
295            current_path: PLPath::new(vec![start]),
296            puncture_points: puncture_points.into(),
297            word: String::new(),
298        }
299    }
300
301    pub fn from_path(path: PLPath, puncture_points: Arc<[PuncturePoint]>) -> Self {
302        let mut path_type = Self {
303            current_path: path,
304            puncture_points,
305            word: String::new(),
306        };
307        path_type.update_word();
308        path_type
309    }
310
311    #[must_use]
312    pub fn concatenate(&self, other: &PLPath) -> Self {
313        Self::from_path(
314            self.current_path.concatenate(other),
315            self.puncture_points.clone(),
316        )
317    }
318
319    fn pop(&mut self) -> Option<Vec2> {
320        self.current_path.nodes.pop()
321    }
322
323    /// Appends a 2d position to the end of the current path.
324    pub fn push(&mut self, point: &Vec2) {
325        if let [.., p1, p2] = &self.current_path.nodes[..] {
326            if should_remove(p1, p2, point, &self.puncture_points) {
327                self.pop();
328                self.push(point);
329            } else {
330                self.current_path.push(point);
331            }
332        } else {
333            self.current_path.push(point);
334        }
335        self.update_word();
336    }
337
338    /// Updates the word representing the homotopy type of the path.
339    /// Returns the updated word.
340    pub fn update_word(&mut self) -> String {
341        let mut word = String::new();
342        let full_loop: Vec<&Vec2> = self
343            .current_path
344            .nodes
345            .iter()
346            .chain(std::iter::once(self.current_path.start()))
347            .collect();
348        for segment in full_loop.windows(2) {
349            let (start, end) = (segment[0], segment[1]);
350            let punctures: Vec<&PuncturePoint> = match start.x.partial_cmp(&end.x) {
351                Some(Ordering::Less) => self.puncture_points.iter().collect(),
352                Some(Ordering::Greater) => self
353                    .puncture_points
354                    .iter()
355                    //.rev()
356                    .collect(),
357                _ => continue,
358            };
359            for puncture in punctures {
360                if let Some(n) = puncture.winding_update(start, end) {
361                    match n {
362                        1 => word.push(puncture.name.to_ascii_lowercase()),
363                        -1 => word.push(puncture.name.to_ascii_uppercase()),
364                        _ => {}
365                    }
366                }
367            }
368        }
369
370        simplify_word(&mut word);
371        self.word = word.clone();
372        word
373    }
374}
375
376fn simplify_word(word: &mut String) {
377    let mut i = 0;
378    while i + 1 < word.len() {
379        let a = word.as_bytes()[i] as char;
380        let b = word.as_bytes()[i + 1] as char;
381
382        if a.to_ascii_uppercase() == b.to_ascii_uppercase() && a != b {
383            word.drain(i..i + 2);
384            i = i.saturating_sub(1);
385        } else {
386            i += 1;
387        }
388    }
389}
390
391/// This visualizes the piecewise-linear paths.
392fn debug_render_paths(path_types: Query<&PathType>, mut gizmos: Gizmos) {
393    for path_type in path_types.iter() {
394        if path_type.current_path.nodes.len() > 1 {
395            for segment in path_type.current_path.to_segment2d_iter() {
396                gizmos.primitive_2d(segment.0, segment.1, 0.0, Color::WHITE);
397            }
398        }
399    }
400}
401
402#[cfg(test)]
403mod tests {
404    use super::*;
405
406    #[test]
407    fn test_is_point_in_triangle() {
408        let p1 = &Vec2::new(0.0, 0.0);
409        let p2 = &Vec2::new(4.0, 0.0);
410        let p3 = &Vec2::new(2.0, 4.0);
411
412        let puncture_point_inside = PuncturePoint::new(*p1, 'A');
413        let puncture_point_inside_2 = PuncturePoint::new(*p2, 'B');
414        let puncture_point_outside = PuncturePoint::new(*p3, 'A');
415
416        assert!(puncture_point_inside.is_in_triangle(p1, p2, p3));
417        assert!(puncture_point_inside_2.is_in_triangle(p1, p2, p3));
418        assert!(!puncture_point_outside.is_in_triangle(p1, p2, p3));
419    }
420
421    #[test]
422    fn test_simplify_word_with_multibyte_chars() {
423        let mut word = "ßAa".to_string();
424        simplify_word(&mut word);
425        assert_eq!(word, "ß");
426    }
427}
charred_path/piecewise_linear.rs

charred_path/
piecewise_linear.rs
