Here comes the Sun

今天偶然看到一个Ruby的GeoHash库，功能非常简单，就是将经纬度坐标哈希成字符串，并且，利用这个字符串可以粗略地比较两点的距离。这个库的代码host在GitHub上，要安装，需要将github加入gem：
sudo gem sources -a http://gems.github.com
sudo gem install davotroy-geohash

用法，irb：
irb(main):001:0> require ‘rubygems’
=> true
irb(main):002:0> require ‘geohash’
=> true
irb(main):003:0> GeoHash.encode(32.168, 118.54)
=> “wtsr12n0nj”
irb(main):004:0> GeoHash.decode(‘wtsr12n0nj’)
=> [32.168, 118.54]

代码可以从github上获得
git clone git://github.com/davetroy/geohash.git

GeoHash的核心部分用C实现，仔细看一下可以发现是一个四叉树的结构：

[codesyntax lang="c"]
#define BASE32	"0123456789bcdefghjkmnpqrstuvwxyz"
static void encode_geohash(double latitude, double longitude, int precision, char *geohash) {
	int is_even=1, i=0;
	double lat[2], lon[2], mid;
	char bits[] = {16,8,4,2,1};
	int bit=0, ch=0;

	lat[0] = -90.0;  lat[1] = 90.0;
	lon[0] = -180.0; lon[1] = 180.0;

	while (i < precision) {
		if (is_even) {
 			mid = (lon[0] + lon[1]) / 2;
 			if (longitude > mid) {
				ch |= bits[bit];
				lon[0] = mid;
			} else
				lon[1] = mid;
		} else {
			mid = (lat[0] + lat[1]) / 2;
			if (latitude > mid) {
				ch |= bits[bit];
				lat[0] = mid;
			} else
				lat[1] = mid;
		}

		is_even = !is_even;
		if (bit < 4)
			bit++;
		else {
			geohash[i++] = BASE32[ch];
			bit = 0;
			ch = 0;
		}
	}
	geohash[i] = 0;
}

[/codesyntax]

可惜在学校的时候没有看到这么精致的代码。

One Response to “GeoHash”