几种简单方案实现LBS

方案一： Mysql

通过球面两点距离公式

$ AB = R * \arccos{( \cos{wA} * \cos{wB} * \cos{jB-jA} + \sin{wA}*\sin{wB})}$
其中 A（jA,wA）和B（jB，wB）,推导过程见这里

示意图

对于大部分已经使用MySQL的应用来说，使用这种方案没有任何迁移和部署成本，但使用SQL语句进行查询的缺点也显而易见，每条SQL的计算量都会非常大，性能将会是严重的问题。

# 创建表
CREATE TABLE address (
	id INT (11) AUTO_INCREMENT,
	name CHAR (80) NOT NULL,
	lat CHAR (10),
	lng CHAR (10),
	PRIMARY KEY (id)
);

# 插入测试数据
INSERT INTO address(name,lat,lng) VALUES
 ('成都', 30.659673,104.068433)
,('绵阳', 31.473909,104.680961)
,('泸州', 28.876403,105.450251) 
,('德阳', 31.134847,104.408441);

# 查询
SELECT
    id,name, (
      6371 * acos (    # 3959是地球半径的英里，6371是地球半径的千米
      cos ( radians(30.452034) )
      * cos( radians( lat ) )
      * cos( radians( lng ) - radians(106.644153) )
      + sin ( radians(30.452034) )
      * sin( radians( lat ) )
    )
) AS distance
FROM address
ORDER BY distance
LIMIT 0 , 20;

# 或通过 st_distance_sphere 函数计算
SELECT 
  name,
	round( st_distance_sphere ( point ( 106.644153, 30.452034 ), point ( lng, lat ))/ 1000, 2 ) AS distance 
FROM address 
ORDER BY distance ASC 

/**
 * 查询结果

 3	泸州	209.7647687926011
 2	绵阳	218.97099731812352
 4	德阳	226.64161541779157
 1	成都	247.70751793832144

 */

通过空间存储(spatial)

MySQL的空间扩展（MySQL Spatial Extensions），它允许在MySQL中直接处理、保存和分析地理位置相关的信息，但是需要手动排序（请忽略distance字段）。文档可见这里

# 创建表
CREATE TABLE address (
	id INT (11) AUTO_INCREMENT,
	name CHAR (80) NOT NULL,
	point POINT NOT NULL,
	PRIMARY KEY (id)
);
# 创建索引
ALTER TABLE address ADD SPATIAL INDEX(point);

# 插入测试数据
INSERT INTO address(name,point,lat,lng) VALUES
 ('成都', GeomFromText('POINT(30.659673 104.068433)'))
,('绵阳', GeomFromText('POINT(31.473909 104.680961)'))
,('泸州', GeomFromText('POINT(28.876403 105.450251)')) 
,('德阳', GeomFromText('POINT(31.134847 104.408441)'));

# 查询： 查找坐标(30.452034,106.644153)附近 220 公里内的城市
SELECT  id,name,(
          6371 * acos (    # 3959是地球半径的英里，6371是地球半径的千米
          cos ( radians(30.452034) )
          * cos( radians( lat ) )
          * cos( radians( lng ) - radians(106.644153) )
          + sin ( radians(30.452034) )
          * sin( radians( lat ) )
        )
    ) AS distance # 仅供结果可视，非必须
    FROM    address
    WHERE   MBRContains (
                LineString(
                        Point (
                                30.452034 + 220 / ( 111.1 / COS(RADIANS(30.452034))), // 1弧度 = 111.1
                                106.644153 + 220 / 111.1
                          ),
                        Point (
                                30.452034 - 220 / ( 111.1 / COS(RADIANS(30.452034))),
                                106.644153 - 220 / 111.1
                        ) 
                ), point)

/**
 * 查询结果

 2	绵阳	218.97099731812352
 3	泸州	209.7647687926011
 
 */

通过Geohash算法

GeoHash是一种地址编码，通过切分地图区域为小方块（切分次数越多，精度越高），它能把二维的经纬度编码成一维的字符串。也就是说，理论上geohash字符串表示的并不是一个点，而是一个矩形区域，只要矩形区域足够小，达到所需精度即可。（MongoDB的索引也是基于geohash）

