MySQL 根据经纬度查找排序

目的是,根据经纬度,实现查其找附近的人或地点,LBS 场景。
做基于地理位置的应用后台,没有使用 mongodb,看了网上的很多答案,其实也就是几份答案而已,天下文章一大抄。
这里综合网上的,结合自身,总结出了几种根据经纬度的排序算法,测试可用,性能也还可以。逐步递进优化,不同阶段,不同使用。

这里 x 为纬度,y 为经度。

PS:SQL 代码不完整,仅供阅读参考,理解意思就好。

一、MySQL 不使用空间函数,简单版

1. 粗算,根据场景得到一个 range,计算经纬度,得到的是一个矩形区域 (A),不精确,但是已经有范围这个雏形了,最容易实现的方式之一。

where latitude>y-range
and latitude<y+range
and longitude>x-range
and longitude <x+range
order by abs(longitude -x)+abs(latitude -y)
limit 10;

2. 使用 PHP 函数计算出距离,排序即可。

/**
 * @param $lat1 纬度
 * @param $lng1 经度
 * @param $lat2 纬度
 * @param $lng2 经度
 * @return float|int
 * 计算距离 (KM)
 */
function GetDistance($lat1, $lng1, $lat2, $lng2)
{
    $EARTH_RADIUS = 6378.137;
    $radLat1 = rad($lat1);
    $radLat2 = rad($lat2);
    $a = $radLat1 - $radLat2;
    $b = rad($lng1) - rad($lng2);
    $s = 2 * asin(sqrt(pow(sin($a / 2), 2) +
            cos($radLat1) * cos($radLat2) * pow(sin($b / 2), 2)));
    $s = $s * $EARTH_RADIUS;
    $s = round($s * 10000) / 10000;
    return $s;
}

/**
 * @param $d
 * @return float
 * 转换弧度
 */
function rad($d)
{
    return $d * pi() / 180.0;
}

排序的话,自己灵活实现。很多语言都有封装排序算法,效率也挺高的。


二、MySQL 不使用空间函数,优化版

这里的优化是对(一)中 range 的优化。根据范围半径,计算出经纬度的变化范围,得到一个比较准确的 range,这里的范围 (B) 是圆形的 (因为 $radius 是俩点间的距离)。

但是筛选时候的范围 (C) 是矩形,所以精确上来说,圆 B 是矩形 C 的内切圆,不在圆 B 但是在矩形 C 中的点也会出现在我们的 SQL 结果中。但是已经比 (一) 要好很多了。

$radius = 1;//半径范围,单位 km
$rangeLat = 180 / pi() * $radius / 6372.797;//纬度范围
$rangeLng = $rangeLat / cos($x * pi() / 180.0); //经度范围
$maxLat = $x + $range; //x1
$minLat = $x - $range; //x0
$maxLng = $y + $lngR; //y1
$minLng = $y - $lngR; //y0

我见过把这个计算带入到 SQL 中的,一大串 SQL,这种计算本来就不是 SQL 该有的,不推荐这样做。


三、MySQL 使用空间函数

在(二)中,我们得到了 4 个点。这个就是矩形范围,我们只要判断是否在这个矩形内就好了。其实用到 MySQL 的空间函数可以支持任意多边形。
还支持索引优化,MyISAM 能建立空间索引,MySQL 5.7 版本 InnoDB 也支持空间索引了。

优化程序将调查可用的空间索引是否能包含在使用某些函数的查询搜索中,如 WHERE 子句中的 MBRContains () 或 MBRWithin () 函数。
--19.6.2. 使用空间索引

这里的核心思想就是用一个范围判断某个点是否在这个范围内。
在数据库有一个类型为 geometry 的列 g。

select id,AsText(g) from geom
where MBRContains(GeomFromText('Polygon((x0 y0,x1 y0,x1 y1,x0 y1,x0 x0))'),g);

即可准确筛选出在这个范围内的点。即使后面跟 ORDER BY 限制距离性能也没有太大影响。

SELECT id, AsText(g), SQRT(POW( ABS( X(g) - X(x)), 2) + POW( ABS(Y(g) - Y(y)), 2 )) AS distance
FROM geom[*1]
WHERE MBRIntersects(g, GeomFromText('Polygon((x0 y0,x1 y0,x1 y1,x0 y1,x0 x0))'))[*2]
AND SQRT(POW( ABS( X(g) - X(x)), 2) + POW( ABS(Y(g) - Y(y)), 2 )) < radius[*3]
ORDER BY distance;[*4]

