simplify_polyline/
lib.rs

1#![warn(missing_docs)]
2#![doc = include_str!("../README.md")]
3
4pub use traits::ExtendedNumOps;
5
6/// stub
7#[cfg(feature = "serde")]
8pub mod serde;
9
10mod point;
11mod traits;
12
13pub use point::Point;
14
15fn get_sq_seg_dist<const D: usize, T: ExtendedNumOps>(
16    pt: &Point<D, T>,
17    start: &Point<D, T>,
18    end: &Point<D, T>,
19) -> T {
20    let mut intersection = *start;
21    let difference = end - start;
22
23    if !difference.is_origin() {
24        let t = ((pt - start) * difference).value_sum() / difference.sq_dist_origin();
25        if t > T::one() {
26            intersection = *end;
27        } else if t > T::zero() {
28            intersection = intersection + (difference * t)
29        }
30    }
31
32    (pt - intersection).sq_dist_origin()
33}
34
35fn simplify_radial_dist<const D: usize, T: ExtendedNumOps>(
36    points: &[Point<D, T>],
37    tolerance: T,
38) -> Vec<Point<D, T>> {
39    let mut prev_point = points[0];
40    let mut new_points = vec![prev_point];
41    let mut point = prev_point;
42
43    for pt in points.iter().skip(1) {
44        point = *pt;
45        if pt.sq_dist(&prev_point) > tolerance {
46            new_points.push(*pt);
47            prev_point = *pt;
48        }
49    }
50
51    if prev_point != point {
52        new_points.push(point);
53    }
54
55    new_points
56}
57
58fn simplify_dp_step<const D: usize, T: ExtendedNumOps>(
59    points: &[Point<D, T>],
60    first: usize,
61    last: usize,
62    tolerance: T,
63    simplified: &mut Vec<Point<D, T>>,
64) {
65    let mut max_sq_dist = tolerance;
66    let mut max_index = 0;
67
68    for i in first + 1..last {
69        let sq_dist = get_sq_seg_dist(&points[i], &points[first], &points[last]);
70        if sq_dist > max_sq_dist {
71            max_index = i;
72            max_sq_dist = sq_dist;
73        }
74    }
75
76    if max_sq_dist > tolerance {
77        if (max_index - first) > 1 {
78            simplify_dp_step(points, first, max_index, tolerance, simplified);
79        }
80        simplified.push(points[max_index]);
81        if (last - max_index) > 1 {
82            simplify_dp_step(points, max_index, last, tolerance, simplified);
83        }
84    }
85}
86
87fn simplify_douglas_peucker<const D: usize, T: ExtendedNumOps>(
88    points: &[Point<D, T>],
89    tolerance: T,
90) -> Vec<Point<D, T>> {
91    let mut simplified = vec![points[0]];
92    simplify_dp_step(points, 0, points.len() - 1, tolerance, &mut simplified);
93    simplified.push(points[points.len() - 1]);
94
95    simplified
96}
97
98/// Simplifies a polyline within a given tolerance.
99///
100///
101/// # Arguments
102///
103/// - `tolerance`: A distance measurement used for both radial distance and Douglas–Peucker -- the
104/// higher the tolerance, the more points will be removed from the polyline.
105/// - `high_quality`: Controls the algorithm(s) to be used in simplification
106///   - `true`: this will take the entire array of points and simplify using the Douglas–Peucker
107///     algorithm.
108///   - `false`: the list of points are first filtered using a simple radial distance algorithm,
109///     and then passed to the the Douglas-Peucker algorithm for final simplification.
110pub fn simplify<const D: usize, T: ExtendedNumOps>(
111    points: &[Point<D, T>],
112    tolerance: T,
113    high_quality: bool,
114) -> Vec<Point<D, T>> {
115    if points.len() <= 2 {
116        return points.to_vec();
117    }
118
119    let tolerance_sq = tolerance * tolerance;
120    let intermediate = if high_quality {
121        points.to_vec()
122    } else {
123        simplify_radial_dist(points, tolerance_sq)
124    };
125
126    simplify_douglas_peucker(&intermediate, tolerance_sq)
127}
simplify_polyline/lib.rs

simplify_polyline/
lib.rs
