这是一个创建于 3472 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一组二维数组
如[[1,1], [2,3], [5,4],[7,4],[6,1],[7,6]] 没有重复的值
我现在有一个坐标为 [4,4] 我要找出该坐标在二维数组中最接近的值:
比如上面的计算出来最接近的值 是[5,4]. （假如有N个数值最接近，也就是说对比x,y的绝对值是一样的,只取其中随便一个就行了 列出多个也可以）.
这个算法该怎么算呢? 第一次接触到这种问题，比较头疼。
 |
1
sneezry 2015-05-22 04:11:36 +08:00 via iPhone
已知点的排列顺序是怎样的呢
|
 |
2
Valyrian 2015-05-22 05:45:09 +08:00 via iPhone  1
Voronoi diagram
|
 |
3
sumhat 2015-05-22 05:49:28 +08:00
有序可以二分，无序只能遍历了
|
 |
4
Gonster 2015-05-22 08:43:14 +08:00 via iPhone
如果允许用其他数据结构 可以考虑使用QuadTree或者其他的一些树来替代数组
|
 |
5
lancelot 2015-05-22 09:28:16 +08:00
不能简单点就用平面点距离公式都遍历一次吗？
|
 |
6
w88975 OP 我自己写了一个比对的算法 不知道还有没有优化的余地
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; } } } |
 |
8
rtyurtyu 2015-05-23 00:59:27 +08:00
O(1)的时间就能得出，那些遍历的就歇歇吧
|
Select Language