Terry.Li-彬

虚其心,可解天下之问;专其心,可治天下之学;静其心,可悟天下之理;恒其心,可成天下之业。

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  143 随笔 :: 344 文章 :: 130 评论 :: 0 Trackbacks
这年头和 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/
posted on 2010-12-16 22:37 礼物 阅读(1124) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。

网站导航: