visioncortex/path/
paths.rs

1use std::fmt::{Debug, Write};
2use std::ops::{Add, AddAssign, Index, IndexMut, Mul, Range, RangeFrom, RangeInclusive, Sub};
3
4use crate::{BinaryImage, Point2, PointF64, PointI32, Shape, ToSvgString};
5use super::{PathSimplify, PathSimplifyMode, PathWalker, smooth::SubdivideSmooth, reduce::reduce};
6
7#[derive(Clone, Debug, Default)]
8/// Path of generic points in 2D space
9pub struct Path<T> {
10    /// T can be PointI32/PointF64, etc. (see src/point.rs).
11    pub path: Vec<T>,
12}
13
14/// Path of 2D PointI32
15pub type PathI32 = Path<PointI32>;
16/// Path of 2D PointF64
17pub type PathF64 = Path<PointF64>;
18
19impl<T> Path<T>
20{
21    /// Creates a new 2D Path with no points
22    pub fn new() -> Self {
23        Self {
24            path: vec![]
25        }
26    }
27
28    /// Creates a 2D Path with 'points' as its points
29    pub fn from_points(points: Vec<T>) -> Self {
30        Self {
31            path: points
32        }
33    }
34
35    /// Adds a point to the end of the path
36    pub fn add(&mut self, point: T) {
37        self.path.push(point);
38    }
39
40    /// Removes the last point from the path and returns it, or None if it is empty.
41    pub fn pop(&mut self) -> Option<T> {
42        self.path.pop()
43    }
44
45    /// Returns an iterator on the vector of points in the path
46    pub fn iter(&self) -> std::slice::Iter<'_, T> {
47        self.path.iter()
48    }
49
50    /// Returns the number of points in the path
51    pub fn len(&self) -> usize {
52        self.path.len()
53    }
54
55    /// Returns true if the path is empty, false otherwise
56    pub fn is_empty(&self) -> bool {
57        self.len() == 0
58    }
59}
60
61impl<T> Index<usize> for Path<T>
62{
63    type Output = T;
64
65    fn index(&self, index: usize) -> &Self::Output {
66        &self.path[index]
67    }
68}
69
70impl<T> IndexMut<usize> for Path<T>
71{
72    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
73        &mut self.path[index]
74    }
75}
76
77impl<T> Index<Range<usize>> for Path<T>
78{
79    type Output = [T];
80
81    fn index(&self, index: Range<usize>) -> &Self::Output {
82        &self.path[index]
83    }
84}
85
86impl<T> Index<RangeInclusive<usize>> for Path<T>
87{
88    type Output = [T];
89
90    fn index(&self, index: RangeInclusive<usize>) -> &Self::Output {
91        &self.path[index]
92    }
93}
94
95impl<T> Index<RangeFrom<usize>> for Path<T>
96{
97    type Output = [T];
98
99    fn index(&self, index: RangeFrom<usize>) -> &Self::Output {
100        &self.path[index]
101    }
102}
103
104impl<T> Path<T>
105where
106    T: Clone + PartialEq
107{
108    /// Convert a closed path to an open path.
109    /// A clone of 'self' is returned untouched if 'self' is empty or open.
110    pub fn to_open(&self) -> Self {
111        if self.is_empty() {
112            return self.clone();
113        }
114        
115        let len = self.len();
116        if self.path[0] != self.path[len-1] {
117            self.clone()
118        } else {
119            Self::from_points(self.path[0..(len-1)].to_vec())
120        }
121    }
122
123    /// Convert an unclosed path to a closed path.
124    /// A clone of 'self' is returned untouched if 'self' is empty or closed.
125    pub fn to_closed(&self) -> Self {
126        if self.is_empty() {
127            return self.clone();
128        }
129
130        let len = self.len();
131        if self.path[0] == self.path[len-1] {
132            self.clone()
133        } else {
134            let mut points = self.path.clone();
135            points.push(self.path[0].clone());
136            Self::from_points(points)
137        }
138    }
139}
140
141impl<T> Path<T>
142where
143    T: AddAssign + Copy
144{
145    /// Applies an offset to all points in the path
146    pub fn offset(&mut self, o: &T) {
147        for point in self.path.iter_mut() {
148            point.add_assign(*o);
149        }
150    }
151}
152
153impl<T> Path<T>
154where
155    T: ToSvgString + Copy + Add<Output = T>
156{
157    /// Generates a string representation of the path in SVG format.
158    /// 
159    /// Takes a bool to indicate whether the end should be wrapped back to start.
160    /// 
161    /// An offset is specified to apply an offset to the display points (useful when displaying on canvas elements).
162    /// 
163    /// If `close` is true, assume the last point of the path repeats the first point
164    pub fn to_svg_string(&self, close: bool, offset: &T, precision: Option<u32>) -> String {
165        let o = *offset;
166        let mut string = String::new();
167
168        self.path
169            .iter()
170            .take(1)
171            .for_each(|p| write!(&mut string, "M{} ", (*p+o).to_svg_string(precision)).unwrap());
172
173        self.path
174            .iter()
175            .skip(1)
176            .take(self.path.len() - if close { 2 } else { 1 })
177            .for_each(|p| write!(&mut string, "L{} ", (*p+o).to_svg_string(precision)).unwrap());
178
179        if close {
180            write!(&mut string, "Z ").unwrap();
181        }
182
183        string
184    }
185}
186
187impl<T> Path<Point2<T>>
188where T: Add<Output = T> + Sub<Output = T> + Mul<Output = T> +
189    std::cmp::PartialEq + std::cmp::PartialOrd + Copy + Into<f64> {
190
191    /// Path is a closed path (shape), but the reduce algorithm only reduces open paths.
192    /// We divide the path into four sections, spliced at the extreme points (max-x max-y min-x min-y),
193    /// and reduce each section individually.
194    /// Thus the most simplified path consists of at least 4 points.
195    /// This function assumes the last point of the path repeats the first point.
196    pub fn reduce(&self, tolerance: f64) -> Option<Self> {
197        if !self.path.is_empty() {
198            assert!(self.path[0] == self.path[self.path.len() - 1]);
199        }
200        let mut corners = [(0, self.path[0]); 4];
201        for (i, p) in self.path.iter().enumerate() {
202            if i == self.path.len() - 1 {
203                break;
204            }
205            if p.x < corners[0].1.x { corners[0] = (i, *p); }
206            if p.y <= corners[1].1.y { corners[1] = (i, *p); }
207            if p.x >= corners[2].1.x { corners[2] = (i, *p); }
208            if p.y >= corners[3].1.y { corners[3] = (i, *p); }
209        }
210        let abs = |i: T| -> f64 { let i: f64 = i.into(); if i < 0.0 { -i } else { i } };
211        if  abs(corners[0].1.x - corners[2].1.x) < tolerance &&
212            abs(corners[1].1.y - corners[3].1.y) < tolerance {
213            return None;
214        }
215        corners.sort_by_key(|c| c.0);
216        let mut sections = [
217            &self.path[corners[0].0..=corners[1].0],
218            &self.path[corners[1].0..=corners[2].0],
219            &self.path[corners[2].0..=corners[3].0],
220            &[],
221        ];
222        let mut last = self.path[corners[3].0..self.path.len()-1].to_vec();
223        last.append(&mut self.path[0..=corners[0].0].to_vec());
224        sections[3] = &last.as_slice();
225        let mut combined = Vec::new();
226        for (i, path) in sections.iter().enumerate() {
227            let mut reduced = reduce::<T>(path, tolerance);
228            if i != 3 {
229                reduced.pop();
230            }
231            combined.append(&mut reduced);
232        }
233        if combined.len() <= 3 {
234            return None
235        }
236        Some(Self {
237            path: combined
238        })
239    }
240
241}
242
243impl PathI32 {
244    /// Returns a copy of self after Path Smoothing, preserving corners.
245    /// 
246    /// `corner_threshold` is specified in radians.
247    /// `outset_ratio` is a real number >= 1.0.
248    /// `segment_length` is specified in pixels (length unit in path coordinate system).
249    pub fn smooth(
250        &self, corner_threshold: f64, outset_ratio: f64, segment_length: f64, max_iterations: usize
251    ) -> PathF64 {
252        assert!(max_iterations > 0);
253        let mut corners = SubdivideSmooth::find_corners(self, corner_threshold, true);
254        let mut path = self.to_path_f64();
255        for _i in 0..max_iterations {
256            let result = SubdivideSmooth::subdivide_keep_corners(&path, &corners, outset_ratio, segment_length, true);
257            path = result.0;
258            corners = result.1;
259            if result.2 { // Can terminate early
260                break;
261            }
262        }
263        path
264    }
265}
266
267impl PathF64 {
268    pub fn smooth(
269        &self, corner_threshold: f64, outset_ratio: f64, segment_length: f64, max_iterations: usize
270    ) -> PathF64 {
271        assert!(max_iterations > 0);
272        let mut corners = SubdivideSmooth::find_corners(self, corner_threshold, true);
273        let mut path = PathF64::new();
274        for _i in 0..max_iterations {
275            let result = SubdivideSmooth::subdivide_keep_corners(self, &corners, outset_ratio, segment_length, true);
276            path = result.0;
277            corners = result.1;
278            if result.2 { // Can terminate early
279                break;
280            }
281        }
282        path
283    }
284}
285
286impl PathI32 {
287
288    /// Returns a copy of self after Path Simplification:
289    /// 
290    /// First remove staircases then simplify by limiting penalties.
291    pub fn simplify(&self, clockwise: bool) -> Self {
292        let path = PathSimplify::remove_staircase(self, clockwise);
293        PathSimplify::limit_penalties(&path)
294    }
295
296    /// Converts outline of pixel cluster to path with Path Walker. 
297    /// Takes a bool representing the clockwiseness of traversal (useful in svg representation to represent holes).
298    /// Takes an enum PathSimplifyMode which indicates the required operation:
299    /// 
300    /// - Polygon - Walk path and simplify it
301    /// - Otherwise - Walk path only
302    pub fn image_to_path(image: &BinaryImage, clockwise: bool, mode: PathSimplifyMode) -> PathI32 {
303        match mode {
304            PathSimplifyMode::Polygon => {
305                let path = Self::image_to_path_baseline(image, clockwise);
306                path.simplify(clockwise)
307            },
308            // Otherwise
309            PathSimplifyMode::None | PathSimplifyMode::Spline => {
310                Self::image_to_path_baseline(image, clockwise)
311            },
312        }
313    }
314
315    /// Returns a copy of self converted to PathF64
316    pub fn to_path_f64(&self) -> PathF64 {
317        PathF64 {
318            path: self.path.iter().map(|p| {PointF64{x:p.x as f64, y:p.y as f64}}).collect()
319        }
320    }
321
322    fn image_to_path_baseline(image: &BinaryImage, clockwise: bool) -> PathI32 {
323        let (_boundary, start, _length) = Shape::image_boundary_and_position_length(&image);
324        let mut path = Vec::new();
325        if let Some(start) = start {
326            let walker = PathWalker::new(&image, start, clockwise);
327            path.extend(walker);
328        }
329        PathI32 { path }
330    }
331}
332
333#[cfg(test)]
334mod tests {
335    use super::*;
336
337    #[test]
338    fn test_to_svg_string() {
339        let mut path = PathI32::new();
340        path.add(PointI32 { x: 0, y: 0 });
341        path.add(PointI32 { x: 1, y: 0 });
342        path.add(PointI32 { x: 1, y: 1 });
343        assert_eq!("M0,0 L1,0 L1,1 ", path.to_svg_string(false, &PointI32::default(), None));
344    }
345
346    #[test]
347    fn test_to_svg_string_offset() {
348        let mut path = PathI32::new();
349        path.add(PointI32 { x: 0, y: 0 });
350        path.add(PointI32 { x: 1, y: 0 });
351        path.add(PointI32 { x: 1, y: 1 });
352        assert_eq!("M1,1 L2,1 L2,2 ", path.to_svg_string(false, &PointI32 { x: 1, y: 1 }, None));
353    }
354
355    #[test]
356    fn test_to_svg_string_closed() {
357        let mut path = PathI32::new();
358        path.add(PointI32 { x: 0, y: 0 });
359        path.add(PointI32 { x: 1, y: 0 });
360        path.add(PointI32 { x: 1, y: 1 });
361        path.add(PointI32 { x: 0, y: 0 });
362        assert_eq!("M0,0 L1,0 L1,1 Z ", path.to_svg_string(true, &PointI32::default(), None));
363    }
364
365    #[test]
366    fn test_reduce_noop() {
367        let path = Path {
368            path: vec![
369                PointI32 { x: 0, y: 0 },
370                PointI32 { x: 1, y: 0 },
371                PointI32 { x: 1, y: 1 },
372                PointI32 { x: 0, y: 1 },
373                PointI32 { x: 0, y: 0 },
374            ]
375        };
376        assert_eq!(path.reduce(0.5).unwrap().path, path.path);
377    }
378
379    #[test]
380    fn test_reduce_empty() {
381        let path = Path {
382            path: vec![
383                PointI32 { x: 0, y: 0 },
384                PointI32 { x: 1, y: 0 },
385                PointI32 { x: 1, y: 1 },
386                PointI32 { x: 0, y: 1 },
387                PointI32 { x: 0, y: 0 },
388            ]
389        };
390        assert!(path.reduce(2.0).is_none());
391    }
392
393    #[test]
394    fn test_reduce_noop_2() {
395        let path = Path {
396            path: vec![
397                PointI32 { x: 0, y: 0 },
398                PointI32 { x: 1, y: 0 },
399                PointI32 { x: 10, y: 0 },
400                PointI32 { x: 10, y: 9 },
401                PointI32 { x: 10, y: 10 },
402                PointI32 { x: 0, y: 10 },
403                PointI32 { x: 0, y: 9 },
404                PointI32 { x: 0, y: 0 },
405            ]
406        };
407        assert_eq!(path.reduce(0.5).unwrap().path, vec![
408            PointI32 { x: 0, y: 0 },
409            PointI32 { x: 10, y: 0 },
410            PointI32 { x: 10, y: 10 },
411            PointI32 { x: 0, y: 10 },
412            PointI32 { x: 0, y: 0 },
413        ]);
414    }
415
416    #[test]
417    fn test_reduce() {
418        let path = Path {
419            path: vec![
420                PointI32 { x: 0, y: 0 },
421                PointI32 { x: 1, y: 0 },
422                PointI32 { x: 10, y: 0 },
423                PointI32 { x: 10, y: 9 },
424                PointI32 { x: 10, y: 10 },
425                PointI32 { x: 0, y: 10 },
426                PointI32 { x: 0, y: 9 },
427                PointI32 { x: 0, y: 0 },
428            ]
429        };
430        assert_eq!(path.reduce(1.0).unwrap().path, vec![
431            PointI32 { x: 0, y: 0 },
432            PointI32 { x: 10, y: 0 },
433            PointI32 { x: 10, y: 10 },
434            PointI32 { x: 0, y: 10 },
435            PointI32 { x: 0, y: 0 },
436        ]);
437    }
438
439    #[test]
440    fn test_reduce_shuffle() {
441        let path = Path {
442            path: vec![
443                PointI32 { x: 0, y: 0 },
444                PointI32 { x: 1, y: 0 },
445                PointI32 { x: 10, y: 0 },
446                PointI32 { x: 10, y: 10 },
447                PointI32 { x: 9, y: 9 },
448                PointI32 { x: 0, y: 9 },
449                PointI32 { x: 0, y: 10 },
450                PointI32 { x: 0, y: 0 },
451            ]
452        };
453        assert_eq!(path.reduce(1.0).unwrap().path, vec![
454            PointI32 { x: 0, y: 0 },
455            PointI32 { x: 10, y: 0 },
456            PointI32 { x: 10, y: 10 },
457            PointI32 { x: 0, y: 10 },
458            PointI32 { x: 0, y: 0 },
459        ]);
460    }
461
462    #[test]
463    fn test_reduce_diamond_noop() {
464        let path = Path {
465            path: vec![
466                PointI32 { x: 0, y: 0 },
467                PointI32 { x: 1, y: 1 },
468                PointI32 { x: 0, y: 2 },
469                PointI32 { x: -1, y: 1 },
470                PointI32 { x: 0, y: 0 },
471            ]
472        };
473        assert_eq!(path.reduce(0.5).unwrap().path, path.path);
474    }
475
476    #[test]
477    fn test_reduce_diamond() {
478        let path = Path {
479            path: vec![
480                PointI32 { x: 0, y: 0 },
481                PointI32 { x: 10, y: 10 },
482                PointI32 { x: 9, y: 9 },
483                PointI32 { x: 0, y: 20 },
484                PointI32 { x: 0, y: 19 },
485                PointI32 { x: -10, y: 10 },
486                PointI32 { x: -10, y: 9 },
487                PointI32 { x: 0, y: 0 },
488            ]
489        };
490        assert_eq!(path.reduce(2.0).unwrap().path, vec![
491            PointI32 { x: 0, y: 0 },
492            PointI32 { x: 10, y: 10 },
493            PointI32 { x: 0, y: 20 },
494            PointI32 { x: -10, y: 10 },
495            PointI32 { x: 0, y: 0 },
496        ]);
497    }
498
499    #[test]
500    fn test_reduce_triangle_noop() {
501        let path = Path {
502            path: vec![
503                PointI32 { x: 0, y: 0 },
504                PointI32 { x: 1, y: 1 },
505                PointI32 { x: 0, y: 1 },
506                PointI32 { x: 0, y: 0 },
507            ]
508        };
509        assert_eq!(path.reduce(0.5).unwrap().path, path.path);
510    }
511
512    #[test]
513    fn test_reduce_triangle_degenerate() {
514        let path = Path {
515            path: vec![
516                PointI32 { x: 0, y: 0 },
517                PointI32 { x: 10, y: 10 },
518                PointI32 { x: 0, y: 1 },
519                PointI32 { x: 0, y: 0 },
520            ]
521        };
522        assert!(path.reduce(2.0).is_none());
523    }
524
525    #[test]
526    fn test_path_to_svg_precision_i32() {
527        let path = Path {
528            path: vec![
529                PointI32 { x: 0, y: 0 },
530                PointI32 { x: 2, y: 3 },
531                PointI32 { x: 4, y: 5 },
532            ]
533        };
534        assert_eq!(
535            path.to_svg_string(false, &PointI32 { x: 0, y: 0 }, None),
536            "M0,0 L2,3 L4,5 ".to_owned()
537        );
538        assert_eq!(
539            path.to_svg_string(false, &PointI32 { x: 0, y: 0 }, Some(2)),
540            "M0,0 L2,3 L4,5 ".to_owned()
541        );
542    }
543
544    #[test]
545    fn test_path_to_svg_precision_f64() {
546        let path = Path {
547            path: vec![
548                PointF64 { x: 2.22, y: 2.67 },
549                PointF64 { x: 3.50, y: 3.48 },
550                PointF64 { x: 0.0, y: 0.0 },
551            ]
552        };
553        assert_eq!(
554            path.to_svg_string(false, &PointF64 { x: 0.0, y: 0.0 }, None),
555            "M2.22,2.67 L3.5,3.48 L0,0 ".to_owned()
556        );
557        assert_eq!(
558            path.to_svg_string(false, &PointF64 { x: 0.0, y: 0.0 }, Some(1)),
559            "M2.2,2.7 L3.5,3.5 L0,0 ".to_owned()
560        );
561        assert_eq!(
562            path.to_svg_string(false, &PointF64 { x: 0.0, y: 0.0 }, Some(0)),
563            "M2,3 L4,3 L0,0 ".to_owned()
564        );
565    }
566}
visioncortex/path/paths.rs

visioncortex/path/
paths.rs
