acap/
lp.rs

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
//! [`$\ell^p$`]/[Minkowski] distance.
//!
//! [`$\ell^p$`]: https://en.wikipedia.org/wiki/Lp_space
//! [Minkowski]: https://en.wikipedia.org/wiki/Minkowski_distance

use crate::coords::Coordinates;
use crate::distance::Proximity;

use num_traits::real::Real;
use num_traits::zero;

/// A point in L<sup>1</sup> space.
pub use crate::taxi::Taxicab as L1;

/// Compute the L<sup>1</sup> distance between two points.
pub use crate::taxi::taxicab_distance as l1_distance;

/// A point in L<sup>2</sup> space.
pub use crate::euclid::Euclidean as L2;
/// An L<sup>2</sup> distance.
pub use crate::euclid::EuclideanDistance as L2Distance;

/// Compute the L<sup>2</sup> distance between two points.
pub use crate::euclid::euclidean_distance as l2_distance;

/// A point in L<sup>∞</sup> space.
pub use crate::chebyshev::Chebyshev as Linf;

/// Compute the L<sup>∞</sup> distance between two points.
pub use crate::chebyshev::chebyshev_distance as linf_distance;

/// Compute the [`$\ell^p$`]/[Minkowski] distance between two points.
///
/// ```math
/// \begin{aligned}
/// \mathrm{lp\_distance}(p, x, y) &= \|x - y\|_p \\
/// &= \left( \sum_i |x_i - y_i|^p \right)^{1/p}
/// \end{aligned}
/// ```
///
/// [`$\ell^p$`]: https://en.wikipedia.org/wiki/Lp_space
/// [Minkowski]: https://en.wikipedia.org/wiki/Minkowski_distance
pub fn lp_distance<T, U>(p: T::Value, x: T, y: U) -> T::Value
where
    T: Coordinates,
    U: Coordinates<Value = T::Value>,
    T::Value: Real,
{
    debug_assert!(x.dims() == y.dims());

    let mut sum: T::Value = zero();
    for i in 0..x.dims() {
        sum += (x.coord(i) - y.coord(i)).abs().powf(p);
    }

    sum.powf(p.recip())
}

/// Marker trait for [Minkowski distances].
///
/// [Minkowski distances]: https://en.wikipedia.org/wiki/Minkowski_distance
pub trait Minkowski<T: ?Sized = Self>: Proximity<T> {}

/// Blanket [`Minkowski`] implementation for references.
impl<'k, 'v, K: Minkowski<V>, V> Minkowski<&'v V> for &'k K {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lp_distance() {
        assert_eq!(l1_distance(&[0.0, 0.0], &[3.0, 4.0]), 7.0);
        assert_eq!(l2_distance(&[0.0, 0.0], &[3.0, 4.0]), 5.0);
        assert!(lp_distance(3.0, &[0.0, 0.0], &[3.0, 4.0]) < 5.0);
        assert_eq!(linf_distance(&[0.0, 0.0], &[3.0, 4.0]), 4.0);
    }
}