use crate::coords_iter::CoordsIter;
use crate::euclidean_distance::EuclideanDistance;
use crate::{GeoFloat, LineString, Point};
use num_traits::FromPrimitive;
pub trait FrechetDistance<T, Rhs = Self> {
fn frechet_distance(&self, rhs: &Rhs) -> T;
}
impl<T> FrechetDistance<T, LineString<T>> for LineString<T>
where
T: GeoFloat + FromPrimitive,
{
fn frechet_distance(&self, ls: &LineString<T>) -> T {
if self.coords_count() != 0 && ls.coords_count() != 0 {
let mut data = Data {
cache: vec![vec![T::nan(); ls.coords_count()]; self.coords_count()],
ls_a: self,
ls_b: ls,
};
data.compute(self.coords_count() - 1, ls.coords_count() - 1)
} else {
T::zero()
}
}
}
struct Data<'a, T>
where
T: GeoFloat + FromPrimitive,
{
cache: Vec<Vec<T>>,
ls_a: &'a LineString<T>,
ls_b: &'a LineString<T>,
}
impl<'a, T> Data<'a, T>
where
T: GeoFloat + FromPrimitive,
{
fn compute(&mut self, i: usize, j: usize) -> T {
if self.cache[i][j].is_nan() {
let eucl = Point::from(self.ls_a[i]).euclidean_distance(&Point::from(self.ls_b[j]));
self.cache[i][j] = match (i, j) {
(0, 0) => eucl,
(_, 0) => self.compute(i - 1, 0).max(eucl),
(0, _) => self.compute(0, j - 1).max(eucl),
(_, _) => ((self.compute(i - 1, j).min(self.compute(i - 1, j - 1)))
.min(self.compute(i, j - 1)))
.max(eucl),
};
}
self.cache[i][j]
}
}
#[cfg(test)]
mod test {
use crate::euclidean_distance::EuclideanDistance;
use crate::FrechetDistance;
use crate::LineString;
#[test]
fn test_single_point_in_linestring() {
let ls_a = LineString::from(vec![(1., 1.)]);
let ls_b = LineString::from(vec![(0., 2.)]);
assert_relative_eq!(
(ls_a.clone().into_points())[0].euclidean_distance(&(&ls_b.clone().into_points())[0]),
ls_a.frechet_distance(&ls_b)
);
}
#[test]
fn test_identical_linestrings() {
let ls_a = LineString::from(vec![(1., 1.), (2., 1.), (2., 2.)]);
let ls_b = LineString::from(vec![(1., 1.), (2., 1.), (2., 2.)]);
assert_relative_eq!(0., ls_a.frechet_distance(&ls_b));
}
#[test]
fn different_dimensions_linestrings() {
let ls_a = LineString::from(vec![(1., 1.)]);
let ls_b = LineString::from(vec![(2., 2.), (0., 1.)]);
assert_relative_eq!(2f64.sqrt(), ls_a.frechet_distance(&ls_b));
}
#[test]
fn test_frechet_1() {
let ls_a = LineString::from(vec![(1., 1.), (2., 1.)]);
let ls_b = LineString::from(vec![(2., 2.), (2., 3.)]);
assert_relative_eq!(2., ls_a.frechet_distance(&ls_b));
}
#[test]
fn test_frechet_2() {
let ls_a = LineString::from(vec![(1., 1.), (2., 1.), (2., 2.)]);
let ls_b = LineString::from(vec![(2., 2.), (0., 1.), (2., 4.)]);
assert_relative_eq!(2., ls_a.frechet_distance(&ls_b));
}
}