对于一个完整的二维空间,我们可以用二分的思想将它均匀划分。也就是在水平方向上一分为二,在垂直方向上也一分为二。这样一个空间就会被均匀地划分为四个子空间,这四个子空间,我们可以用两个比特位来编号。在水平方向上,我们用 0 来表示左边的区域,用 1 来表示右边的区域;在垂直方向上,我们用 0 来表示下面的区域,用 1 来表示上面的区域。因此,这四个区域,从左下角开始按照顺时针的顺序,分别是 00、01、11 和 10。
接下来,如果要继续划分空间,我们依然沿用这个思路,将每个区域再分为四块。这样,整个空间就被划分成了 16 块区域,那对应的编号也会再增加两位。比如说,01 编号的区域被划分成了 4 小块,那这四小块的编号就是在 01 后面追加两位编码,分别为 01 00、01 01、 01 10、 01 11。依次类推,我们可以将整个空间持续细分。具体划分到什么粒度,就取决于应用对于「附近」的定义和需求了。
这种区域编码的方式有 2 个优点:
- 区域有层次关系:如果两个区域的前缀是相同的,说明它们属于同一个大区域;
- 区域编码带有分割意义:奇数位的编号代表了垂直切分,偶数位的编号代表了水平切分,这会方便区域编码的计算(奇偶位是从右边以第 0 位开始数起的)。