summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2020-05-28 17:10:03 -0400
committerTavian Barnes <tavianator@tavianator.com>2020-06-24 10:03:44 -0400
commit5deaaf8e584fbb8634ca3aa88852bc75b470e9a6 (patch)
tree555054738b29879abeb7f5a01d0d24330cc29e9f
parent97d64547f40f362120109fd23f647f15241c08d9 (diff)
downloadacap-5deaaf8e584fbb8634ca3aa88852bc75b470e9a6.tar.xz
taxi: Implement taxicab distance
-rw-r--r--src/lib.rs1
-rw-r--r--src/taxi.rs116
2 files changed, 117 insertions, 0 deletions
diff --git a/src/lib.rs b/src/lib.rs
index 2b3c8fe..8cce2d8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -95,6 +95,7 @@ pub mod distance;
pub mod euclid;
pub mod exhaustive;
pub mod kd;
+pub mod taxi;
pub mod vp;
mod util;
diff --git a/src/taxi.rs b/src/taxi.rs
new file mode 100644
index 0000000..be74fd3
--- /dev/null
+++ b/src/taxi.rs
@@ -0,0 +1,116 @@
+//! Taxicab (Manhattan) distance.
+
+use crate::coords::{Coordinates, CoordinateMetric, CoordinateProximity};
+use crate::distance::{Metric, Proximity};
+
+use num_traits::{zero, Signed};
+
+/// A point in taxicab space.
+///
+/// This wrapper equips any [coordinate space] with the [taxicab distance metric].
+///
+/// [coordinate space]: [Coordinates]
+/// [taxicab distance metric]: https://en.wikipedia.org/wiki/Taxicab_geometry
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub struct Taxicab<T>(pub T);
+
+impl<T> Taxicab<T> {
+ /// Wrap a point.
+ pub fn new(point: T) -> Self {
+ Self(point)
+ }
+
+ /// Unwrap a point.
+ pub fn inner(&self) -> &T {
+ &self.0
+ }
+
+ /// Unwrap a point.
+ pub fn into_inner(self) -> T {
+ self.0
+ }
+}
+
+impl<T: Coordinates> Coordinates for Taxicab<T> {
+ type Value = T::Value;
+
+ fn dims(&self) -> usize {
+ self.0.dims()
+ }
+
+ fn coord(&self, i: usize) -> Self::Value {
+ self.0.coord(i)
+ }
+}
+
+/// Compute the taxicab distance between two points.
+pub fn taxicab_distance<T, U>(x: T, y: U) -> T::Value
+where
+ T: Coordinates,
+ U: Coordinates<Value = T::Value>,
+{
+ debug_assert!(x.dims() == y.dims());
+
+ let mut sum = zero();
+ for i in 0..x.dims() {
+ sum += (x.coord(i) - y.coord(i)).abs();
+ }
+
+ sum
+}
+
+/// The taxicab distance function.
+impl<T: Coordinates> Proximity for Taxicab<T> {
+ type Distance = T::Value;
+
+ fn distance(&self, other: &Self) -> Self::Distance {
+ taxicab_distance(self, other)
+ }
+}
+
+impl<T: Coordinates> Proximity<T> for Taxicab<T> {
+ type Distance = T::Value;
+
+ fn distance(&self, other: &T) -> Self::Distance {
+ taxicab_distance(self, other)
+ }
+}
+
+impl<T: Coordinates> Proximity<Taxicab<T>> for T {
+ type Distance = T::Value;
+
+ fn distance(&self, other: &Taxicab<T>) -> Self::Distance {
+ taxicab_distance(self, other)
+ }
+}
+
+/// Taxicab distance is a metric.
+impl<T: Coordinates> Metric for Taxicab<T> {}
+
+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;
+
+ fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance {
+ taxicab_distance(self, coords)
+ }
+}
+
+impl<T: Coordinates> CoordinateMetric<T::Value> for Taxicab<T> {}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn test_distance() {
+ assert_eq!(taxicab_distance([-3, 4], [4, -3]), 14);
+
+ assert_eq!(Taxicab([-3, 4]).distance(&Taxicab([4, -3])), 14);
+ assert_eq!(Taxicab([-3, 4]).distance(&[4, -3]), 14);
+ assert_eq!([-3, 4].distance(&Taxicab([4, -3])), 14);
+ }
+}