2012/06/07

社交網路設計:在地圖中找尋附近的人

很多社交網路App都會用到地圖,以自己為中心,找尋附近的店家、朋友等等。
用程式的邏輯來表達就是:
以 (x, y) 座標為中心,找尋方圓 n 公里以內的點

資料庫不外乎就是儲存經緯度 (longitude, latitude)
-----------------------------
 id | lat       | lng
----+-----------+------------
 1  | 25.151000 | 121.549000
 2  | 25.010000 | 121.574000
 3  | 25.070000 | 121.589000


今天我想找 User1 附近 10km 以內的人
方法一
來看"距離"跟"經緯度"的關係是什麼,從 Decimal degrees - Wikipedia 知道,其實他們並非線性的關係,而是一堆三角函數算出來的,因為隨著緯度越高,單位經緯度所對應的距離就越短。從 別搗蛋 歸納出的對應表:
台灣地區:
兩地經緯度相差 0.5度:距離相差約 50公里
兩地經緯度相差 0.1度:距離相差約 10公里
兩地經緯度相差 0.05度:距離相差約 5公里
兩地經緯度相差 0.01度:距離相差約 1公里


So 我們以 (25.151000, 121.549000) 為中心,分別加減 0.1度 算出東西經、南北緯對應的位置:
                           (25.251000, 121.549000)
                                      |
                                      |
(25.151000, 121.449000) -- (25.151000, 121.549000) -- (25.151000, 121.649000)
                                      |
                                      |
                           (25.051000, 121.549000)

轉換成範圍大概就是下面這樣子:
 121.449000  121.649000
    |           |
    |           |
----+-----------+---- 25.251000
    |           |
    |   user1   |
    |     o     |
    |           |
    |           |
----+-----------+---- 25.251000
    |           |
    |           |
於是SQL query就可以這麼下:
SELECT * FROM `user` WHERE 
  lat > 25.251000 AND lat < 25.251000 AND 
  lng > 121.449000 AND lng < 121.649000;
這個方法找到的範圍沒有那麼精準,而且找出來的範圍不是圓的是方的XD,不過通常我們的應用都不需要那麼準確啦。好處是 NoSQL 也可以用,因為我們只用到簡單的 SELECT、WHERE 而已。另外就是要注意跨換日線的例外處理。


方法二
如果是用 relational database,那 database server 提供的 function 就足夠幫我們把需要的座標挑出來啦!參考一下 google 寫的文件:

That's it! 只要一行 SQL query 搞定!
SELECT id, ( 6371 * acos( cos( radians(25.151000) ) * cos( radians( lat ) ) *
            cos( radians( lng ) - radians(121.549000) ) + 
            sin( radians(25.151000) ) * sin( radians( lat ) ) ) ) AS distance 
  FROM `user` HAVING distance < 10 ORDER BY distance LIMIT 0 , 20;

回傳距離 (25.151000, 121.549000) 10公里的前 20個位置,而且還帶有 distance 值!有了這些資訊,秀在地圖上就不成問題摟!


參考資料


沒有留言:

張貼留言