有一组二维数组
如[[1,1], [2,3], [5,4],[7,4],[6,1],[7,6]] 没有重复的值
我现在有一个坐标为 [4,4] 我要找出该坐标在二维数组中最接近的值:
比如上面的计算出来最接近的值 是[5,4]. （假如有N个数值最接近，也就是说对比x,y的绝对值是一样的,只取其中随便一个就行了 列出多个也可以）.
这个算法该怎么算呢? 第一次接触到这种问题，比较头疼。
This topic created in 4192 days ago, the information mentioned may be changed or developed.
 |
sneezryMay 22, 2015 via iPhone
1
已知点的排列顺序是怎样的呢
|
 |
2
Voronoi diagram
|
1 |
sumhatMay 22, 2015
3
有序可以二分，无序只能遍历了
|
 |
GonsterMay 22, 2015 via iPhone
4
如果允许用其他数据结构 可以考虑使用QuadTree或者其他的一些树来替代数组
|
 |
lancelotMay 22, 2015
5
不能简单点就用平面点距离公式都遍历一次吗？
|
 |
6
我自己写了一个比对的算法 不知道还有没有优化的余地
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; } } } |
 |
rtyurtyuMay 23, 2015
8
O(1)的时间就能得出，那些遍历的就歇歇吧
|
Select Language