美团如何查询附近商家

我们日常电脑美团或者饿了么点外卖，附近的商家几乎都是秒回的，最简单的理解，我们可以用经纬度来计算。

经纬度

谈到经纬度。想必大家在中学时代的地理课本里早就学过了。我们把地球分成纵横交错的一些格子，每个点都可以用横竖坐标来表示。横线表示纬度，范围在[-90°, +90°]，竖线表示经度，范围在[-180°, +180°]。

我们当前的经纬度，可以从wifi或者手机的GPS获取。

计算距离

接下来我们计算两点的距离。

地球是一个近乎标准的椭球体，它的赤道半径为6378.140千米，极半径为6356.755千米，平均半径6371.004千米。如果我们假设地球是一个完美的球体，那么它的半径就是地球的平均半径，记为R。如果以0度经线为基准，那么根据地球表面任意两点的经纬度就可以计算出这两点间的地表距离（这里忽略地球表面地形对计算带来的误差，仅仅是理论上的估算值）。

设第一点A的经纬度为(LonA, LatA)，第二点B的经纬度为(LonB, LatB)，按照0度经线的基准，东经取经度的正值(Longitude)，西经取经度负值(-Longitude)，北纬取90-纬度值(90-Latitude)，南纬取90+纬度值(90+Latitude)，则经过上述处理过后的两点被计为(MLonA, MLatA)和(MLonB, MLatB)。那么根据三角推导，可以得到计算两点距离的如下公式：

C = sin(MLatA)*sin(MLatB)*cos(MLonA-MLonB) + cos(MLatA)*cos(MLatB) Distance = R*Arccos(C)*Pi/180

google maps的脚本里代码

private const double EARTH_RADIUS = 6378.137;
private static double rad(double d)
{
    return d * Math.PI / 180.0;
}
public static double GetDistance(double lat1, double lng1, double lat2, double lng2)
{
    double radLat1 = rad(lat1);
    double radLat2 = rad(lat2);
    double a = radLat1 - radLat2;
    double b = rad(lng1) - rad(lng2);
    double s = 2 * Math.Asin(Math.Sqrt(Math.Pow(Math.Sin(a/2),2) + 
     Math.Cos(radLat1)*Math.Cos(radLat2)*Math.Pow(Math.Sin(b/2),2)));
    s = s * EARTH_RADIUS;
    s = Math.Round(s * 10000) / 10000;
    return s;
}

如果我们相距的两点不是特别远（相对地球半径而言），我们就可以把他们近似看成平面上的两点，可以用下面的公式计算距离：

当我们的商户不是太多的时候，就可以遍历所有商户，依次计算出所有的商户同我的距离d1 d2 ... dk，然后按照距离从小到大排序，得到我们想要的结果。

我们来算算时间复杂度。

1.遍历所有的点，计算距离，是一个O(n)复杂度的算法；

2.排序做TopN，按照快排来算的话，基本上是一个O(nlogn)的复杂度；

所以总的复杂度趋近于O(nlogn)。

那么当有大量商户的时候该怎么办呢？

方案一：简单的分布式计算：

将商铺信息进行分组，分别进行排序取出前N的推荐，最后把前面排序的结果，再进行一次TopN排序，这样就可以找到最近的商铺信息了。

这种实现方式简单，但是有几个比较严重的问题：

1. 随着商户的增长，进行的分组会越来越多，呈直线上升趋势；
2. 有时结果不会特别精确。假设全部的最优解都在某一个分组里，可能不会进到最后的归并排序里。

刚刚我们已经提到过了，我们用经线和纬线来分割地球，此时的地球已经被我们分成一块一块的了，我们看看下面这个图：

如同我们的红箭头指的那个点，要找到它附近的点，是不是直接取出它所在的经纬度格子的所有点就可以了呢？再加上围绕它所在格子的八个格子的所有点，那就一定是这个点周围的所有点了！

那么接下来就是如何给这些经纬度格子编码的问题了！

编码

我们用经度切割，以上海经纬度121.43333,34.50000来举例：

以0°为中轴，将地球切成两半[-180°,0°),[0°，180°]，并对他们进行二进制编码，左边为0，右边为1；

此时上海的经度编码就是1。

我们再切割一次，将精度切成[-180°,-90°),[-90°，0°),[0°,90°),[90°,180°],按照二进制编码，分别为：00，01，10，11

此时上海的经度编码就是11

如此这样重复N次，我们就可以将地球按经度切割成很多很多的小格子，如果切割的次数足够多，每一个格子相当于一个点，那也会得到对应这个小块儿的二进制编码。比如上海的的经度121.43333经过多次切割得到如下这个表格：

比如此时我们分割了8次，上海的经度编码就是11010110。随着切分的继续，我们可以得到更长的编码，这样就可以对应更细致的区间。

按照同样的方法，我们切割一下纬度，则上海的纬度34.50000可以得到如下表格编码：

上海的纬度编码就是：10110001

最终我们得到的上海经纬度编码为

（121.43333,34.50000）-->（11010110，10110001）

统一编码

为了方便记录，我们把经度和维度的二进制格子编码进行合并，按经度、纬度、经度、维度……这样的顺序，一位一位的进行放置：

（11010110，10110001）-->1110011100101001

奇数位的红色是经度编码，偶数位的黑色是纬度编码

我们可以用16进制、32进制、64进制这样的进制来缩短编码长度。这里业界推荐的是32进制

所以1110011100101001的32编码为：wwn(取三位有效)

精度

有了这样的编码，那到底要划分多少次，我们的数据才足够精确呢？维基百科上找到了这样的一张对应表：

当有一个32位数字的时候，精细度大概是2500公里，当有8个数字的时候，精细度大概是0.019km = 19米。也就是说，8个32位的数字 对应 8*5=40个二进制数，也就是经纬度分别划20次，就可以达到19米的精细度。

这个就是著名的 Geohash

值得注意的是：

1.Geohash比直接用经纬度的高效很多，而且使用者可以发布地址编码，既能表明自己位于某地方附近，又不至于暴露自己的精确坐标，有助于隐私保护。

2.GeoHash用一个字符串表示经度和纬度两个坐标。在数据库中可以实现在一列上应用索引（某些情况下无法在两列上同时应用索引）

3.GeoHash表示的并不是一个点，而是一个矩形区域

4.GeoHash编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。这个特性可以用于附近地点搜索

查找

通过上面的方法，我们就可以将所有商铺的经纬度给一个编码存进数据库，建立索引。这样根据当前自己的经纬度计算相应的编码，查询数据库

select * from merchant where code = 'xxx'

这样就可以获取附近的商铺了，是不是超级开心！

当然不要忘记，如果两个点距离很近，但是划到了两个格子里，这样是找不到的，所以我们还要把附近的8个格子的编码分别算出来一起查询，最后进行汇总！

本文参考：

http://en.wikipedia.org/wiki/Geohash

http://openlocation.org/geohash/geohash-js/

https://zhuanlan.zhihu.com/p/21856335