如：wm3yr31d252414ux就是目前我所在的位置，降低一些精度，就会是wm3yr31d2524，再降低一些精度，就会是wm3yr。

所以这样一来，我们就可以在MySQL中用LIKE ‘wm3yr%’来限定区域范围查询目标点，并且可以对结果集做缓存。更不会因为微小的经纬度变化而无法用上数据库的Query Cache。

这种方案的优点显而易见，仅用一个字符串保存经纬度信息，并且精度由字符串从头到尾的长度决定，可以方便索引。

但这种方案的缺点是：从geohash的编码算法中可以看出，靠近每个方块边界两侧的点虽然十分接近，但所属的编码会完全不同。实际应用中，虽然可以通过去搜索环绕当前方块周围的8个方块来解决该问题，但一下子将原来只需要1次SQL查询变成了需要查询9次，这样不仅增大了查询量，也将原本简单的方案复杂化了。除此之外，这个方案也无法直接得到距离，需要程序协助进行后续的排序计算。

geohash的编码算法

成都永丰立交经纬度(30.63578,104.031601)

1)、纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)，如果目标纬度位于前一个区间，则编码为0，否则编码为1。

由于30.625265属于(0, 90)，所以取编码为1。

然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0

然后再将(0, 45)分成 (0, 22.5), (22.5, 45)两个区间，而39.92324位于(22.5, 45)，所以编码为1

依次类推可得永丰立交纬度编码为101010111001001000100101101010。

2)、经度也用同样的算法，对(-180, 180)依次细分，(-180，0)、(0,180) 得出编码110010011111101001100000000000

3)、合并经纬度编码，从高到低，先取一位经度，再取一位纬度；得出结果 111001001100011111101011100011000010110000010001010001000100

4)、用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(30.63578,104.031601)的编码为wm3yr31d2524。

11100 10011 00011 11110 10111 00011 00001 01100 00010 00101 00010 00100 => wm3yr31d2524

算法如下：

<?php
class GeoHash
{
    /**
     * Base32编码映射关系
     */
    const DIGITS = ['0', '1', '2', '3', '4', '5', '6', '7', '8',
        '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
        'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];

    /**
     * 精确度，值越大越精准, 建议此处使用5的倍数
     */
    const MAX = 40;

    /**
     * GeoHash encode
     * @param $lat
     * @param $lng
     * @return string
     */
    public static function encode($lat, $lng)
    {
        return self::base32_encode(self::combine(self::dec2bit($lat, -90, 90), self::dec2bit($lng, -180, 180)));
    }

    /**
     * GeoHash decode
     * @param $val
     * @return array
     */
    public static function decode($val)
    {
        $encode = self::base32_decode($val);
        list($elat, $elng) = self::spilt($encode);
        return [self::bit2dec($elat, -90, 90), self::bit2dec($elng, -180, 180)];
    }

    /**
     * 将十进制转换成二进制经纬度
     * @param float $v 十进制经纬度
     * @param float $l 左阈值
     * @param float $r 右阈值
     * @return string
     */
    private static function dec2bit($v, $l, $r)
    {
        $s = '';
        $max = self::MAX;
        while ($max--) {
            $mid = ($l + $r) / 2;
            $d = $mid > $v ? 0 : 1;
            if ($d) {
                $l = $mid;
            } else {
                $r = $mid;
            }
            $s .= $d;
        }
        return $s;
    }

    /**
     * 经纬度编码值合并
     * @param int $elat 二进制维度
     * @param int $elng 二进制经度
     * @return string
     */
    private static function combine($elat, $elng)
    {
        $c = '';
        $max = self::MAX;
        for ($i = 0; $i < $max; $i++) {
            $c .= $elng[$i] . $elat[$i];
        }
        return $c;
    }


    /**
     * base32编码
     * @param string $s 合并后的经纬度
     * @return string
     */
    private static function base32_encode($s)
    {
        $r = '';
        for ($i = 0; $i < strlen($s); $i += 5) {
            $sub = str_pad(substr($s, $i, 5), 5, 0, STR_PAD_RIGHT);
            $num = base_convert($sub,2,10);
            $r .= self::DIGITS[$num];
        }
        return $r;
    }

    /**
     * base32解码
     * @param string $s GeoHash.encode的值
     * @return string
     */
    private static function base32_decode($s)
    {
        $r = '';
        for ($i = 0; $i < strlen($s); $i++) {
            $v = array_search($s[$i], self::DIGITS);
            $b = str_pad(base_convert($v, 10, 2), 5, 0, STR_PAD_LEFT);
            $r .= $b;
        }
        return $r;
    }

    /**
     * 经纬度拆分
     * @param string $s 将合并的经纬度拆出来
     * @return array
     */
    private static function spilt($s)
    {
        $lat = '';
        $lng = '';
        for ($i = 0; $i < strlen($s); $i += 2) {
            $lng .= $s[$i];
            $lat .= $s[$i + 1];
        }
        return [$lat, $lng];
    }

    /**
     * 二进制转换成十进制经纬度
     * @param float $s 二进制经纬度
     * @param float $l 左阈值
     * @param float $r 右阈值
     * @return float|int|string
     */
    private static function bit2dec($s, $l, $r)
    {
        $k = '';
        $mid = ($l + $r) / 2;
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i]) {
                $l = $mid;
            } else {
                $r = $mid;
            }
            $mid = ($l + $r) / 2;
            $k = $mid;
        }
        return $k;
    }
}

