首页 > Php, Sql-Mysql > PHP,Mysql-根据一个给定经纬度的点,进行附近地点查询–合理利用算法,效率提高2125倍

PHP,Mysql-根据一个给定经纬度的点,进行附近地点查询–合理利用算法,效率提高2125倍

目前的工作是需要对用户的一些数据进行分析,每个用户都有若干条记录,每条记录中有用户的一个位置,是用经度和纬度表示的。
还有一个给定的数据库,存储的是一些已知地点以及他们的经纬度,内有43W多条的数据。
现在需要拿用户的经纬度和已知地点进行距离匹配,如果它们之间的距离小于一定的数据,比如说500米,就认为用户是在这个地点。
MYSQL本身是支持空间索引的,但是在5.x的版本中,取消了对Distance()和Related()的支持,参考这里:MySQL 5.1参考手册 :: 19. 中的空间扩展 19.5.6. 测试几何类之间空间关系的函数,无法使用空间的距离函数去直接去查询距离在一定范围内的点。所以,我首先想到的是,对每条记录,去进行遍历,跟数据库中的每一个点进行距离计算,当距离小于500米时,认为匹配。这样做确实能够得到结果,但是效率极其低下,因为每条记录都要去循环匹配40W条数据,其消耗的时间可想而知。经过记录,发现每条记录处理的时间消耗达到1700ms,针对每天上亿的数据量,这样一个处理速度,让人情何以堪啊。。。
我自己也有个想法,就是找到每条记录所在点的经纬度周围的一个大概范围,比方说正方形的四个点,然后使用mysql的空间计算,使用MBR去得出点在这个矩形内的已知记录,然后进行匹配。可惜,自己没想出能计算到四个点经纬度的方法。
意外的,查询到了一个关于这个计算附近地点搜索初探,里面使用python实现了这个想法。
所以参考了一下原文中的算法,使用PHP进行了实现。
实现原理也是很相似的,先算出该点周围的矩形的四个点,然后使用经纬度去直接匹配数据库中的记录。

红色部分为要求的搜索范围,绿色部分我们能间接得到的结果范围

红色部分为要求的搜索范围,绿色部分我们能间接得到的结果范围

参考wiki百科上的一些球面计算公式:

假设已知点的经纬度分别为$lng, $lat
先实现经度范围的查询,
在haversin公式中令φ1 = φ2,可得:

用PHP进行计算,就是:

//$lat 已知点的纬度
$dlng =  2 * asin(sin($distance / (2 * EARTH_RADIUS)) / cos(deg2rad($lat)));
$dlng = rad2deg($dlng);//转换弧度

然后是纬度范围的查询,
在haversin公式中令 Δλ = 0,可得

在PHP中进行计算,就是:

$dlat = $distance/EARTH_RADIUS;//EARTH_RADIUS地球半径
$dlat = rad2deg($dlat);//转换弧度

最后,就可以得出四个点的坐标:
left-top : (lat + dlat, lng – dlng)
right-top : (lat + dlat, lng + dlng)
left-bottom : (lat – dlat, lng – dlng)
right-bottom: (lat – dlat, lng + dlng)

我把以上方法写成了一个函数,综合起来就是:

define(EARTH_RADIUS, 6371);//地球半径,平均半径为6371km
 /**
 *计算某个经纬度的周围某段距离的正方形的四个点
 *
 *@param lng float 经度
 *@param lat float 纬度
 *@param distance float 该点所在圆的半径,该圆与此正方形内切,默认值为0.5千米
 *@return array 正方形的四个点的经纬度坐标
 */
 function returnSquarePoint($lng, $lat,$distance = 0.5){

	$dlng =  2 * asin(sin($distance / (2 * EARTH_RADIUS)) / cos(deg2rad($lat)));
	$dlng = rad2deg($dlng);
	
	$dlat = $distance/EARTH_RADIUS;
	$dlat = rad2deg($dlat);
	
	return array(
				'left-top'=>array('lat'=>$lat + $dlat,'lng'=>$lng-$dlng),
				'right-top'=>array('lat'=>$lat + $dlat, 'lng'=>$lng + $dlng),
				'left-bottom'=>array('lat'=>$lat - $dlat, 'lng'=>$lng - $dlng),
				'right-bottom'=>array('lat'=>$lat - $dlat, 'lng'=>$lng + $dlng)
				);
 }
