summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/chebyshev.rs14
-rw-r--r--src/coords.rs25
-rw-r--r--src/euclid.rs20
-rw-r--r--src/exhaustive.rs4
-rw-r--r--src/kd.rs92
-rw-r--r--src/lib.rs6
-rw-r--r--src/lp.rs19
-rw-r--r--src/taxi.rs14
-rw-r--r--src/vp.rs8
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);
}
}
diff --git a/src/kd.rs b/src/kd.rs
index 291028e..dae73ec 100644
--- a/src/kd.rs
+++ b/src/kd.rs
@@ -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);
}
}
diff --git a/src/lib.rs b/src/lib.rs
index d6e5579..57f3dac 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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);
diff --git a/src/lp.rs b/src/lp.rs
index 4afd209..db9e65c 100644
--- a/src/lp.rs
+++ b/src/lp.rs
@@ -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 {
diff --git a/src/vp.rs b/src/vp.rs
index 85d3972..c44b323 100644
--- a/src/vp.rs
+++ b/src/vp.rs
@@ -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);
}
}