diff options
| -rw-r--r-- | src/chebyshev.rs | 14 | ||||
| -rw-r--r-- | src/coords.rs | 25 | ||||
| -rw-r--r-- | src/euclid.rs | 20 | ||||
| -rw-r--r-- | src/exhaustive.rs | 4 | ||||
| -rw-r--r-- | src/kd.rs | 92 | ||||
| -rw-r--r-- | src/lib.rs | 6 | ||||
| -rw-r--r-- | src/lp.rs | 19 | ||||
| -rw-r--r-- | src/taxi.rs | 14 | ||||
| -rw-r--r-- | src/vp.rs | 8 |
9 files changed, 84 insertions, 118 deletions
diff --git a/src/chebyshev.rs b/src/chebyshev.rs index f6eba8a..a01b24f 100644 --- a/src/chebyshev.rs +++ b/src/chebyshev.rs @@ -1,7 +1,8 @@ //! [Chebyshev distance](https://en.wikipedia.org/wiki/Chebyshev_distance). -use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates}; +use crate::coords::Coordinates; use crate::distance::{Metric, Proximity}; +use crate::lp::Minkowski; use num_traits::{zero, Signed}; @@ -104,15 +105,12 @@ impl<T: Coordinates> Metric<T> for Chebyshev<T> {} impl<T: Coordinates> Metric<Chebyshev<T>> for T {} -impl<T: Coordinates> CoordinateProximity<T::Value> for Chebyshev<T> { - type Distance = T::Value; +/// Chebyshev distance is a [Minkowski] distance. +impl<T: Coordinates> Minkowski for Chebyshev<T> {} - fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance { - chebyshev_distance(self, coords) - } -} +impl<T: Coordinates> Minkowski<T> for Chebyshev<T> {} -impl<T: Coordinates> CoordinateMetric<T::Value> for Chebyshev<T> {} +impl<T: Coordinates> Minkowski<Chebyshev<T>> for T {} #[cfg(test)] mod tests { diff --git a/src/coords.rs b/src/coords.rs index 2e292ae..7c83946 100644 --- a/src/coords.rs +++ b/src/coords.rs @@ -1,6 +1,6 @@ //! [Coordinate spaces](https://en.wikipedia.org/wiki/Cartesian_coordinate_system). -use crate::distance::{Distance, Value}; +use crate::distance::Value; /// A coordinate space. pub trait Coordinates { @@ -88,26 +88,3 @@ impl<T: ?Sized + Coordinates> Coordinates for &T { (*self).coord(i) } } - -/// Types that support computing distances to raw slices of coordinates. -pub trait CoordinateProximity<T> { - type Distance: Distance; - - /// Compute the distance to a point specified by its coordinates. - fn distance_to_coords(&self, coords: &[T]) -> Self::Distance; -} - -/// Blanket [`CoordinateProximity`] implementation for references. -impl<T: CoordinateProximity<U>, U> CoordinateProximity<U> for &T { - type Distance = T::Distance; - - fn distance_to_coords(&self, coords: &[U]) -> Self::Distance { - (*self).distance_to_coords(coords) - } -} - -/// Marker trait for coordinate proximities that are [metrics][crate::distance::Metric]. -pub trait CoordinateMetric<T>: CoordinateProximity<T> {} - -/// Blanket [`CoordinateMetric`] implementation for references. -impl<T: CoordinateMetric<U>, U> CoordinateMetric<U> for &T {} diff --git a/src/euclid.rs b/src/euclid.rs index 3833146..3ec0af9 100644 --- a/src/euclid.rs +++ b/src/euclid.rs @@ -1,7 +1,8 @@ //! [Euclidean space](https://en.wikipedia.org/wiki/Euclidean_space). -use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates}; +use crate::coords::Coordinates; use crate::distance::{Distance, Metric, Proximity, Value}; +use crate::lp::Minkowski; use num_traits::zero; @@ -128,19 +129,20 @@ where EuclideanDistance<T::Value>: Distance, {} -impl<T> CoordinateProximity<T::Value> for Euclidean<T> +/// Euclidean distance is a [Minkowski] distance. +impl<T> Minkowski for Euclidean<T> where T: Coordinates, EuclideanDistance<T::Value>: Distance, -{ - type Distance = EuclideanDistance<T::Value>; +{} - fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance { - euclidean_distance(self, coords) - } -} +impl<T> Minkowski<T> for Euclidean<T> +where + T: Coordinates, + EuclideanDistance<T::Value>: Distance, +{} -impl<T> CoordinateMetric<T::Value> for Euclidean<T> +impl<T> Minkowski<Euclidean<T>> for T where T: Coordinates, EuclideanDistance<T::Value>: Distance, diff --git a/src/exhaustive.rs b/src/exhaustive.rs index 221641c..37af4c6 100644 --- a/src/exhaustive.rs +++ b/src/exhaustive.rs @@ -80,10 +80,10 @@ impl<K: Proximity<V>, V> ExactNeighbors<K, V> for ExhaustiveSearch<V> {} pub mod tests { use super::*; - use crate::tests::test_nearest_neighbors; + use crate::tests::test_exact_neighbors; #[test] fn test_exhaustive_index() { - test_nearest_neighbors(ExhaustiveSearch::from_iter); + test_exact_neighbors(ExhaustiveSearch::from_iter); } } @@ -1,10 +1,13 @@ //! [k-d trees](https://en.wikipedia.org/wiki/K-d_tree). -use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates}; -use crate::distance::{Metric, Proximity}; +use crate::coords::Coordinates; +use crate::distance::Proximity; +use crate::lp::Minkowski; use crate::util::Ordered; use crate::{ExactNeighbors, NearestNeighbors, Neighborhood}; +use num_traits::Signed; + use std::iter::FromIterator; use std::ops::Deref; @@ -86,7 +89,7 @@ pub trait KdProximity<V: ?Sized = Self> where Self: Coordinates<Value = V::Value>, Self: Proximity<V>, - Self: CoordinateProximity<V::Value, Distance = <Self as Proximity<V>>::Distance>, + Self::Value: PartialOrd<Self::Distance>, V: Coordinates, {} @@ -95,31 +98,14 @@ impl<K, V> KdProximity<V> for K where K: Coordinates<Value = V::Value>, K: Proximity<V>, - K: CoordinateProximity<V::Value, Distance = <K as Proximity<V>>::Distance>, - V: Coordinates, -{} - -/// Marker trait for [`Metric`] implementations that are compatible with k-d tree. -pub trait KdMetric<V: ?Sized = Self> -where - Self: KdProximity<V>, - Self: Metric<V>, - Self: CoordinateMetric<V::Value>, - V: Coordinates, -{} - -/// Blanket [`KdMetric`] implementation. -impl<K, V> KdMetric<V> for K -where - K: KdProximity<V>, - K: Metric<V>, - K: CoordinateMetric<V::Value>, + K::Value: PartialOrd<K::Distance>, V: Coordinates, {} trait KdSearch<K, V, N>: Copy where K: KdProximity<V>, + K::Value: PartialOrd<K::Distance>, V: Coordinates + Copy, N: Neighborhood<K, V>, { @@ -133,41 +119,29 @@ where fn right(self) -> Option<Self>; /// Recursively search for nearest neighbors. - fn search(self, level: usize, closest: &mut [V::Value], neighborhood: &mut N) { + fn search(self, level: usize, neighborhood: &mut N) { let item = self.item(); neighborhood.consider(item); let target = neighborhood.target(); - if target.coord(level) <= item.coord(level) { - self.search_near(self.left(), level, closest, neighborhood); - self.search_far(self.right(), level, closest, neighborhood); + let bound = target.coord(level) - item.coord(level); + let (near, far) = if bound.is_negative() { + (self.left(), self.right()) } else { - self.search_near(self.right(), level, closest, neighborhood); - self.search_far(self.left(), level, closest, neighborhood); - } - } + (self.right(), self.left()) + }; + + let next = (level + 1) % self.item().dims(); - /// Search the subtree closest to the target. - fn search_near(self, near: Option<Self>, level: usize, closest: &mut [V::Value], neighborhood: &mut N) { if let Some(near) = near { - let next = (level + 1) % self.item().dims(); - near.search(next, closest, neighborhood); + near.search(next, neighborhood); } - } - /// Search the subtree farthest from the target. - fn search_far(self, far: Option<Self>, level: usize, closest: &mut [V::Value], neighborhood: &mut N) { if let Some(far) = far { - // Update the closest possible point - let item = self.item(); - let target = neighborhood.target(); - let saved = std::mem::replace(&mut closest[level], item.coord(level)); - if neighborhood.contains(target.distance_to_coords(closest)) { - let next = (level + 1) % item.dims(); - far.search(next, closest, neighborhood); + if neighborhood.contains(bound.abs()) { + far.search(next, neighborhood); } - closest[level] = saved; } } } @@ -175,6 +149,7 @@ where impl<'a, K, V, N> KdSearch<K, &'a V, N> for &'a KdNode<V> where K: KdProximity<&'a V>, + K::Value: PartialOrd<K::Distance>, V: Coordinates, N: Neighborhood<K, &'a V>, { @@ -315,6 +290,7 @@ impl<T> IntoIterator for KdTree<T> { impl<K, V> NearestNeighbors<K, V> for KdTree<V> where K: KdProximity<V>, + K::Value: PartialOrd<K::Distance>, V: Coordinates, { fn search<'k, 'v, N>(&'v self, mut neighborhood: N) -> N @@ -324,16 +300,17 @@ where N: Neighborhood<&'k K, &'v V>, { if let Some(root) = &self.root { - let mut closest = neighborhood.target().as_vec(); - root.search(0, &mut closest, &mut neighborhood); + root.search(0, &mut neighborhood); } neighborhood } } +/// k-d trees are exact for [Minkowski] distances. impl<K, V> ExactNeighbors<K, V> for KdTree<V> where - K: KdMetric<V>, + K: KdProximity<V> + Minkowski<V>, + K::Value: PartialOrd<K::Distance>, V: Coordinates, {} @@ -389,6 +366,7 @@ impl<T: Coordinates> FlatKdNode<T> { impl<'a, K, V, N> KdSearch<K, &'a V, N> for &'a [FlatKdNode<V>] where K: KdProximity<&'a V>, + K::Value: PartialOrd<K::Distance>, V: Coordinates, N: Neighborhood<K, &'a V>, { @@ -465,6 +443,7 @@ impl<T> IntoIterator for FlatKdTree<T> { impl<K, V> NearestNeighbors<K, V> for FlatKdTree<V> where K: KdProximity<V>, + K::Value: PartialOrd<K::Distance>, V: Coordinates, { fn search<'k, 'v, N>(&'v self, mut neighborhood: N) -> N @@ -474,18 +453,17 @@ where N: Neighborhood<&'k K, &'v V>, { if !self.nodes.is_empty() { - let mut closest = neighborhood.target().as_vec(); - self.nodes - .as_slice() - .search(0, &mut closest, &mut neighborhood); + self.nodes.as_slice().search(0, &mut neighborhood); } neighborhood } } +/// k-d trees are exact for [Minkowski] distances. impl<K, V> ExactNeighbors<K, V> for FlatKdTree<V> where - K: KdMetric<V>, + K: KdProximity<V> + Minkowski<V>, + K::Value: PartialOrd<K::Distance>, V: Coordinates, {} @@ -493,16 +471,16 @@ where mod tests { use super::*; - use crate::tests::test_nearest_neighbors; + use crate::tests::test_exact_neighbors; #[test] fn test_kd_tree() { - test_nearest_neighbors(KdTree::from_iter); + test_exact_neighbors(KdTree::from_iter); } #[test] fn test_unbalanced_kd_tree() { - test_nearest_neighbors(|points| { + test_exact_neighbors(|points| { let mut tree = KdTree::new(); for point in points { tree.push(point); @@ -513,6 +491,6 @@ mod tests { #[test] fn test_flat_kd_tree() { - test_nearest_neighbors(FlatKdTree::from_iter); + test_exact_neighbors(FlatKdTree::from_iter); } } @@ -464,10 +464,10 @@ pub mod tests { type Point = Euclidean<[f32; 3]>; - /// Test a [NearestNeighbors] implementation. - pub fn test_nearest_neighbors<T, F>(from_iter: F) + /// Test an [ExactNeighbors] implementation. + pub fn test_exact_neighbors<T, F>(from_iter: F) where - T: NearestNeighbors<Point>, + T: ExactNeighbors<Point>, F: Fn(Vec<Point>) -> T, { test_empty(&from_iter); @@ -1,6 +1,10 @@ -//! [`$L^p$` spaces](https://en.wikipedia.org/wiki/Lp_space). +//! [`$\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; @@ -25,7 +29,7 @@ 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 [`$L^p$` distance] between two points. +/// Compute the [`$\ell^p$`]/[Minkowski] distance between two points. /// /// ```math /// \begin{aligned} @@ -34,7 +38,8 @@ pub use crate::chebyshev::chebyshev_distance as linf_distance; /// \end{aligned} /// ``` /// -/// [`$L^p$` distance]: https://en.wikipedia.org/wiki/Lp_space +/// [`$\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, @@ -51,6 +56,14 @@ where 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::*; diff --git a/src/taxi.rs b/src/taxi.rs index 7c33ecb..e189a36 100644 --- a/src/taxi.rs +++ b/src/taxi.rs @@ -1,7 +1,8 @@ //! [Taxicab (Manhattan) distance](https://en.wikipedia.org/wiki/Taxicab_geometry). -use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates}; +use crate::coords::Coordinates; use crate::distance::{Metric, Proximity}; +use crate::lp::Minkowski; use num_traits::{zero, Signed}; @@ -100,15 +101,12 @@ impl<T: Coordinates> Metric<T> for Taxicab<T> {} impl<T: Coordinates> Metric<Taxicab<T>> for T {} -impl<T: Coordinates> CoordinateProximity<T::Value> for Taxicab<T> { - type Distance = T::Value; +/// Taxicab distance is a [Minkowski] distance. +impl<T: Coordinates> Minkowski for Taxicab<T> {} - fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance { - taxicab_distance(self, coords) - } -} +impl<T: Coordinates> Minkowski<T> for Taxicab<T> {} -impl<T: Coordinates> CoordinateMetric<T::Value> for Taxicab<T> {} +impl<T: Coordinates> Minkowski<Taxicab<T>> for T {} #[cfg(test)] mod tests { @@ -532,16 +532,16 @@ where mod tests { use super::*; - use crate::tests::test_nearest_neighbors; + use crate::tests::test_exact_neighbors; #[test] fn test_vp_tree() { - test_nearest_neighbors(VpTree::from_iter); + test_exact_neighbors(VpTree::from_iter); } #[test] fn test_unbalanced_vp_tree() { - test_nearest_neighbors(|points| { + test_exact_neighbors(|points| { let mut tree = VpTree::new(); for point in points { tree.push(point); @@ -552,6 +552,6 @@ mod tests { #[test] fn test_flat_vp_tree() { - test_nearest_neighbors(FlatVpTree::from_iter); + test_exact_neighbors(FlatVpTree::from_iter); } } |