GeoHash

2018/01/25

Tags: geohash

我们的应用里面,会有需要用户提交一些坐标点,然后还需要判断这些坐标点和其他坐标点是不是重合或者距离在一定范围内(例如 200M)。

这个需求最简单的做法就是用户提交的时候,循环和所有需要判断的点比较一下就可以了,但是如果数据量比较大的情况下,这个消耗还是很可观的,因为无法提前索引。所以我们就想,是不是有更好的思路呢?

一个比较简单的思路是,每次坐标点存储的时候都 hash 一下,一定范围内的,都 hash 到同一个值,这样比较的时候只需要做等于判断就可以了,这个可以索引。那么最简单的做法就是参考 https://en.wikipedia.org/wiki/Decimal_degrees 把坐标点的经纬度按照精度 round,例如 123.4567890123123.4567894562 都 round 为 123.456789 ,但是这么做无法精确到想要的那个 200M。

然后依据上面的思路,和四舍五入的思路,我琢磨是不是可以弄一个 x 舍 x+1 入这么个逻辑,把坐标轴分为 x 等份。然后我就可以通过自己定义 x 来做到想要的精度了(通过经纬度来定义实际距离应该本身就是有误差的,这个和把球面坐标系投影到平面坐标系的方法有关系)。

按照上面 x 舍 x+1 入的逻辑,实际上是把平面分成了 n 个正方形,同一个正方形里面的,可以认为他们是符合条件的。但是,很明显在相邻的区域里面的,也有可能有符合条件的点,比如两个点分别在区域的这边和另一边。这些点怎么找到呢?

有一个思路是先找到点所在的区域,然后把周围 8 个区域的点也找出来,这个查找是可以索引的,是 O(1) 的,然后再循环的和找出来的点单个做比较算距离,这个过程是 O(n),但是 n 小了很多。

上面是我山寨的一个思路,找了一下发现已经有了,就是 geohash,可以看参考链接,里面比较详细了。

参考链接

Comments