1: 从 geom 表中根据俩点间的距离公式计算结果,命名为 distance
2: 条件 1,g 列中的点和算出来的范围相交!相交!相交!注意我用的是 MBRIntersects (),不是 MBRContains ()
3: 条件 2,distance 小于给定的半径 radius
4: 根据 distance 排序

上面是根据官方文档写的示例代码,比较重要,如果你没看懂,没关系,我来举个栗子

这里选用 MBRContains () 来举例子,你可以自己实验下 MBRWithin () 函数,注意参数顺序就好了,我这里得到的结果是一样的。

函数用法:MBRContains (g1,g2)

函数说明:返回 1 或 0 以指明 g1 的最小边界矩形是否包含 g2 的最小边界矩形
函数已经说明了是 g1 是否包含 g2,所以不要弄反了;这里的矩形支持任意多变形

目标点:D (1,1)
也可以是范围哟,见注释 * 1

范围:E (0 0,0 3,3 3,3 0,0 0),闭合矩形,其实支持任意闭合多边形

SELECT id,name
from geom
where MBRContains(GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))'),
                  GeomFromText('Point(1 1)'));[*1]

1: 这里的目标点 D 也支持任意多边形,参数不再是 Point () 而是 Polygon ()

这条 SQL 可以解释为判断点 D 是否在范围内 E。

SELECT id,name,AsText(g)[*1]
from geom
where MBRContains(GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))'),
                  g);

1: 因为 g 列是 geometry 类型的,所以要用 AsText 转换下再展现出来

这条 SQL 可以解释为列出数据库中所有包含在范围 E 中的点。

更多相交、包含、接触等方法见上面开发文档《19.5.5. 关于几何最小边界矩形(MBR)的关系》


四、geohash

这个 GeoHash 是将二维的经纬度转换成字符串,字符串长度越长,精度就越精细。俩个字符串长度匹配的位数越多,就越接近,绝大部分情况看起来是这个样子的,但有例外。

类似于:(G->)|J…… 我 | K……|(<-H)

因为 GeoHash 是将区域划分为一个个规则矩形,所以在同一个矩形中,GeoHash 是一样的,但是会出现一个边际问题:G、H 俩个左右相邻的矩形,我在 G 的右边际处 (右边际和 H 相邻),餐厅 J 在 G 的左边际,餐厅 K 也在 H 的左边际,通过 GeoHash 得出来的结果是餐厅 J 离我更近,显然不合理。

可以通过加大矩形区域的精细程度和扩大相似范围解决。

根据匹配相应的位数,在 MySQL 加入索引,可以极大提高效率。GeoHash 和经纬度的转换,网上都有现成的代码,这里不再展示,PHP 还有对应的 C 拓展能提高计算速度。

* 在纬度相等的情况下:

* 经度每隔 0.00001 度,距离相差约 1 米;

* 每隔 0.0001 度,距离相差约 10 米;

* 每隔 0.001 度,距离相差约 100 米;

* 每隔 0.01 度,距离相差约 1000 米;

* 每隔 0.1 度,距离相差约 10000 米。

* 在经度相等的情况下:

* 纬度每隔 0.00001 度,距离相差约 1.1 米;

* 每隔 0.0001 度,距离相差约 11 米;

* 每隔 0.001 度,距离相差约 111 米;

* 每隔 0.01 度,距离相差约 1113 米;

* 每隔 0.1 度,距离相差约 11132 米。

Geohash,如果 geohash 的位数是 6 位数的时候,大概为附近 1 千米。


五、Redis GeoHash

官网在这里

Redis 也能玩定位?

sure!并且效率奇高!

虽然也是通过 GeoHash (高性能、高精度版) 来实现的,但是它封装了很多有用的方法,直接使用经纬度即可操作,能直接根据距离返回对应的点,支持直接返回 json,还支持排序输出。

毕竟是 Redis,持久化和容量都是要考虑的问题。

但是 Redis 从来不是孤军奋战的工具。

可以和 MySql 搭配,放在数据库前扛着,里面存储高频定位点,MySQL 也支持定位 (方案三),合理使用应该很好的 MySQL 定位解决方案了。

以上就是根据现有资料整理的 MySQL 经纬度经纬解决方案,如果有更好的方案,欢迎评论区讨论。

Happy Coding~

http://howto-use-mysql-spatial-ext.blogspot.com

http://www.cnblogs.com/dengxinglin/archive/2012/12/14/2817761.html#a