算法-Z-order算法

1、学习背景
激光雷达点云是无序的，Transformer只能对有序的数据进行处理，为了将Transformer用在点云处理中，需要将无序的点云转换成有序的数据，另外，由于Transformer会用到局部注意力机制，所以将无序的数据转成有序的数据后，还要尽可能的保持空间邻近性。
2、Z-order算法
Z-order就是一种可以将无序数据转换为有序数据同时可以在一定程度上保持空间邻近性的方法。
2.1 算法步骤
假设我们有一个二维空间中的点(x, y)，其中x = 5，y = 6。我们想要将这个点映射到Z-order曲线的一维索引上。以下是具体的步骤：
将坐标转换为二进制表示：
x = 5的二进制表示是101。
y = 6的二进制表示是110。
交错排列二进制位：
我们将x和y的二进制位交错排列，从最低位（最右边的位）开始。
交错后的二进制字符串是111001。
将交错后的二进制字符串转换为整数：

交错后的二进制字符串111001转换为十进制整数是57。
因此，点(5, 6)在Z-order曲线上的Z值是57。

这个过程可以推广到三维空间中的点(x, y, z)。例如，如果x = 5，y = 6，z = 3，那么：

将坐标转换为二进制表示：

x = 5的二进制表示是101。
y = 6的二进制表示是110。
z = 3的二进制表示是011。
交错排列二进制位：

我们将x、y和z的二进制位交错排列，从最低位开始。
交错后的二进制字符串是011110101。
将交错后的二进制字符串转换为整数：

交错后的二进制字符串011110101转换为十进制整数是485。
因此，点(5, 6, 3)在Z-order曲线上的Z值是485。

通过以上步骤就可以将高维无序点转换成一维有序点。
2.2 Z-order曲线

左图是一个Z-order曲线的示例，中间的图是用实际的二维无序点填充后的Z-order曲线，也就是说，Z-order曲线是基于点的实际位置以及用2.1的方法计算出的Z值，在原图中画出的曲线。比如：
图中1的坐标为（0，1），2的坐标为（1，1），3的坐标为（3，0），则1的交错后的二进制字符串为0010（对应的Z值为2），2的交错后的二进制字符串为0011（对应的Z值为3），3的交错后的二进制字符串为0101（对应的Z值为5）。根据Z值由小到大画Z-order曲线即如图所示。
之所以称之为Z-order曲线，是因为二维数据画出来的Z-order曲线形状像Z。在二维空间中，Z-order曲线呈现出类似字母"Z"的折线形状，而在三维空间中，Z-order曲线则更加复杂，但仍然保持了点的局部性。
之所以说，Z-order曲线保持了空间局部性，从Z-order曲线上就可以看出来，你看，1，2，3在空间上是邻近的，转成一维索引后，索引也是挨着的，三维空间类似，这就证明了Z-order曲线不仅可以有序还可以保持空间邻近性。