use crate::algorithm::coords_iter::CoordsIter;
use crate::algorithm::euclidean_distance::EuclideanDistance;
use crate::{Coordinate, GeoFloat, Line, LineString, MultiLineString, MultiPolygon, Polygon};
#[derive(Copy, Clone)]
struct RdpIndex<T>
where
T: GeoFloat,
{
index: usize,
coord: Coordinate<T>,
}
fn rdp<T>(coords: impl Iterator<Item = Coordinate<T>>, epsilon: &T) -> Vec<Coordinate<T>>
where
T: GeoFloat,
{
if *epsilon <= T::zero() {
return coords.collect::<Vec<Coordinate<T>>>();
}
compute_rdp(
&coords
.enumerate()
.map(|(idx, coord)| RdpIndex { index: idx, coord })
.collect::<Vec<RdpIndex<T>>>(),
epsilon,
)
.into_iter()
.map(|rdpindex| rdpindex.coord)
.collect()
}
fn calculate_rdp_indices<T>(rdp_indices: &[RdpIndex<T>], epsilon: &T) -> Vec<usize>
where
T: GeoFloat,
{
if *epsilon <= T::zero() {
return rdp_indices
.iter()
.map(|rdp_index| rdp_index.index)
.collect();
}
compute_rdp(rdp_indices, epsilon)
.into_iter()
.map(|rdpindex| rdpindex.index)
.collect::<Vec<usize>>()
}
fn compute_rdp<T>(rdp_indices: &[RdpIndex<T>], epsilon: &T) -> Vec<RdpIndex<T>>
where
T: GeoFloat,
{
if rdp_indices.is_empty() {
return vec![];
}
let first = rdp_indices[0];
let last = rdp_indices[rdp_indices.len() - 1];
let first_last_line = Line::new(first.coord, last.coord);
let (farthest_index, farthest_distance) = rdp_indices
.iter()
.enumerate()
.take(rdp_indices.len() - 1)
.skip(1)
.map(|(index, rdp_index)| (index, rdp_index.coord.euclidean_distance(&first_last_line)))
.fold(
(0usize, T::zero()),
|(farthest_index, farthest_distance), (index, distance)| {
if distance > farthest_distance {
(index, distance)
} else {
(farthest_index, farthest_distance)
}
},
);
if farthest_distance > *epsilon {
let mut intermediate = compute_rdp(&rdp_indices[..=farthest_index], &*epsilon);
intermediate.pop();
intermediate.extend_from_slice(&compute_rdp(&rdp_indices[farthest_index..], &*epsilon));
intermediate
} else {
vec![first, last]
}
}
pub trait Simplify<T, Epsilon = T> {
fn simplify(&self, epsilon: &T) -> Self
where
T: GeoFloat;
}
pub trait SimplifyIdx<T, Epsilon = T> {
fn simplify_idx(&self, epsilon: &T) -> Vec<usize>
where
T: GeoFloat;
}
impl<T> Simplify<T> for LineString<T>
where
T: GeoFloat,
{
fn simplify(&self, epsilon: &T) -> Self {
LineString::from(rdp(self.coords_iter(), epsilon))
}
}
impl<T> SimplifyIdx<T> for LineString<T>
where
T: GeoFloat,
{
fn simplify_idx(&self, epsilon: &T) -> Vec<usize> {
calculate_rdp_indices(
&self
.0
.iter()
.enumerate()
.map(|(idx, coord)| RdpIndex {
index: idx,
coord: *coord,
})
.collect::<Vec<RdpIndex<T>>>(),
epsilon,
)
}
}
impl<T> Simplify<T> for MultiLineString<T>
where
T: GeoFloat,
{
fn simplify(&self, epsilon: &T) -> Self {
MultiLineString(self.iter().map(|l| l.simplify(epsilon)).collect())
}
}
impl<T> Simplify<T> for Polygon<T>
where
T: GeoFloat,
{
fn simplify(&self, epsilon: &T) -> Self {
Polygon::new(
self.exterior().simplify(epsilon),
self.interiors()
.iter()
.map(|l| l.simplify(epsilon))
.collect(),
)
}
}
impl<T> Simplify<T> for MultiPolygon<T>
where
T: GeoFloat,
{
fn simplify(&self, epsilon: &T) -> Self {
MultiPolygon(self.iter().map(|p| p.simplify(epsilon)).collect())
}
}
#[cfg(test)]
mod test {
use super::*;
use crate::{line_string, polygon};
#[test]
fn rdp_test() {
let vec = vec![
Coordinate { x: 0.0, y: 0.0 },
Coordinate { x: 5.0, y: 4.0 },
Coordinate { x: 11.0, y: 5.5 },
Coordinate { x: 17.3, y: 3.2 },
Coordinate { x: 27.8, y: 0.1 },
];
let compare = vec![
Coordinate { x: 0.0, y: 0.0 },
Coordinate { x: 5.0, y: 4.0 },
Coordinate { x: 11.0, y: 5.5 },
Coordinate { x: 27.8, y: 0.1 },
];
let simplified = rdp(vec.into_iter(), &1.0);
assert_eq!(simplified, compare);
}
#[test]
fn rdp_test_empty_linestring() {
let vec = Vec::new();
let compare = Vec::new();
let simplified = rdp(vec.into_iter(), &1.0);
assert_eq!(simplified, compare);
}
#[test]
fn rdp_test_two_point_linestring() {
let vec = vec![
Coordinate { x: 0.0, y: 0.0 },
Coordinate { x: 27.8, y: 0.1 },
];
let compare = vec![
Coordinate { x: 0.0, y: 0.0 },
Coordinate { x: 27.8, y: 0.1 },
];
let simplified = rdp(vec.into_iter(), &1.0);
assert_eq!(simplified, compare);
}
#[test]
fn multilinestring() {
let mline = MultiLineString(vec![LineString::from(vec![
(0.0, 0.0),
(5.0, 4.0),
(11.0, 5.5),
(17.3, 3.2),
(27.8, 0.1),
])]);
let mline2 = mline.simplify(&1.0);
assert_eq!(
mline2,
MultiLineString(vec![LineString::from(vec![
(0.0, 0.0),
(5.0, 4.0),
(11.0, 5.5),
(27.8, 0.1),
])])
);
}
#[test]
fn polygon() {
let poly = polygon![
(x: 0., y: 0.),
(x: 0., y: 10.),
(x: 5., y: 11.),
(x: 10., y: 10.),
(x: 10., y: 0.),
(x: 0., y: 0.),
];
let poly2 = poly.simplify(&2.);
assert_eq!(
poly2,
polygon![
(x: 0., y: 0.),
(x: 0., y: 10.),
(x: 10., y: 10.),
(x: 10., y: 0.),
(x: 0., y: 0.),
],
);
}
#[test]
fn multipolygon() {
let mpoly = MultiPolygon(vec![polygon![
(x: 0., y: 0.),
(x: 0., y: 10.),
(x: 5., y: 11.),
(x: 10., y: 10.),
(x: 10., y: 0.),
(x: 0., y: 0.),
]]);
let mpoly2 = mpoly.simplify(&2.);
assert_eq!(
mpoly2,
MultiPolygon(vec![polygon![
(x: 0., y: 0.),
(x: 0., y: 10.),
(x: 10., y: 10.),
(x: 10., y: 0.),
(x: 0., y: 0.)
]]),
);
}
#[test]
fn simplify_negative_epsilon() {
let ls = line_string![
(x: 0., y: 0.),
(x: 0., y: 10.),
(x: 5., y: 11.),
(x: 10., y: 10.),
(x: 10., y: 0.),
];
let simplified = ls.simplify(&-1.0);
assert_eq!(ls, simplified);
}
#[test]
fn simplify_idx_negative_epsilon() {
let ls = line_string![
(x: 0., y: 0.),
(x: 0., y: 10.),
(x: 5., y: 11.),
(x: 10., y: 10.),
(x: 10., y: 0.),
];
let indices = ls.simplify_idx(&-1.0);
assert_eq!(vec![0usize, 1, 2, 3, 4], indices);
}
}