/**
 * Testing
 */
$lat = 30.63578;
$lng = 104.031601;
var_dump("初始值: $lat,$lng");
var_dump("编码后: " . ($s = GeoHash::encode($lat, $lng)));
var_dump("解码后: " . (implode(',', GeoHash::decode($s))));


/**
 * 输出
string(30) "初始值: 30.63578,104.031601"
string(27) "编码后: wm3yr31d252414ux"
string(41) "解码后: 30.63577999993,104.03160100012"
*/

方案二： MongoDB

MongoDB原生支持地理位置索引，可以直接用于位置距离计算和查询。

另外，它也是如今最流行的NoSQL数据库之一，除了能够很好地支持地理位置计算之外，还拥有诸如面向集合存储、模式自由、高性能、支持复杂查询、支持完全索引等等特性。查询结果默认将会由近到远排序，而且查询结果也包含目标点对象、距离目标点的距离等信息。由于geoNear是MongoDB原生支持的查询函数，所以性能上也做到了高度的优化，完全可以应付生产环境的压力。

# 插入数据
db.location.insert({
      "xian":"成都",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[104.068433,30.659673]}
});
db.location.insert({
      "xian":"绵阳",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[104.680961,31.473909]}
});
db.location.insert({
      "xian":"泸州",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[105.450251,28.876403]}
});
db.location.insert({
      "xian":"德阳",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[104.408441,31.134847]}
});
 
# 创建 2dsphere索引
db.location.createIndex({"center":"2dsphere"}); # 或 db.location.ensureIndex( { center : "2dsphere" } )

# 查询: 这种方法可以返回的由近及远的点，但是不能获取距离，支持分页查询
db.location.find({
  center:{
     $near:{
       $geometry:{
          type:"Point",
          coordinates:[106.644153,30.452034]
       },
       $maxDistance: 500000 
     }
  }
}).limit(3);
/** 查询结果
{ "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d3"), "xian" : "泸州", "sheng" : "四川", "center" : { "type" : "Point", "coordinates" : [ 105.450251, 28.876403 ] } }
{ "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d2"), "xian" : "绵阳", "sheng" : "四川", "center" : { "type" : "Point", "coordinates" : [ 104.680961, 31.473909 ] } }
{ "_id" : ObjectId("5f1e4e991a9a5bb3e50e17d4"), "xian" : "德阳", "sheng" : "四川", "center" : { "type" : "Point", "coordinates" : [ 104.408441, 31.134847 ] } }
**/

#查询：这种方法更加灵活，可以返回距离，还可以指定查询条件等,但是不可以分页

db.runCommand( {
   geoNear: "location" ,
   near: { 
      type: "Point" , 
      coordinates: [106.644153,30.452034]
    } ,
   spherical: true,
   limit:3
});

