Chinaunix首页 | 论坛 | 博客
  • 博客访问: 200568
  • 博文数量: 75
  • 博客积分: 3000
  • 博客等级: 中校
  • 技术积分: 970
  • 用 户 组: 普通用户
  • 注册时间: 2007-08-11 09:44
文章存档

2010年(5)

2009年(18)

2008年(52)

我的朋友

分类:

2010-05-13 11:37:41

Manhattan Distance Calculation(曼哈顿距离算法)
2007-08-23 16:01

首先介绍一下曼哈顿,曼哈顿是一个极为繁华的街区,高楼林立,街道纵横,从A地点到达B地点没有直线路径,必须绕道,而且至少要经C地点,走AC和CB才能到达,由于街道很规则,ACB就像一个直角3角形,AB是斜边,AC和CB是直角边,根据毕达格拉斯定理,或者向量理论,都可以知道用AC和CB可以表达AB的长度。
在早期的计算机图形学中,屏幕是由像素构成,是整数,点的坐标也一般是整数,原因是浮点运算很昂贵,很慢而且有误差,如果直接使用AB的距离,则必须要进行浮点运算,如果使用AC和CB,则只要计算加减法即可,这就大大提高了运算速度,而且不管累计运算多少次,都不会有误差。因此,计算机图形学就借用曼哈顿来命名这一表示方法。
在我们常用的平面CAD中,都会有格点,他是基本单位,定义了格点大小后,就可以使用整数来表示和运算,不会引入计算误差,又快又精确。
与此类似,在3维图形学中,空间向量也是用3个单位向量的和来表示的。

欧氏距离:

在二维和三维空间中的欧式距离的就是两点之间的距离,二维的公式是
d = sqrt((x1-x2)^+(y1-y2)^)
三维的公式是
d=sqrt(x1-x2)^+(y1-y2)^+z1-z2)^)
推广到n维空间,欧式距离的公式是
d=sqrt( ∑(xi1-xi2)^ ) 这里i=1,2..n
xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标


阅读(2666) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~