geocoding基于地理编码和逆地理编码的算法问题(转载)

今天看了下geocoding内容，找了几篇问题：

http://hi.baidu.com/moonstream/blog/item/168bab8b71d6a9759e2fb4f2.html

 

如果你在一家从事GIS开发的软件公司呆上一阵子，一定经常听到人们提起"地理编码"这个词。那么，什么是地理编码呢？

我们先来看一看维基百科中是怎么解释的：

Geocoding is the process of assigning geographic coordinates (e.g.

latitude-longitude) to street addresses, as well as other points and

features. With geographic coordinates, the features can then be mapped and

entered into Geographic Information Systems.

——From Wikipedia, the free encyclopedia.

地理编码是将地理坐标（例如经纬度）赋予街道地址还有其他点位和地理特征的过程。有了地理坐标，地理特征就可以被显示到地图上或运用到地理信息系统中。

相反的，由一个地理坐标得到相应的地址表述的过程，就称作"逆地理编码（Reverse Geocoding）"。

地理编码和逆地理编码都是很常用的功能。例如，你想去海龙大厦，于是进入某个本地搜索网站，输入关键字"海龙大厦"，然后你就得到了一张标有"海龙大厦"

的地图。在这个过程中，地理编码的步骤被隐含着，因为对于一般用户来说，得到经纬度的数值是没有用处的，只要得到包含目标的地图就可以了。对于后台服务，

则经历了两个步骤：第一步，通过地理编码查询得到海龙大厦的地理坐标；第二步，取得一幅这个坐标附近的地图，把"海龙大厦"标在这个地图上显示给用户。又

例如，你从GPS设备得到了你当前的经纬度，可是你并不知道自己身在何处，这个时候你可以通过逆地理编码服务得到你当前所在的地区名和街道名，并且了解到

你附近有什么标志性建筑（地标），你还可以把这个地址描述发给你的朋友从而让他方便地找到你。

那么，地理编码功能又是如何实现的呢？首先，当然要有一个地址库了。也就是一个包含着地理坐标信息的地址列表。有了这个地址库，我们就可以迅速的查询到某

个地址的地理坐标。但是，任何一个小城市也都会存在着数不胜数的地址，想要采集出全部的地址及其坐标几乎是不可能的。于是，在美国以及许多国家，人们通过

一种叫做"地址插值"的方法来计算某个地址的坐标。假设我们知道中关村大街1号的坐标和中关村大街50号的坐标，就可以近似的认为中关村大街2号至49号

这些地址平均分布在整个中关村大街上，于是我们就可以用数学公式近似计算出中关村大街2号至49号全部地址的坐标。这种方法当然会存在一定误差。美国大部

分城市地址的规则度较高，所以地址插值法在美国的实用性还比较好，但是对于中国现在地址分布较乱的国情，这种编码过程就不太适用了。因此，我们不得不尽可

能多地来收集地址信息。而这样浩大的工程，通常都会由政府部门来投资。另外，国内有测绘资质的商业公司也都在采集数据。

逆地理编码的过程通常这样：根据指定的地理坐标，从空间数据库中分别查询出该坐标所在的城市名称、区域名称、街道名称以及附近的地标，然后把这些信息组合成一个­完整的地址描述。例如：北京市海淀区中关村大街1号海龙大厦附近。

Google Maps

API是现在热门的免费地图接口，但是它并不包含地理编码服务，因此Google的官方文档中建议用户使用一些其它的开放地理编码服务。而互联网上能够找

到的地理编码服务几乎都是美国和加拿大的数据。在中国能够提供免费数据的只有灵图一家（http://freemosp.51ditu.com），

在灵图的开放接口中，包含了38个城市的地理编码及逆地理编码服务。美中不足的是，灵图的地理编码服务目前只能通过名称来查找位置，而不能通过地址来进行

查找。例如，你用"海龙大厦"作为关键字可以查找到"中关村大街1号"及其经纬度，但是用"中关村大街1号"作为关键字却不能匹配到"海龙大厦"。

位置服务其实是一把双刃剑，人们享受着位置服务带来的便利，同时又担心自己的隐私受到侵犯。而国家更不希望位置信息落入敌国或恐怖组织的手中。因此灵图公

布出来的地理坐标都是经过了偏移的，这是一个折衷的办法，使得我们能够在法律许可的范围内得到地址和经纬度数据。

地理编码和位置搜索经常被人们混淆，其实它们之间并没有很明显的界线。通常，位置搜索的方式更加灵活，为了更加准确地搜索出我们关心的位置，我们可以加入

区域和类别等限制条件，但是如果我们的目的依然是获取某个地方的"地理坐标"，那么我们实际上就是在进行"地理编码"。

（摘自“http://www.cnblogs.com/kaixin110/archive/2007/09/25/905175.html”）

 

http://blog.csdn.net/historyasamirror/archive/2010/06/01/5638248.aspx

 

这年头和 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 。

到此，我们还没有回答之前提的问题，如果有很多点，该怎样从其中找出附近的点呢？答案貌似已经呼之欲出，俺就不多说了。