曼哈顿距离和切比雪夫距离的转换
引言
假设有两个点 A ( x 1 , y 1 ) A(x_1, y_1) A(x1,y1)， B ( x 2 , y 2 ) B(x_2,y_2) B(x2,y2)
曼哈顿距离 = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1-x_2|+|y_1-y_2| ∣x1−x2∣+∣y1−y2∣
切比雪夫距离 = m a x ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) max(|x_1-x_2|,|y_1-y_2|) max(∣x1−x2∣,∣y1−y2∣)
一个是折线的距离，一个是 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_1, y_1) (x1,y1)到 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)的曼哈顿距离 = ( x 1 + y 1 , x 1 − y 1 ) (x_1+y_1,x_1-y_1) (x1+y1,x1−y1)到 ( x 2 + y 2 , x 2 − y 2 ) (x_2+y_2,x_2-y_2) (x2+y2,x2−y2)的切比雪夫距离
反过来，解一个二元一次方程组可得， ( x 1 , y 1 ) (x_1, y_1) (x1,y1)到 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)的切比雪夫距离 = ( x 1 + y 1 2 , x 1 − y 1 2 ) (\frac{x_1+y_1}2,\frac{x_1-y_1}2) (2x1+y1,2x1−y1)到 ( x 2 + y 2 2 , x 2 − y 2 2 ) (\frac{x_2+y_2}2,\frac{x_2-y_2}2) (2x2+y2,2x2−y2)的曼哈顿距离
图形角度
红色是曼哈顿距离为 1 的点的集合，橙色是距离为 1 的切比雪夫距离的点的集合