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

#[cfg(feature = "tests")]
use serde::{Deserialize, Serialize};

#[derive(Clone, Copy, PartialEq, Debug)]
#[cfg_attr(feature = "tests", derive(Serialize, Deserialize))]
pub struct Point {
    pub x: f64,
    pub y: f64,
}

#[macro_export]
macro_rules! point {
    ($x:expr,$y:expr) => {
        Point { x: $x, y: $y }
    };
}

#[macro_export]
macro_rules! points {
    ($(($x:expr,$y:expr)),*) => {
        &[$(point!($x,$y)),*]
    };
}

fn get_sq_dist(p1: &Point, p2: &Point) -> f64 {
    let dx = p2.x - p1.x;
    let dy = p2.y - p1.y;

    dx * dx + dy * dy
}

fn get_sq_seg_dist(pt: &Point, start: &Point, end: &Point) -> f64 {
    let (mut x, mut y, mut dx, mut dy) = (start.x, start.y, end.x - start.x, end.y - start.y);

    if dx != 0.0 || dy != 0.0 {
        let t = ((pt.x - x) * dx + (pt.y - y) * dy) / (dx * dx + dy * dy);

        if t > 1.0 {
            x = end.x;
            y = end.y;
        } else if t > 0.0 {
            x += dx * t;
            y += dy * t;
        }
    }

    dx = pt.x - x;
    dy = pt.y - y;

    dx * dx + dy * dy
}

fn simplify_radial_dist(points: &[Point], tolerance: f64) -> Vec<Point> {
    let mut prev_point = points[0];
    let mut new_points = vec![prev_point];
    let mut point = prev_point;

    for pt in points.iter().skip(1) {
        point = *pt;
        if get_sq_dist(pt, &prev_point) > tolerance {
            new_points.push(*pt);
            prev_point = *pt;
        }
    }

    if prev_point != point {
        new_points.push(point);
    }

    new_points
}

fn simplify_dp_step(
    points: &[Point],
    first: usize,
    last: usize,
    tolerance: f64,
    simplified: &mut Vec<Point>,
) {
    let mut max_sq_dist = tolerance;
    let mut max_index = 0;

    for i in first + 1..last {
        let sq_dist = get_sq_seg_dist(&points[i], &points[first], &points[last]);
        if sq_dist > max_sq_dist {
            max_index = i;
            max_sq_dist = sq_dist;
        }
    }

    if max_sq_dist > tolerance {
        if (max_index - first) > 1 {
            simplify_dp_step(points, first, max_index, tolerance, simplified);
        }
        simplified.push(points[max_index]);
        if (last - max_index) > 1 {
            simplify_dp_step(points, max_index, last, tolerance, simplified);
        }
    }
}

fn simplify_douglas_peucker(points: &[Point], tolerance: f64) -> Vec<Point> {
    let mut simplified = vec![points[0]];
    simplify_dp_step(points, 0, points.len() - 1, tolerance, &mut simplified);
    simplified.push(points[points.len() - 1]);

    simplified
}

pub fn simplify(points: &[Point], tolerance: f64, high_quality: bool) -> Vec<Point> {
    if points.len() <= 2 {
        return points.to_vec();
    }

    let tolerance_sq = tolerance * tolerance;
    let intermediate = if high_quality {
        points.to_vec()
    } else {
        simplify_radial_dist(points, tolerance_sq)
    };

    simplify_douglas_peucker(&intermediate, tolerance_sq)
}