找到与给定点最近的点

Question

我已经搜遍了这个,但我似乎无法找到最好的方法.我有大约22000纬度/经度点,我想找到最接近iPhone当前位置的点.我见过有人问过Quad Trees,Dijkstra算法和空间数据库.哪种iPhone最好？空间数据库似乎最简单,但我不确定.

编辑:实际上有超过20,000点.您认为迭代所有这些是实现它的方法吗？但感谢您的投入.

谢谢.

Answer 1

实际上,最好对纬度/长点使用Haversine(大圆)计算,否则越来越大的距离将是错误的,特别是如果你使用Jherico的答案中的简单触发.

快速搜索提供了这个javascript示例:

var R = 6371; // km Radius of earth
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
        Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

就数据结构而言,Geohash值得关注.

Answer 2

如果你需要比O(N)更好,你只能在你第一次支付N lg N来构建某种空间哈希(四叉树,八叉树,哈希网格或类似物)时才能得到它.然后每个测试将大约为O(lg N),并且通常通过缓存您检查的最后位置可以更好,如果存在大量一致性(通常存在).

我可能会在Euler(地心,XYZ)空间中构建一个八叉树,因为这样可以让我获得"真实"距离,而不是"扭曲"纬度/经度距离.但是,实际上,lat/lon空间中的四叉树可能运行得很好.一旦你有一个命中,你坚持到那个树节点(假设树没有在运行时重建),下一个查询开始从该树节点走,只需要担心可能更接近的节点前一点远离前一个答案.