#![allow(clippy::range_minus_one)]
#![deny(
deprecated_in_future,
exported_private_dependencies,
future_incompatible,
missing_copy_implementations,
missing_crate_level_docs,
missing_debug_implementations,
missing_docs,
private_in_public,
rust_2018_compatibility,
rust_2018_idioms,
trivial_casts,
trivial_numeric_casts,
unsafe_code,
unstable_features,
unused_import_braces,
unused_qualifications
)]
use std::ops::RangeInclusive;
use legasea_line::LineDistance;
use mint::Point2;
pub fn rdp<T, U>(points: &[Point2<T>], epsilon: f64) -> Vec<usize>
where
T: Copy + std::ops::Sub<Output = U>,
U: num_traits::cast::NumCast,
T: num_traits::cast::NumCast,
{
if points.len() < 3 {
return (0..points.len()).collect();
}
let mut ranges = Vec::<RangeInclusive<usize>>::new();
let mut results = Vec::new();
results.push(0);
ranges.push(0..=points.len() - 1);
while let Some(range) = ranges.pop() {
let range_start = *range.start();
let range_end = *range.end();
let start = points[range_start];
let end = points[range_end];
let line = LineDistance::new(start, end);
let (max_distance, max_index) = points[range_start + 1..range_end].iter().enumerate().fold(
(0.0_f64, 0),
move |(max_distance, max_index), (index, point)| {
let distance = match line.to(point) {
Some(distance) => distance,
None => {
let base = (point.x - start.x).to_f64().unwrap();
let height = (point.y - start.y).to_f64().unwrap();
base.hypot(height)
}
};
if distance > max_distance {
return (distance, index + 1);
}
(max_distance, max_index)
},
);
if max_distance > epsilon {
let division_point = range_start + max_index;
let first_section = range_start..=division_point;
let second_section = division_point..=range_end;
let should_keep_second_half = division_point - range_start > 2;
if should_keep_second_half {
ranges.push(second_section);
}
if division_point - range_start > 2 {
ranges.push(first_section);
} else {
results.push(division_point);
}
if !should_keep_second_half {
results.push(range_end);
}
} else {
results.push(range_end);
}
}
results
}
#[cfg(test)]
mod tests {
use mint::Point2;
use super::*;
#[test]
fn within_epsilon() {
let points = vec![
Point2 { x: 0.0, y: 0.0 },
Point2 { x: 1.0, y: 0.5 },
Point2 { x: 2.0, y: -0.9 },
Point2 { x: 3.0, y: 0.3 },
Point2 { x: 4.0, y: 0.0 },
];
let actual = rdp(&points, 1.0);
let expected = vec![0, 4];
assert_eq!(expected, actual);
}
#[test]
fn within_center_out() {
let points = vec![
Point2 { x: 0.0, y: 0.0 },
Point2 { x: 1.0, y: 0.5 },
Point2 { x: 2.0, y: -1.1 },
Point2 { x: 3.0, y: 0.3 },
Point2 { x: 4.0, y: 0.0 },
];
let actual = rdp(&points, 1.0);
let expected = vec![0, 2, 4];
assert_eq!(expected, actual);
}
#[test]
fn inner_edges_out() {
let points = vec![
Point2 { x: 0.0, y: 0.0 },
Point2 { x: 1.0, y: 2.5 },
Point2 { x: 2.0, y: 1.1 },
Point2 { x: 3.0, y: 2.6 },
Point2 { x: 4.0, y: 0.0 },
];
let actual = rdp(&points, 1.0);
let expected = vec![0, 1, 3, 4];
assert_eq!(expected, actual);
}
#[test]
fn one_point() {
let points = vec![
Point2 { x: 0.0, y: 0.0 },
];
let actual = rdp(&points, 1.0);
let expected = vec![0];
assert_eq!(expected, actual);
}
#[test]
fn two_points() {
let points = vec![
Point2 { x: 0.0, y: 0.0 },
Point2 { x: 4.0, y: 0.0 },
];
let actual = rdp(&points, 1.0);
let expected = vec![0, 1];
assert_eq!(expected, actual);
}
#[test]
fn simplify_circle() {
let points = vec![
Point2 { x: 1, y: 1 },
Point2 { x: 2, y: 1 },
Point2 { x: 3, y: 1 },
Point2 { x: 3, y: 2 },
Point2 { x: 3, y: 3 },
Point2 { x: 2, y: 3 },
Point2 { x: 1, y: 3 },
Point2 { x: 1, y: 2 },
Point2 { x: 1, y: 1 },
];
let actual = rdp(&points, 1.0);
let expected = vec![0, 2, 4, 6, 8];
assert_eq!(actual, expected);
}
}