曼哈顿距离和切比雪夫距离的转换

引言

假设有两个点$A(x_1,y_1)$，$B(x_2,y_2)$

曼哈顿距离 = $|x_1-x_2|+|y_1-y_2|$

切比雪夫距离 = $max(|x_1-x_2|,|y_1-y_2|)$

一个是折线的距离，一个是 x,y 方向上更大的那个距离，这二者有什么关系呢？

数学角度

∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ = m a x { x 1 − x 2 + y 1 − y 2 , x 1 − x 2 + y 2 − y 1 , x 2 − x 1 + y 1 − y 2 , x 2 − x 1 + y 2 − y 1 } = m a x ( ∣ ( x 1 + y 1 ) − ( x 2 + y 2 ) ∣ , ∣ ( x 1 − y 1 ) − ( x 2 − y 2 ) ∣ ) |x_1-x_2|+|y_1-y_2| = max\{x_1-x_2+y_1-y_2, x_1-x_2+y_2-y_1, x_2-x_1+y_1-y_2,x_2-x_1+y_2-y_1\} \\ = max(|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|) ∣x1​−x2​∣+∣y1​−y2​∣=max{x1​−x2​+y1​−y2​,x1​−x2​+y2​−y1​,x2​−x1​+y1​−y2​,x2​−x1​+y2​−y1​}=max(∣(x1​+y1​)−(x2​+y2​)∣,∣(x1​−y1​)−(x2​−y2​)∣)

即：$(x_1,y_1)$到$(x_2,y_2)$的曼哈顿距离 = $(x_1+y_1,x_1-y_1)$到$(x_2+y_2,x_2-y_2)$的切比雪夫距离

反过来，解一个二元一次方程组可得，$(x_1,y_1)$到$(x_2,y_2)$的切比雪夫距离 = $(\frac{x_1+y_1}{2},\frac{x_1-y_1}{2})$到$(\frac{x_2+y_2}{2},\frac{x_2-y_2}{2})$的曼哈顿距离

图形角度

红色是曼哈顿距离为 1 的点的集合，橙色是距离为 1 的切比雪夫距离的点的集合