问查找与给定点最近的点

EN

实际上，对于经度/长度点最好使用哈维正弦(大圆)计算，否则越来越大的距离将是错误的，特别是如果您使用简单的三角，如在Jherico's answer中。

快速搜索提供了以下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值得一看。

如果你需要比O(N)更好的，你只能在你首先为构建某种类型的空间散列(四叉树、八叉树、散列网格或类似的)而支付N lg N时才能得到。然后，每个测试将大约是O(lg N)，如果有很多一致性(通常是有)，可以通过缓存上一次检查的位置来做得更好。

我可能会在Euler (geocentric，XYZ)空间中构建一个八叉树，因为这允许我获得“真实”距离，而不是“扭曲”的经度/经度距离。然而，在实践中，在经度/经度空间中的四叉树可能会工作得足够好。一旦命中，您将保留该树节点(假设树在运行时没有重新构建)，并且下一个查询将从该树节点开始遍历，并且只需要担心如果上一个点移动到离前一个答案更远的地方，可能更近的节点。

当您在iPhone上时，您可以使用CoreLoaction来执行地理距离-使用CLLocation的– getDistanceFrom:

我很想使用2k点的线性搜索，如果这还不够快，可以切换到像GeoHash这样的东西来存储元数据来搜索你的点。