把地图坐标的横纵二进制位交错存放,会得到一种不同于逐行扫描的编号方式。它能让对齐的正方形区域形成连续区段,但并不是所有矩形都能只用一个区段表示。

先确定规则与输入

地图八乘八,横纵各三位。横坐标第i位放到编号第2i位,纵坐标第i位放到第2i加1位。也可以理解为从大到小按左上、右上、左下、右下顺序选择象限。

地图8×8,横纵各三位。前三个小区域对齐,最后一个小区域未对齐。

逐项算出过程

点1坐标[0, 1],横位000、纵位001,交错编号000010,十进制2。

点2坐标[5, 6],横位101、纵位110,交错编号111001,十进制57。

点3坐标[0, 2],横位000、纵位010,交错编号001000,十进制8。

点4坐标[7, 2],横位111、纵位010,交错编号011101,十进制29。

点5坐标[7, 0],横位111、纵位000,交错编号010101,十进制21。

点6坐标[6, 0],横位110、纵位000,交错编号010100,十进制20。

点7坐标[4, 0],横位100、纵位000,交错编号010000,十进制16。

点8坐标[3, 7],横位011、纵位111,交错编号101111,十进制47。

点9坐标[2, 5],横位010、纵位101,交错编号100110,十进制38。

点10坐标[4, 3],横位100、纵位011,交错编号011010,十进制26。

左上[6, 6]、边长2区域,对应编号[60, 61, 62, 63],最小最大之间共4个整数,而区域本身只占四格。

左上[4, 4]、边长2区域,对应编号[48, 49, 50, 51],最小最大之间共4个整数,而区域本身只占四格。

左上[2, 4]、边长2区域,对应编号[36, 37, 38, 39],最小最大之间共4个整数,而区域本身只占四格。

左上[1, 5]、边长2区域,对应编号[35, 38, 41, 44],最小最大之间共10个整数,而区域本身只占四格。

前三个区域的编号区间应连续;最后一个区域用于检查把最小最大编号之间的空隙误算进区域的风险。

复核时看什么

对每个格子都进行编码和解码,应该回到原坐标,六十四个编号也应不重不漏。检查左上坐标为偶数的二乘二区域,它的四个编号应恰好连续;再对比一个未对齐区域。

练习时可以先遮住结果,沿用相同输入独立记录中间状态,再逐项比较。发现不同后先定位最早分歧,确认边界包含方式、编号起点、更新顺序以及是否提前取整。最后结果一致也不表示每个中间步骤都正确,因此保留过程记录有助于看清原因。

适用范围

这只是空间编号规则,没有证明某个实际缓存一定更快。访问模式、块大小与数据布局都会影响效果。跨区域查询仍需拆成适当的区段,不能只拿最小最大编号就认定其中全部属于目标区域。