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