PHP,Mysql-根據(jù)一個給定經(jīng)緯度的點，進行附近地點查詢–合理利用算法，效率提高2125倍2012年6月15日
DigDeeply目前的工作是需要對用戶的一些數(shù)據(jù)進行分析，每個用戶都有若干條記錄，每條記錄中有用戶的一個位置，是用經(jīng)度和緯度表示的。
還有一個給定的數(shù)據(jù)庫，存儲的是一些已知地點以及他們的經(jīng)緯度，內(nèi)有43W多條的數(shù)據(jù)。
現(xiàn)在需要拿用戶的經(jīng)緯度和已知地點進行距離匹配，如果它們之間的距離小于一定的數(shù)據(jù)，比如說500米，就認為用戶是在這個地點。
MYSQL本身是支持空間索引的，但是在5.x的版本中，取消了對Distance()和Related()的支持，參考這里：
MySQL 5.1參考手冊 :: 19. 中的空間擴展 19.5.6. 測試幾何類之間空間關(guān)系的函數(shù)，無法使用空間的距離函數(shù)去直接去查詢距離在一定范圍內(nèi)的點。所以，我首先想到的是，對每條記錄，去進行遍歷，跟數(shù)據(jù)庫中的每一個點進行距離計算，當距離小于500米時，認為匹配。這樣做確實能夠得到結(jié)果，但是效率極其低下，因為每條記錄都要去循環(huán)匹配40W條數(shù)據(jù)，其消耗的時間可想而知。經(jīng)過記錄，發(fā)現(xiàn)每條記錄處理的時間消耗達到1700ms，針對每天上億的數(shù)據(jù)量，這樣一個處理速度，讓人情何以堪啊。。。
我自己也有個想法，就是找到每條記錄所在點的經(jīng)緯度周圍的一個大概范圍，比方說正方形的四個點，然后使用mysql的空間計算，使用MBR去得出點在這個矩形內(nèi)的已知記錄，然后進行匹配?？上В约簺]想出能計算到四個點經(jīng)緯度的方法。
意外的，查詢到了一個關(guān)于這個計算
附近地點搜索初探，里面使用python實現(xiàn)了這個想法。
所以參考了一下原文中的算法，使用PHP進行了實現(xiàn)。
實現(xiàn)原理也是很相似的，先算出該點周圍的矩形的四個點，然后使用經(jīng)緯度去直接匹配數(shù)據(jù)庫中的記錄。
紅色部分為要求的搜索范圍，綠色部分我們能間接得到的結(jié)果范圍
參考wiki百科上的一些球面計算公式：
Great-circle distanceH
aversine formula假設(shè)已知點的經(jīng)緯度分別為$lng, $lat
先實現(xiàn)經(jīng)度范圍的查詢，
在haversin公式中令φ1 = φ2，可得:
用PHP進行計算，就是：
Example1
2
3
//$lat 已知點的緯度
$dlng = 2 * asin(sin($distance / (2 * EARTH_RADIUS)) / cos(deg2rad($lat)));
$dlng = rad2deg($dlng);//轉(zhuǎn)換弧度
然后是緯度范圍的查詢，
在haversin公式中令 Δλ = 0，可得
在PHP中進行計算，就是：
Example1
2
$dlat = $distance/EARTH_RADIUS;//EARTH_RADIUS地球半徑
$dlat = rad2deg($dlat);//轉(zhuǎn)換弧度
最后，就可以得出四個點的坐標：
left-top : (lat + dlat, lng – dlng)
right-top : (lat + dlat, lng + dlng)
left-bottom : (lat – dlat, lng – dlng)
right-bottom: (lat – dlat, lng + dlng)
我把以上方法寫成了一個函數(shù)，綜合起來就是：
Example1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
define(EARTH_RADIUS, 6371);//地球半徑，平均半徑為6371km
/**
*計算某個經(jīng)緯度的周圍某段距離的正方形的四個點
*
*@param lng float 經(jīng)度
*@param lat float 緯度
*@param distance float 該點所在圓的半徑，該圓與此正方形內(nèi)切，默認值為0.5千米
*@return array 正方形的四個點的經(jīng)緯度坐標
*/
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)
);
}
//使用此函數(shù)計算得到結(jié)果后，帶入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上建立一個聯(lián)合索引后，使用此項查詢，每條記錄的查詢消耗平均為0.8毫秒，相比以前的1700ms，真的是天壤之別啊。效率真真的是以前的2125倍~~
總結(jié)：這應(yīng)該也不是效率最好的辦法，但是效率比以前確實有明顯的提升。請記住，總有辦法更好的。
