欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

曼哈顿距离与切比雪夫距离及其相互转化

程序员文章站 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})$

这样我们就可以将其进行互相转换了