feat(distance): add Manhattan metric, rename types, add docs

thi-ng · Jan 21, 2021 · 4f0b199 · 4f0b199
1 parent 4a09a0f
commit 4f0b199
Show file tree

Hide file tree

Showing 6 changed files with 116 additions and 9 deletions.
diff --git a/packages/distance/src/api.ts b/packages/distance/src/api.ts
@@ -1,9 +1,18 @@
 import type { FnU2, IReset, Pair } from "@thi.ng/api";
 
+/**
+ * Distance metric function
+ */
 export type Metric<T> = FnU2<T, number>;
 
+/**
+ * Tuple of `[distance, T]`
+ */
 export type Neighbor<T> = Pair<number, T>;
 
+/**
+ * Distance metric implementation & conversions from/to raw distances.
+ */
 export interface IDistance<T> {
     /**
      * The actual distance function metric.

diff --git a/packages/distance/src/eucledian.ts b/packages/distance/src/eucledian.ts
@@ -1,5 +1,5 @@
 import { dist, dist2, dist3, ReadonlyVec } from "@thi.ng/vectors";
-import type { Metric, IDistance } from "./api";
+import type { IDistance, Metric } from "./api";
 
 export class Eucledian<T> implements IDistance<T> {
     constructor(public readonly metric: Metric<T>) {}
@@ -13,10 +13,22 @@ export class Eucledian<T> implements IDistance<T> {
     }
 }
 
+/**
+ * Eucledian distance metric for n-D vectors.
+ */
 export const EUCLEDIAN = new Eucledian<ReadonlyVec>(dist);
 
+/**
+ * Eucledian distance metric for numbers.
+ */
 export const EUCLEDIAN1 = new Eucledian<number>((a, b) => Math.abs(a - b));
 
+/**
+ * Eucledian distance metric for 2d vectors.
+ */
 export const EUCLEDIAN2 = new Eucledian<ReadonlyVec>(dist2);
 
+/**
+ * Eucledian distance metric for 3d vectors.
+ */
 export const EUCLEDIAN3 = new Eucledian<ReadonlyVec>(dist3);
diff --git a/packages/distance/src/index.ts b/packages/distance/src/index.ts
@@ -1,6 +1,7 @@
 export * from "./api";
 
 export * from "./eucledian";
+export * from "./manhattan";
 export * from "./squared";
 
 export * from "./knearest";

diff --git a/packages/distance/src/knearest.ts b/packages/distance/src/knearest.ts
@@ -12,8 +12,9 @@ import { DIST_SQ, DIST_SQ1, DIST_SQ2, DIST_SQ3 } from "./squared";
  * @remarks
  * The K-nearest neighbors will be accumulated via an internal
  * {@link @thi.ng/heaps#Heap} and results can be optionally returned in order of
- * proximity. For K=1 it will be more efficient to use {@link Nearest} to avoid
- * the additional overhead.
+ * proximity (via {@link KNearest.deref} or {@link KNearest.values}). For K=1 it
+ * will be more efficient to use {@link Nearest} to avoid the additional
+ * overhead.
  */
 export class KNearest<D, T>
     implements INeighborhood<D, T>, IDeref<Neighbor<T>[]> {

diff --git a/packages/distance/src/manhattan.ts b/packages/distance/src/manhattan.ts
@@ -0,0 +1,84 @@
+import {
+    distManhattan,
+    distManhattan2,
+    distManhattan3,
+    ReadonlyVec,
+} from "@thi.ng/vectors";
+import type { IDistance, Metric } from "./api";
+
+/**
+ * Manhattan distance metric and conversion to/from Eucledian distances.
+ *
+ * @remarks
+ * The conversion are always based on n-D squares, i.e. the assumption that the
+ * distance is equally shared in each dimension.
+ *
+ * E.g. a Manhattan distance of 30 could be obtained from [0,0] -> [10,20], but
+ * would be interpreted here as distance from [0,0] -> [15,15], which produces
+ * the same Manhattan value, but yields a different Eucledian result. For lack
+ * of any other information about the distance values, this is however the only
+ * way to approach conversion and is sufficient for the purposes of this
+ * package...
+ *
+ * @example
+ * ```ts
+ * MANHATTAN2.metric([0,0], [10,20])
+ * // 30
+ *
+ * MANHATTAN2.from(30);
+ * // 21.213203435596427
+ *
+ * Math.hypot(15, 15) // <-- diagonal of manhattan square
+ * // 21.213203435596427
+ *
+ * Math.hypot(10, 20) // <-- actual eucledian dist
+ * // 22.360679774997898
+ *
+ * MANHATTAN2.to(21.213203435596427)
+ * // 30
+ *
+ * // however, starting w/ eucledian dist first
+ * e = mag([10, 20])
+ * // 22.360679774997898
+ *
+ * m = MANHATTAN2.to(e)
+ * // 31.622776601683793
+ *
+ * MANHATTAN2.from(m) === e
+ * // true
+ * ```
+ */
+export class Manhattan<T> implements IDistance<T> {
+    protected _invD: number;
+
+    constructor(
+        public readonly dim: number,
+        public readonly metric: Metric<T>
+    ) {
+        this._invD = this.dim / Math.sqrt(dim);
+    }
+
+    to(x: number) {
+        return x * this._invD;
+    }
+
+    from(x: number) {
+        return Math.sqrt((x / this.dim) ** 2 * this.dim);
+    }
+}
+
+/**
+ * Returns a new Manhattan distance metric for n-D vectors of dimension `dim`.
+ */
+export const defManhattan = (dim: number) =>
+    new Manhattan<ReadonlyVec>(dim, distManhattan);
+
+/**
+ * Manhattan distance metric for 2d vectors.
+ */
+export const MANHATTAN2 = new Manhattan<ReadonlyVec>(2, distManhattan2);
+
+/**
+ * Manhattan distance metric for 3d vectors.
+ */
+export const MANHATTAN3 = new Manhattan<ReadonlyVec>(3, distManhattan3);
diff --git a/packages/distance/src/squared.ts b/packages/distance/src/squared.ts
@@ -1,7 +1,7 @@
 import { distSq, distSq2, distSq3, ReadonlyVec } from "@thi.ng/vectors";
-import type { Metric, IDistance } from "./api";
+import type { IDistance, Metric } from "./api";
 
-export class DistSquared<T> implements IDistance<T> {
+export class Squared<T> implements IDistance<T> {
     constructor(public readonly metric: Metric<T>) {}
 
     to(x: number) {
@@ -13,10 +13,10 @@ export class DistSquared<T> implements IDistance<T> {
     }
 }
 
-export const DIST_SQ = new DistSquared<ReadonlyVec>(distSq);
+export const DIST_SQ = new Squared<ReadonlyVec>(distSq);
 
-export const DIST_SQ1 = new DistSquared<number>((a, b) => (a - b) ** 2);
+export const DIST_SQ1 = new Squared<number>((a, b) => (a - b) ** 2);
 
-export const DIST_SQ2 = new DistSquared<ReadonlyVec>(distSq2);
+export const DIST_SQ2 = new Squared<ReadonlyVec>(distSq2);
 
-export const DIST_SQ3 = new DistSquared<ReadonlyVec>(distSq3);
+export const DIST_SQ3 = new Squared<ReadonlyVec>(distSq3);