/** 查询结果
{
        "results" : [
                {
                        "dis" : 209998.53583992278,// 距离查询点距离，单位：米
                        "obj" : {
                                "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d3"),
                                "xian" : "泸州",
                                "sheng" : "四川",
                                "center" : {
                                        "type" : "Point",
                                        "coordinates" : [
                                                105.450251,
                                                28.876403
                                        ]
                                }
                        }
                },
                {
                        "dis" : 219215.02401424237,
                        "obj" : {
                                "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d2"),
                                "xian" : "绵阳",
                                "sheng" : "四川",
                                "center" : {
                                        "type" : "Point",
                                        "coordinates" : [
                                                104.680961,
                                                31.473909
                                        ]
                                }
                        }
                },
                {
                        "dis" : 226894.19044046788,
                        "obj" : {
                                "_id" : ObjectId("5f1e4e991a9a5bb3e50e17d4"),
                                "xian" : "德阳",
                                "sheng" : "四川",
                                "center" : {
                                        "type" : "Point",
                                        "coordinates" : [
                                                104.408441,
                                                31.134847
                                        ]
                                }
                        }
                }
        ],
        "stats" : {
                "nscanned" : 5,
                "objectsLoaded" : 4,
                "avgDistance" : 218702.58343154436,
                "maxDistance" : 226894.19044046788,
                "time" : 0
        },
        "ok" : 1
}**/

方案三： Redis

自 Redis 3.2版开始，Redis基于geohash和有序集合提供了地理位置相关功能。

Redis Geo模块的6个指令用途说明：

https://www.redis.net.cn/

http://redisdoc.com/script/eval.html

1）GEOADD：将给定的位置对象（纬度、经度、名字）添加到指定的key；

2）GEOPOS：从key里面返回所有给定位置对象的位置（经度和纬度）；

3）GEODIST：返回两个给定位置之间的距离；

4）GEOHASH：返回一个或多个位置对象的Geohash表示；

5）GEORADIUS：以给定的经纬度为中心，返回目标集合中与中心的距离不超过给定最大距离的所有位置对象；

6）GEORADIUSBYMEMBER：以给定的位置对象为中心，返回与其距离不超过给定最大距离的所有位置对象。

# 插入数据
GEOADD city 104.068433 30.659673 成都
GEOADD city 104.680961 31.473909 绵阳
GEOADD city 105.450251 28.876403 泸州
GEOADD city 104.408441 31.134847 德阳

# 查询 300公里内的城市 
GEORADIUS city 106.644153 30.452034 300 km withdist asc
1) 1) "泸州"
   2) "209.8239"
2) 1) "绵阳"
   2) "219.0328"
3) 1) "德阳"
   2) "226.7054"
4) 1) "成都"
   2) "247.7777"

注意：


通过Redis源码分析可以看出，Redis内部使用有序集合(zset)保存位置对象，有序集合中每个元素都是一个带位置的对象，元素的score值为其经纬度对应的52位的geohash值：
1) double类型精度为52位；
2) geohash是以base32的方式编码，52bits最高可存储10位geohash值，对应地理区域大小为0.6*0.6米的格子。换句话说经Redis geo转换过的位置理论上会有约0.3*1.414=0.424米的误差。
3) 用 GEORADIUS 实现【查找附近的人】功能，时间复杂度为：O(N+log(M))。其中N为九宫格范围内的位置元素数量（要算距离）, M是指定层级格子的数量,log(M)是跳表结构中找到每个格子首元素的时间复杂度（这个过程一般会进行9次）

附录：两点距离算法

/**
  * 获取两点间的距离
  * @param float $latitude1 纬度1
  * @param float $longitude1 经度1
  * @param float $latitude2 纬度2
  * @param float $longitude2 经度2
  * @param string $unit 单位: Km/Mi
  * @return false|float
  */
 function getDistanceBetweenPointsNew($latitude1, $longitude1, $latitude2, $longitude2, $unit = 'Mi')
 {
     $theta = $longitude1 - $longitude2;
     $distance = (sin(deg2rad($latitude1)) * sin(deg2rad($latitude2))) + (cos(deg2rad($latitude1)) * cos(deg2rad($latitude2)) * cos(deg2rad($theta)));
     $distance = acos($distance);
     $distance = rad2deg($distance);
     $distance = $distance * 60 * 1.1515;
     switch (strtolower($unit)) {
         case 'mi':
             break;
         case 'km' :
             $distance = $distance * 1.609344;
     }
     return (round($distance, 2));
 }