计算二维数组中最接近的值

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3869 天前的主题，其中的信息可能已经有所发展或是发生改变。

有一组二维数组
如[[1,1], [2,3], [5,4],[7,4],[6,1],[7,6]] 没有重复的值

我现在有一个坐标为 [4,4] 我要找出该坐标在二维数组中最接近的值:
比如上面的计算出来最接近的值是[5,4]. （假如有N个数值最接近，也就是说对比x,y的绝对值是一样的,只取其中随便一个就行了列出多个也可以）.

这个算法该怎么算呢? 第一次接触到这种问题，比较头疼。

数组

坐标

接近

8 条回复 2015-05-23 00:59:27 +08:00

sneezry

2015-05-22 04:11:36 +08:00 via iPhone

已知点的排列顺序是怎样的呢

Valyrian

2015-05-22 05:45:09 +08:00 via iPhone

Voronoi diagram

sumhat

2015-05-22 05:49:28 +08:00

有序可以二分，无序只能遍历了

Gonster

2015-05-22 08:43:14 +08:00 via iPhone

如果允许用其他数据结构可以考虑使用QuadTree或者其他的一些树来替代数组

lancelot

2015-05-22 09:28:16 +08:00

不能简单点就用平面点距离公式都遍历一次吗？

w88975

2015-05-22 11:05:45 +08:00

我自己写了一个比对的算法不知道还有没有优化的余地

var min = Math.abs((xy.x - points[1].x)) + Math.abs((xy.y - points[1].y));
for(var i = 1; i< points.length; i++) {
if (Math.abs((xy.x - points[i].x)) >= 0.03 || Math.abs((xy.y - points[i].y)) >= 0.03) {

}
else {
if ( Math.abs((xy.x - points[i].x)) + Math.abs((xy.y - points[i].y)) < min) {
min = Math.abs((xy.x - points[i].x)) + Math.abs((xy.y - points[i].y));
pos = i;
}
}
}

w88975

2015-05-22 12:24:45 +08:00

@sneezry 排列是无序的

rtyurtyu

2015-05-23 00:59:27 +08:00

O(1)的时间就能得出，那些遍历的就歇歇吧