pub trait Point: Clone {
fn x(&self) -> f64;
fn y(&self) -> f64;
}
pub trait SqDistance<Rhs = Self>
where
Self: Point,
Rhs: Point,
{
fn get_sq_distance(&self, rhs: &Rhs) -> f64 {
let dx = self.x() - rhs.x();
let dy = self.y() - rhs.y();
dx * dx + dy * dy
}
}
pub trait SqSegDistance<L = Self, R = Self>
where
Self: Point,
L: Point,
R: Point,
{
fn get_sq_seg_distance(&self, l: &L, r: &R) -> f64 {
let mut x = l.x();
let mut y = l.y();
let mut dx = r.x() - x;
let mut dy = r.y() - y;
if dx != 0f64 && dy != 0f64 {
let t = ((self.x() - x) * dx + (self.y() - y) * dy) / (dx * dx + dy * dy);
if t > 1f64 {
x = r.x();
y = r.y();
} else if t > 0f64 {
x += dx * t;
y += dy * t;
}
}
dx = self.x() - x;
dy = self.y() - y;
dx * dx + dy * dy
}
}
impl<T> SqDistance<T> for T where T: Point {}
impl<T> SqSegDistance<T> for T where T: Point {}
pub struct Simplify<'a, T>
where
T: Point,
{
highest_quality: bool,
tolerance: f64,
points: &'a mut Vec<T>,
}
impl<'a, T> Simplify<'a, T>
where
T: Point,
{
pub fn new(points: &'a mut Vec<T>) -> Self {
Simplify {
highest_quality: false,
tolerance: 1f64,
points,
}
}
pub fn set_highest_quality(&mut self, b: bool) -> &mut Self {
self.highest_quality = b;
self
}
pub fn set_tolerance(&mut self, t: f64) -> &mut Self {
self.tolerance = t * t;
self
}
fn simplify_radial_dist(&mut self) -> &mut Self {
let mut prev = 0;
let mut index = 1;
while index < self.points.len() - 1 {
unsafe {
if self
.points
.get_unchecked(index)
.get_sq_distance(self.points.get_unchecked(prev))
<= self.tolerance
{
self.points.remove(index);
index -= 1;
} else {
prev = index;
}
}
index += 1;
}
self
}
fn simplify_dp_step(
&mut self,
first: usize,
last: usize,
simplified: &mut Vec<T>,
) {
let mut max_sq_dist = self.tolerance;
let mut index = 0;
for i in first + 1..last {
let sq_dist = unsafe {
self.points[i].get_sq_seg_distance(self.points.get_unchecked(first), self.points.get_unchecked(last))
};
if sq_dist > max_sq_dist {
index = i;
max_sq_dist = sq_dist;
}
}
if max_sq_dist > self.tolerance {
if index - first > 1 {
self.simplify_dp_step(first, index, simplified);
}
simplified.push(unsafe {
self.points.get_unchecked(index).clone()
});
if last - index > 1 {
self.simplify_dp_step(index, last, simplified);
}
}
}
fn simplify_douglas_peucker(&mut self, mut simplified: Vec<T>) -> Vec<T> {
let last = self.points.len() - 1;
self.simplify_dp_step(0, last, &mut simplified);
simplified.push(unsafe {
self.points.get_unchecked(last).clone()
});
simplified
}
pub fn run(&mut self) -> Vec<T> {
if self.points.len() <= 2 {
return self.points.clone();
}
if !self.highest_quality {
self.simplify_radial_dist();
}
let mut simplified = Vec::new();
simplified.push(unsafe {
self.points.get_unchecked(0).clone()
});
self.simplify_douglas_peucker(simplified)
}
}
#[cfg(test)]
mod tests {
use super::{Point as P, Simplify};
#[derive(Clone, Debug)]
pub struct Point {
pub x: f64,
pub y: f64,
}
impl PartialEq for Point {
fn eq(&self, other: &Self) -> bool {
self.x == other.x && self.y == other.y
}
}
impl Eq for Point {}
impl P for Point {
fn x(&self) -> f64 {
self.x
}
fn y(&self) -> f64 {
self.y
}
}
#[test]
fn test_simplify_with_given_tolerance() {
let mut data = vec![ Point { x: 224.55, y: 250.15, }, Point { x: 226.91, y: 244.19, }, Point { x: 233.31, y: 241.45, }, Point { x: 234.98, y: 236.06, }, Point { x: 244.21, y: 232.76, }, Point { x: 262.59, y: 215.31, }, Point { x: 267.76, y: 213.81, }, Point { x: 273.57, y: 201.84, }, Point { x: 273.12, y: 192.16, }, Point { x: 277.62, y: 189.03, }, Point { x: 280.36, y: 181.41, }, Point { x: 286.51, y: 177.74, }, Point { x: 292.41, y: 159.37, }, Point { x: 296.91, y: 155.64, }, Point { x: 314.95, y: 151.37, }, Point { x: 319.75, y: 145.16, }, Point { x: 330.33, y: 137.57, }, Point { x: 341.48, y: 139.96, }, Point { x: 369.98, y: 137.89, }, Point { x: 387.39, y: 142.51, }, Point { x: 391.28, y: 139.39, }, Point { x: 409.52, y: 141.14, }, Point { x: 414.82, y: 139.75, }, Point { x: 427.72, y: 127.30, }, Point { x: 439.60, y: 119.74, }, Point { x: 474.93, y: 107.87, }, Point { x: 486.51, y: 106.75, }, Point { x: 489.20, y: 109.45, }, Point { x: 493.79, y: 108.63, }, Point { x: 504.74, y: 119.66, }, Point { x: 512.96, y: 122.35, }, Point { x: 518.63, y: 120.89, }, Point { x: 524.09, y: 126.88, }, Point { x: 529.57, y: 127.86, }, Point { x: 534.21, y: 140.93, }, Point { x: 539.27, y: 147.24, }, Point { x: 567.69, y: 148.91, }, Point { x: 575.25, y: 157.26, }, Point { x: 580.62, y: 158.15, }, Point { x: 601.53, y: 156.85, }, Point { x: 617.74, y: 159.86, }, Point { x: 622.00, y: 167.04, }, Point { x: 629.55, y: 194.60, }, Point { x: 638.90, y: 195.61, }, Point { x: 641.26, y: 200.81, }, Point { x: 651.77, y: 204.56, }, Point { x: 671.55, y: 222.55, }, Point { x: 683.68, y: 217.45, }, Point { x: 695.25, y: 219.15, }, Point { x: 700.64, y: 217.98, }, Point { x: 703.12, y: 214.36, }, Point { x: 712.26, y: 215.87, }, Point { x: 721.49, y: 212.81, }, Point { x: 727.81, y: 213.36, }, Point { x: 729.98, y: 208.73, }, Point { x: 735.32, y: 208.20, }, Point { x: 739.94, y: 204.77, }, Point { x: 769.98, y: 208.42, }, Point { x: 779.60, y: 216.87, }, Point { x: 784.20, y: 218.16, }, Point { x: 800.24, y: 214.62, }, Point { x: 810.53, y: 219.73, }, Point { x: 817.19, y: 226.82, }, Point { x: 820.77, y: 236.17, }, Point { x: 827.23, y: 236.16, }, Point { x: 829.89, y: 239.89, }, Point { x: 851.00, y: 248.94, }, Point { x: 859.88, y: 255.49, }, Point { x: 865.21, y: 268.53, }, Point { x: 857.95, y: 280.30, }, Point { x: 865.48, y: 291.45, }, Point { x: 866.81, y: 298.66, }, Point { x: 864.68, y: 302.71, }, Point { x: 867.79, y: 306.17, }, Point { x: 859.87, y: 311.37, }, Point { x: 860.08, y: 314.35, }, Point { x: 858.29, y: 314.94, }, Point { x: 858.10, y: 327.60, }, Point { x: 854.54, y: 335.40, }, Point { x: 860.92, y: 343.00, }, Point { x: 856.43, y: 350.15, }, Point { x: 851.42, y: 352.96, }, Point { x: 849.84, y: 359.59, }, Point { x: 854.56, y: 365.53, }, Point { x: 849.74, y: 370.38, }, Point { x: 844.09, y: 371.89, }, Point { x: 844.75, y: 380.44, }, Point { x: 841.52, y: 383.67, }, Point { x: 839.57, y: 390.40, }, Point { x: 845.59, y: 399.05, }, Point { x: 848.40, y: 407.55, }, Point { x: 843.71, y: 411.30, }, Point { x: 844.09, y: 419.88, }, Point { x: 839.51, y: 432.76, }, Point { x: 841.33, y: 441.04, }, Point { x: 847.62, y: 449.22, }, Point { x: 847.16, y: 458.44, }, Point { x: 851.38, y: 462.79, }, Point { x: 853.97, y: 471.15, }, Point { x: 866.36, y: 480.77, }, ];
let simplified = vec![ Point { x: 224.55, y: 250.15, }, Point { x: 267.76, y: 213.81, }, Point { x: 296.91, y: 155.64, }, Point { x: 330.33, y: 137.57, }, Point { x: 409.52, y: 141.14, }, Point { x: 439.60, y: 119.74, }, Point { x: 486.51, y: 106.75, }, Point { x: 529.57, y: 127.86, }, Point { x: 539.27, y: 147.24, }, Point { x: 617.74, y: 159.86, }, Point { x: 629.55, y: 194.60, }, Point { x: 671.55, y: 222.55, }, Point { x: 727.81, y: 213.36, }, Point { x: 739.94, y: 204.77, }, Point { x: 769.98, y: 208.42, }, Point { x: 779.60, y: 216.87, }, Point { x: 800.24, y: 214.62, }, Point { x: 820.77, y: 236.17, }, Point { x: 859.88, y: 255.49, }, Point { x: 865.21, y: 268.53, }, Point { x: 857.95, y: 280.30, }, Point { x: 867.79, y: 306.17, }, Point { x: 859.87, y: 311.37, }, Point { x: 854.54, y: 335.40, }, Point { x: 860.92, y: 343.00, }, Point { x: 849.84, y: 359.59, }, Point { x: 854.56, y: 365.53, }, Point { x: 844.09, y: 371.89, }, Point { x: 839.57, y: 390.40, }, Point { x: 848.40, y: 407.55, }, Point { x: 839.51, y: 432.76, }, Point { x: 853.97, y: 471.15, }, Point { x: 866.36, y: 480.77, }, ];
let mut s = Simplify::new(&mut data);
s.set_tolerance(5f64);
assert_eq!(s.run(), simplified);
}
#[test]
fn test_simplify_with_one_element() {
let mut data = vec![Point { x: 1f64, y: 2f64 }];
let mut s = Simplify::new(&mut data);
assert_eq!(s.run(), vec![Point { x: 1f64, y: 2f64 }]);
}
#[test]
fn test_simplify_with_no_element() {
let mut data: Vec<Point> = vec![];
let mut s = Simplify::new(&mut data);
assert_eq!(s.run(), vec![]);
}
}