//使用此函数计算得到结果后,带入sql查询。
$squares = returnSquarePoint($lng, $lat);
$info_sql = "select id,locateinfo,lat,lng from `lbs_info` where lat<>0 and lat>{$squares['right-bottom']['lat']} and lat<{$squares['left-top']['lat']} and lng>{$squares['left-top']['lng']} and lng<{$squares['right-bottom']['lng']} ";	

在lat和lng上建立一个联合索引后,使用此项查询,每条记录的查询消耗平均为0.8毫秒,相比以前的1700ms,真的是天壤之别啊。效率真真的是以前的2125倍~~

总结:这应该也不是效率最好的办法,但是效率比以前确实有明显的提升。请记住,总有办法更好的。

  1. 6月 20th, 2012 @ 00:42 | #1

    最后的sql,后面的索引无法命中吧。where语句中只能允许一个范围查询

  2. 匿名 4月 7th, 2013 @ 15:39 | #2

    如何排序?

  3. 匿名 5月 27th, 2013 @ 13:30 | #3

    匿名 :
    如何排序?

  4. DigDeeply 5月 27th, 2013 @ 18:31 | #4

    @匿名
    需求是啥? 为什么要排序?怎么个排序的需求?

  5. 心情天空 6月 20th, 2013 @ 17:56 | #5

    正如“夜”所说,最后的Sql语句查不到数据的。

  6. 楼主好淫 8月 7th, 2013 @ 15:31 | #6

    楼主好淫 发我邮箱liaozu@qq.com

  7. 4ngel 10月 29th, 2013 @ 18:14 | #7

    @DigDeeply
    也许他是说按照距离远近排序。。

  8. 匿名 11月 20th, 2013 @ 16:39 | #8

    当经纬度是负数时,有问题吧

  9. 匿名 4月 4th, 2014 @ 16:36 | #9

    仅仅是第一步。 如何获取更多附近的数据呢?

  10. 素馅包子 7月 17th, 2014 @ 17:43 | #10

    为什么不用mysql的空间搜索,你的范围搜索的索引只能用到一个,

    给你一个关键词
    mbrcontains

    • DigDeeply 7月 22nd, 2014 @ 09:58 | #11

      当时使用的mysql版本还不支持空间索引。。

  11. baayso 9月 9th, 2014 @ 00:39 | #12

    我已经用到自己的项目里了,项目是Java写的,目前测试都通过,还没进行严格测试。非常感谢,哈哈!

  12. yison 10月 22nd, 2014 @ 22:44 | #13

    楼主方法不错,一直是借鉴的这个方法,现在需要按远近距离排序了就有点惆怅了,不知道改怎么排序

  13. 匿名 11月 25th, 2014 @ 15:35 | #14

    yison :
    楼主方法不错,一直是借鉴的这个方法,现在需要按远近距离排序了就有点惆怅了,不知道改怎么排序

    话说层主解决这个问题了吗

  14. 小贾jf 2月 5th, 2015 @ 17:50 | #15

    楼主的这个方法查询的是一个圆圈内的点还是正方形内的点啊?

  15. DigDeeply 2月 7th, 2015 @ 18:47 | #16

    @小贾jf
    正方形内的。

  16. 匿名 2月 9th, 2015 @ 18:14 | #17

    获取的是正方形内的点啊,有的不符合要求 加距离限制的话比如 500米,1000米,2000米

    • DigDeeply 2月 26th, 2015 @ 21:53 | #18

      然后你可以再把结果筛选一遍,对符合之前条件的结果计算距离,不符合条件的点再干掉。

评论提交中, 请稍候...

留言

可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 2 )
  1. 8月 6th, 2013 @ 18:15 | #1
    Pingback: GPS定位,经纬度附近地点查询–C#实现方法 – 小小新新 | 查问题
  2. 6月 16th, 2014 @ 09:57 | #2
    Pingback: 百度地图根据经纬度计算500米内商家 | Eric's blog