RSS订阅
Lucene 如何通过GeoHash 查询距离
之前用Lucene做过位置距离查询的项目，其中Lucene搜索定位距离的原理就是GeoHash，关于GeoHash的介绍看这里GeoHash 介绍，这篇文章要说的是如何根据GeoHash查询距离。
以下面以这幅图来看，图片将经度为0作为X轴的原点，纬度为0作为Y轴的原点，图中为了问题简单化，仅化了3层，实际中3层是不够的。
假设坐标轴正方向表示1，负方向表示0。那么按照GeoHash方法划分区域，则A到J的GeoHash分别为：
| 位置点 | GeoHash经度值 | GeoHash纬度值 | GeoHash值(经度+维度) |
| A | 1 0 0 | 1 0 0 | 11 00 00 |
| B | 1 0 0 | 0 1 1 | 10 01 01 |
| C | 0 1 1 | 0 1 1 | 00 11 11 |
| D | 0 1 1 | 1 0 0 | 01 10 10 |
| E | 1 1 0 | 1 1 0 | 11 11 00 |
| F | 1 1 1 | 1 1 1 | 11 11 11 |
| G | 1 1 1 | 1 1 1 | 11 11 11 |
| H | 1 1 1 | 0 1 1 | 01 11 11 |
| I | 0 1 0 | 0 1 0 | 00 11 00 |
| J | 0 0 0 | 1 1 1 | 01 01 01 |
情况1：
我们看E、F两个点，其中前两层都是11，仅第三层不一致，E、F离得很近。
情况2：
我们看E、I两个点，第二、三层匹配，仅第一层不一致，E、I却离得很远。同理B、J也一样。
推测结果：
那么我们可以这样认为，GeoHash匹配距离时，必须从前往后，直到第一个不能匹配为止，匹配的层数越多越相近。
情况3：
拿着结果1，我们看F、G两个点，三层完全匹配，是不是F、G的距离要比E、F的距离近呢？不是，E、F距离更近。
情况4：
加速A、B、C、D无限靠近原点，那么A、B、C、D应该离得非常近，但是我们看GeoHash，A、B、C、D并不是按照从前往后匹配的。
分析结果
GeoHash并不是通过从前往后匹配来判断距离的，推测结果是错误的，那是通过什么呢？下面是我的猜测，具体实现思路还需要看看Lucene的源码。
A、B、C、D四个点，如果按字符串从前往后匹配，那么匹配程度非常低，但是如果把Hash当成一个二进制数，100表示4，而011表示3，通过数的差的绝对值，我们发现，无论是经度还是维度，A、B、C、D之间的差的绝对值都不会大于一。因为A、B、C、D无限靠近原点，即使有Geo划分有无限层，A的维度是1 0 0 0 0 0...（无限0），B的维度是0 1 1 1 1 1...(无限1)，那么他们的绝对值仍然不会大于1。同样的，ABCD任意两点的经纬度差绝对值不会大于1。由于都是整数，除了0之外，最小差绝对值就是1。
由此我们可以推论：判断两个点的距离，是通过GeoHash的经纬度Hash分别按照二进制取差，绝对值越小，则距离越近。
至于经度和维度的合并的距离，由于经纬度是完全垂直的，就可以根据平方和（勾股定理）来定了。
如何判断F、G要比E、F远，应该就没有办法，因为这儿划分的层次太少，当划分层次多的时候，经纬度绝对值差E、F自然会比F、G小。所以，分层的大小直接影响到距离的精度。
以上都是自己分析的，不知是否正确，如有错误，欢迎批评指正。
Load Disqus comments, wait a moment..
更多订阅