Geohash——地理坐标索引

今天看july的博客：第三十六~三十七章、搜索智能提示suggestion，附近地点搜索

（http://blog.csdn.net/v_july_v/article/details/11288807）

里面提到了geohash算法对地理坐标的索引，但是引用的文章和例子让我产生了疑问，对于坐标的经纬度不应该是直接让纬度跟随在经度之后形成一个索引值的，这样只能保证经度相同的且靠近的点排列的比较近，而纬度相同经度只差1的点确不能排列的比较近。

于是查阅了geohash的维基百科说明：http://en.wikipedia.org/wiki/Geohash#Decode_from_base_32

文中举了个例子：

This operation results in the bits 01101 11111 11000 00100 00010. Assuming that counting starts at 0 in the left side, the even bits are taken for the longitude code (0111110000000), while the odd bits are taken for the latitude code (101111001001).

原来是经度和纬度相互交错形成的geohash值。这样就能比较好的让靠近的点按照geohash值也能排列的靠近一些。

写了一段程序来看看经纬度（x坐标和y坐标）互相交错形成的有序值对应的坐标是多少。

//vs2008#include "stdafx.h"
#include <atlstr.h>
#include <conio.h>void GetEvenAndOdd(int nNum, int &nEven, int &nOdd)
{int k = 1;nEven = nOdd = 0;for (int i = 0; i < 8; i++){if (0 != i%2){nEven += k*(nNum & 1);} else{nOdd += k*(nNum & 1);}if (0 != i%2) k *= 2;nNum = nNum >> 1;}
}CString GetBinaryString(int nNum, int nLen)
{CString csRet;for (int i = nLen; i > 0; i--){if ((nNum >> (i-1)) & 1)csRet += "1";elsecsRet += "0";}return csRet;
}int _tmain(int argc, _TCHAR* argv[])
{printf("十进制	geohash值	偶    奇    坐标值\n");for (int i = 0; i < 64; i++){int nEven, nOdd;GetEvenAndOdd(i, nEven, nOdd);CString strGeohash = GetBinaryString(i, 8);CString strEven    = GetBinaryString(nEven, 4);CString strOdd     = GetBinaryString(nOdd, 4);printf("%02d\t%S\t%S\t%S\t(%d,%d)\n", i, strGeohash.GetBuffer(), strEven.GetBuffer(), strOdd.GetBuffer(), nEven, nOdd);}_getch();return 0;
}

将坐标点依次在坐标系上连起来如下图：

可以看出来，geohash和 july文中讲述的R数方法有图形上的分区域相似之处，这种编码方式在区块内尽可能的让邻近点的索引值靠近，但在区块与区块之间还是存在跳跃的地方。所以只简单使用这一种编码技术并不能完全解决邻近点搜索的问题。

要想完美解决问题，还需要考虑的更多一些。

这些问题留待以后继续研究。先写这么多吧。

update:

早上起来搜索了下别人的文章，看到了下面的话：

geohash的最大用途就是附近地址搜索了。不过，从geohash的编码算法中可以看出它的一个缺点：位于格子边界两侧的两点， 虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题。

(from: http://tech.idv2.com/2011/07/05/geohash-intro/)