前言

今天在写工具类方法时写到了两个向量之间的距离算法，copilot 帮我写了下面的内容

    /** 两向量距离 */
    public static getLensBetweenTwoPos(pos1: Type.Vector, pos2: Type.Vector): number {
        return Math.abs(pos1.x - pos2.x) + Math.abs(pos1.y - pos2.y);
    }

我仔细一看，这不是计算了一个三角形的两个直角边的和嘛！少了平方和开根呀！但是一般这种算法copilot不会出错呀，所以我开始探究这个算法到底是怎么由来的

线索

我一开始先搜Math.abs(x1-x2)。紧接着一个StackOverflow的问题中，提问者询问关于如何获取difference in a point的问题映入眼帘，在问题的回答中，我发现了一个关键词Manhattan distance

于是乎，引入了这篇文章，以记录Manhattan distance（曼哈顿距离）的理解

正文

概念

计程车几何（Taxicab geometry）或曼哈顿距离（英语：Manhattan distance/Manhattan length）或方格线距离是由十九世纪的赫尔曼·闵可夫斯基所创辞汇，为欧几里得几何度量空间的几何学之用语，用以标明两个点上在标准坐标系上的绝对轴距之总和。

我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。

例如在平面上，坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：

url

要注意的是，曼哈顿距离依赖座标系统的旋转，而非系统在座标轴上的平移或映射。

曼哈顿距离的命名原因是从规划为方型建筑区块的城市（如曼哈顿）间，最短的行车路径而来（忽略曼哈顿的单向车道以及只存在于3、14大道的斜向车道）。任何往东三区块、往北六区块的的路径一定最少要走九区块，没有其他捷径。

计程车几何学满足除了SAS全等定理之外的希尔伯特几何公理。

用例

  • 早期计算性能有限的时候，浮点运算代价过大，又因为图是有像素的点组成，通过曼哈顿距离可以只计算整型和加减，从而大大提高性能。
  • 当你的数据集有离散和/或二进制属性时，曼哈顿似乎很好用，因为它考虑到了现实中在这些属性值内可以采取的路径。以欧氏距离为例，会在两个向量之间创建一条直线，而在现实中这可能实际上是不可能的

缺点

  • 虽然曼哈顿距离对于高维数据似乎还不错，但它是一个比欧几里得距离更不直观的测量方法，尤其是在高维数据中使用时
  • 而且，它比欧几里得距离更容易给出一个更高的距离值，因为它不可能是最短路径。这不一定会带来问题，但你应该考虑到这一点。