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

[w88975]

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

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

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

[sneezry]

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

[Valyrian]

Voronoi diagram

[sumhat]

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

[Gonster]

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

[lancelot]

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

[w88975]

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

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]

@sneezry 排列是无序的

[rtyurtyu]

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