這年頭和 location 相關的應用越來越火。從 foursquare 的熱鬧程度就可見一般（什么，沒聽過 foursquare…. 哥們，你 out 了）。和 location 有關的應用一般都包括一些共同的操作，最常見的一個，就是找附近的東東（餐館，商店 …. ）。
所以，這里就拋出了一個問題，怎樣才能知道兩個物體離得近呢？
我之前轉過一篇 blog ，是關于 用 cellid進行定位的 ，當然，這種方法是在不得已的情況下才使用，比如得不到 gps 。這里，我們假設可以拿到兩個物體的 gps 數據，所以一個最直觀的辦法，計算兩個 gps 點的直線距離。當然，這個計算不精確，不要忘了，地球是圓的，所以兩個 gps 點之間的距離應該是一個弧線。上網搜一下，應該能找到一個復雜的公式，專門用來計算這個弧長。
對于兩個點來說，上述的方法就夠用了。當如果有很多個點呢，難道要我計算兩兩之間的距離么？
這個問題屬于 spatial data indexing&management 的范疇，有很多關于 database 或者 GIS 的書都會講到一些解決的算法和特殊的數據結構。我在這只介紹一個簡單的方法，叫做 geohash 。
geohash 其實是對 gps 數據進行了編碼，使得上述問題更容易得到解決。（關于 geohash 的詳細論述可以看 wiki ，介紹得很全面）
假設我們有一個 gps 數據，為 <42.6, -5.6> ，首先 (1) 我們會將經緯度分別編碼成一個 binarycode ，比如緯度 42.6 被編碼成“ 101111001001 ”，經度 -5.6 被翻譯成“ 0111110000000 ”，然后 (2) 將兩個 binarycode 連起來，經度的 binarycode 作為奇數位，緯度的 binarycode 作為偶數位，就變成了“ 01101 11111 11000 00100 00010 ”，最后，將這個 binarycode 轉化為一個 32 進制的字符串，變成“ ezs42 ”。
需要說一下經緯度轉化成 binarycode 的算法。舉例來說，比如緯度的范圍是 +90 ~ -90 ，我們將這個分為兩個區間，分別是 (-90, 0) 和 (0,90) ，如果 gps 的 x( 緯度 ) 落在了第一個區間，那么它的第一位 binarycode 就是 0 ，如果落在第二個區間，那么它的第一位 binarycode 就是 1 ，顯然 42.6 是在第二個區間，所以它的第一位 binarycode 是 1 ，然后再對 (0,90) 這個區間做二分，再計算下一步的 binarycode….
編碼方式說完了，說說 geohash 的好處。當兩個 gps 數據對應的 geohash 數據有一定長度的前綴是相同的，表示這兩個數據在一定程度上距離接近，相同的前綴越長，那么兩個點越離得近。（ nearby places will often (but not always) present similar prefixes. ）
注意，需要提及的是，兩個 geohash 有相同前綴，表示這兩個點離得近，但是！兩個點離得近，不一定 geohash 有相同的前綴。 geohash 在這里存在一個缺陷，就是所謂的 edge case 。詳情見 wiki 。
再往深入琢磨一下， geohash 的本質是什么。其實它就是對一個二維平面進行了一個索引，首先對這個平面豎著切一刀，刀的左邊標記為 0 ，刀的右邊標記為 1 ，然后再橫著切一刀，并且繼續標記，然后再豎著切 …. 有很多 spatial data indexing 的方法都是這樣的思路，它的作用就是把平面的這種二維數據改造成一維的數據。而一維數據有個好處，就是可以做 sorting 。
到此，我們還沒有回答之前提的問題，如果有很多點，該怎樣從其中找出附近的點呢？答案貌似已經呼之欲出，俺就不多說了。
Reference ：
http://en.wikipedia.org/wiki/Geohash
http://geohash.org/