既然邻接区域的人距离我们更近,那我们是不是可以建立一个更大的候选集合,把这些邻接区域的用户都加进去,再一起计算距离和排序,这样问题是不是就解决了呢?我们先试着操作一下。
对于目标所在的当前区域,我们可以根据期望的查询半径,以当前区域为中心向周围扩散,从而将周围的区域都包含进来。假设,查询半径正好是一个区域边长的一半,那我们只要将目标区域周围一圈,也就是 8 个邻接区域中的用户都加入候选集,这就肯定不会有遗漏了。这时,虽然计算量提高了 8 倍,但我们可以给出精准的解了。
如果要降低计算量,我们可以将区域划分的粒度提高一个量级。这样,区域的划分就更精准,在查询半径不变的情况下,需要检索的用户的数量就会更少(查询范围对比见下图中两个红框部分)。
知道了要查询的区域有哪些,那我们怎么快速寻找这些区域的编码呢?这就要回到我们区域编码的方案本身了。前面我们说了,区域编码可以根据奇偶位拆成水平编码和垂直编码这两块,如果一个区域编码是 0110,那它的水平编码就是 01,垂直编码就是 10。那该区域右边一个区域的水平编码的值就比它自己的大 1,垂直编码则相同。因此,我们通过分解出当前区域的水平编码和垂直编码,对对应的编码值进行加 1 或者减 1 的操作,就能得到不同方向上邻接的 8 个区域的编码了。
以上,就是精准查询附近人的检索过程,我们可以总结为两步:
● 第一步,先查询出自己所属的区域编码,再计算出周围 8 个邻接区域的区域编码;
● 第二步,在索引中查询 9 次,取出所有属于这些区域中的人,精准计算每一个人和自己的距离,最后排序输出结果。