vsvg/
optimization.rs

1use crate::path_index::IndexBuilder;
2use crate::{Layer, PathDataTrait, Point};
3
4impl Layer {
5    /// Sort the paths such as to minimize the pen up distance
6    ///
7    /// This is done using a greedy algorithm, starting with the layer's first path. Any path that
8    /// cannot be spatially indexed (empty or otherwise degenerate) is moved at the end.
9    pub fn sort(&mut self, flip: bool) {
10        self.sort_with_builder(IndexBuilder::default().flip(flip));
11    }
12
13    #[allow(clippy::missing_panics_doc)]
14    pub fn sort_with_builder(&mut self, builder: IndexBuilder) {
15        if self.paths.len() <= 1 {
16            return;
17        }
18
19        let mut new_paths = Vec::with_capacity(self.paths.len());
20        let mut index = builder.build(&self.paths);
21
22        let mut pos = Point::ZERO;
23        while let Some((path_item, reverse)) = index.pop_nearest(&pos) {
24            new_paths.push((*path_item.path).clone());
25            if reverse {
26                pos = path_item.start.unwrap_or(pos);
27                new_paths.last_mut().expect("just inserted").data.flip();
28            } else {
29                pos = path_item.end.unwrap_or(pos);
30            }
31        }
32
33        // add any remaining, unindexed paths
34        while let Some(path_item) = index.pop_first() {
35            new_paths.push((*path_item.path).clone());
36        }
37
38        self.paths = new_paths;
39    }
40}
41
42#[cfg(test)]
43mod tests {
44    use super::*;
45    use crate::{test_file, Document, DocumentTrait, FlattenedLayer, FlattenedPath, LayerTrait};
46
47    #[test]
48    fn test_sort() {
49        let mut layer = FlattenedLayer::default();
50
51        let p1 = FlattenedPath::from(vec![Point::new(10.0, 10.1), Point::new(0.0, 0.0)]);
52        let p2 = FlattenedPath::from(vec![Point::new(3.0, 2.3), Point::new(10.0, 10.0)]);
53        let p3 = FlattenedPath::from(vec![Point::new(1.0, 0.0), Point::new(0.0, 0.0)]);
54        let p4 = FlattenedPath::from(vec![Point::new(2.0, 1.0), Point::new(1.0, 0.1)]);
55
56        layer.paths.push(p1.clone());
57        layer.paths.push(p2.clone());
58        layer.paths.push(p3.clone());
59        layer.paths.push(p4.clone());
60
61        layer.sort(false);
62
63        assert_eq!(layer.paths[0], p3);
64        assert_eq!(layer.paths[1], p4);
65        assert_eq!(layer.paths[2], p2);
66        assert_eq!(layer.paths[3], p1);
67    }
68
69    #[test]
70    fn test_sort_bidir() {
71        let mut layer = FlattenedLayer::default();
72
73        let p1 = FlattenedPath::from(vec![Point::new(10.0, 10.1), Point::new(20.0, 20.0)]);
74        let p2 = FlattenedPath::from(vec![Point::new(3.0, 2.3), Point::new(10.0, 10.0)]);
75        let mut p3 = FlattenedPath::from(vec![Point::new(1.0, 0.0), Point::new(0.0, 0.0)]);
76        let mut p4 = FlattenedPath::from(vec![Point::new(3.0, 2.0), Point::new(1.0, 0.1)]);
77
78        layer.paths.push(p1.clone());
79        layer.paths.push(p2.clone());
80        layer.paths.push(p3.clone());
81        layer.paths.push(p4.clone());
82
83        layer.sort(true);
84
85        p3.data.flip();
86        assert_eq!(layer.paths[0], p3);
87        p4.data.flip();
88        assert_eq!(layer.paths[1], p4);
89        assert_eq!(layer.paths[2], p2);
90        assert_eq!(layer.paths[3], p1);
91    }
92
93    #[test]
94    fn test_sort_problematic_case() {
95        let mut doc = Document::from_svg(test_file!("random_100_sort.svg"), false).unwrap();
96        doc.get_mut(1).sort(true);
97    }
98}
vsvg/optimization.rs

vsvg/
optimization.rs
