revrt 0.1.0

A library for optimizing transmission infrastructure for electrical grid.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

//! Simplify a path by removing points that fall on straight segments

/// Compute slope between two points
///
/// `p1`, `p2`: 2-tuples representing points (x, y).
///
/// This function returns `None` for vertical slopes.
fn slope(p1: &(f64, f64), p2: &(f64, f64)) -> Option<f64> {
    let dx = p2.0 - p1.0;
    let dy = p2.1 - p1.1;
    if dx.abs() < 1e-12 {
        None
    } else {
        Some(dy / dx)
    }
}

/// Check two slopes for equality within a tolerance
///
/// `a`, `b`: Slope values. `None` indicates a vertical slope.
/// `tol`: A float representing a slope tolerance to allow.
///  The tolerance is non-inclusive.
fn equal_slopes(a: Option<f64>, b: Option<f64>, tol: f64) -> bool {
    match (a, b) {
        (None, None) => true, // both vertical
        (Some(x), Some(y)) => (x - y).abs() < tol,
        _ => false, // one vertical, the other not
    }
}

/// Function to simplify a path by removing points that fall on straight segments
///
/// `points`: A collection points (x, y) representing a path.
/// `slope_tolerance`: A float representing a slope tolerance to allow
///  (not inclusive). For typical 8-direction routing, a value of 1 or less
///  should suffice.
///
/// Note that this function intentionally consumes the input vector.
/// The idea is that the output vector will be a lossless representation
/// of the input, so cloning is not necessary.
pub(super) fn simplify_path(points: Vec<(f64, f64)>, slope_tolerance: f64) -> Vec<(f64, f64)> {
    let len = points.len();
    if len <= 2 {
        return points;
    }

    points.into_iter().fold(
        Vec::with_capacity(len),
        |mut simplified_path, next_point| {
            match simplified_path.len() {
                0 | 1 => simplified_path.push(next_point),
                size => {
                    let prev_prev_point = &simplified_path[size - 2];
                    let prev_point = &simplified_path[size - 1];
                    if equal_slopes(
                        slope(prev_prev_point, prev_point),
                        slope(prev_point, &next_point),
                        slope_tolerance,
                    ) {
                        simplified_path.pop();
                    }
                    simplified_path.push(next_point);
                }
            }
            simplified_path
        },
    )
}

#[cfg(test)]
mod test_simplify_path {
    use super::*;

    #[test]
    fn basic_simplify() {
        let path = vec![(1.0, 1.0), (2.0, 2.0), (3.0, 3.0)];
        let simplified = simplify_path(path, 0.01);

        assert_eq!(simplified, vec![(1.0, 1.0), (3.0, 3.0)]);
    }

    #[test]
    fn basic_simplify_all_points() {
        let path = vec![(1.0, 1.0), (2.0, 2.0), (3.0, 2.0)];
        let simplified = simplify_path(path.clone(), 0.01);

        assert_eq!(simplified, path);
    }

    #[test]
    fn empty_simplify() {
        let path = vec![];
        let simplified = simplify_path(path.clone(), 0.01);

        assert_eq!(simplified, path);
    }

    #[test]
    fn single_item_simplify() {
        let path = vec![(1.0, 1.0)];
        let simplified = simplify_path(path.clone(), 0.01);

        assert_eq!(simplified, path);
    }

    #[test]
    fn two_item_simplify() {
        let path = vec![(1.0, 1.0), (2.0, 2.0)];
        let simplified = simplify_path(path.clone(), 0.01);

        assert_eq!(simplified, path);
    }

    #[test]
    fn v_shape() {
        let path = vec![(0.0, 2.0), (1.0, 1.0), (2.0, 2.0)];
        let simplified = simplify_path(path.clone(), 0.01);

        assert_eq!(simplified, path);
    }

    #[test]
    fn long_path() {
        let path = vec![
            (0.0, 0.0),
            (1.0, 1.0),
            (2.0, 2.0),
            (3.0, 3.0),
            (4.0, 4.0),
            (5.0, 5.0),
            (6.0, 6.0),
            (7.0, 7.0),
            (8.0, 8.0),
            (9.0, 9.0),
            (10.0, 10.0),
            (11.0, 10.0),
        ];
        let simplified = simplify_path(path, 0.01);

        assert_eq!(simplified, vec![(0.0, 0.0), (10.0, 10.0), (11.0, 10.0)]);
    }
}