曼哈顿距离与切比雪夫距离及其相互转化
程序员文章站
2022-03-21 21:11:13
本文只讨论二维空间中的曼哈顿距离与切比雪夫距离 曼哈顿距离 定义 设平面空间内存在两点,它们的坐标为$(x1,y1)$,$(x2,y2)$ 则$dis=|x1-x2|+|y1-y2|$ 即两点横纵坐标差之和 煮个栗子 如图所示,图中$A,B$两点的曼哈顿距离为$AC+BC=4+3=7$ 切比雪夫距离 ......
本文只讨论二维空间中的曼哈顿距离与切比雪夫距离
曼哈顿距离 定义设平面空间内存在两点,它们的坐标为$(x1,y1)$,$(x2,y2)$
则$dis=|x1-x2|+|y1-y2|$
即两点横纵坐标差之和
煮个栗子如图所示,图中$A,B$两点的曼哈顿距离为$AC+BC=4+3=7$
切比雪夫距离 定义
设平面空间内存在两点,它们的坐标为$(x1,y1)$,$(x2,y2)$
则$dis=max(|x1-x2|,|y1-y2|)$
即两点横纵坐标差的最大值
$dis=max(AC,BC)=AC=4$
两者之间的关系
两者的定义看上去好像毛线关系都没有,但实际上,这两种距离可以相互转化!
我们考虑最简单的情况,在一个二维坐标系中,设原点为$(0,0)$
如果用曼哈顿距离表示,则与原点距离为$1$的点会构成一个边长为$1$的正方形
如果用切比雪夫距离表示,则与原点距离为$1$的点会构成一个边长为$2$的正方形
仔细对比这两个图形,你会发现什么?
没错!
第二个图像是由第一个图像放大两倍后旋转$45^{\circ}$得到的
然后根据向量矩阵什么乱七八糟的可以得到
第一个图中的点$(x,y)$对应第二个图中的点$(\dfrac{x+y}{2},\dfrac{x-y}{2})$
这样我们就可以将其进行互相转换了
上一篇: 设计模式漫谈之中介者模式
下一篇: 选择排序(正序倒序)解读