z-order-curve - Z-Index 有越界限制

Question

我需要从它的 2 个坐标 x，y 计算平面上一个点的 Z-Index (Morton)。

传统上，这只是通过比特交错来解决。

但是我有边界，我希望该点的 z-index 仅在其位于活动区域内时增加 morton 计数，而在外部时跳过计数。

需要明确的是，4x4 正方形中的典型 z 顺序是：

|  0  1  4  5 |
|  2  3  6  7 |
|  8  9 12 13 |
| 10 11 14 15 |

但是，如果我有一个 3x3 的活动区域，我希望索引计算如下：

|  0  1  4  x |
|  2  3  5  x |
|  6  7  8  x |
|  x  x  x  x |

如您所见，00-11 四边形已满，02-13 跳过了落在活动区域之外的 2 个点的计数，对于 20-31 和 22-33 也是如此。

重要提示：我想在不迭代的情况下执行此操作。

这个问题有已知的解决方案吗？

score 0 · Accepted Answer

要处理矩形区域，请将所有维度四舍五入到最接近的 2 次方，并线性打包长轴。

例如，在 5x4 矩形中结束编码点 (2,3) 如下，

将 5x4 向上舍入到最接近 2 的幂得到 8x4，即 3 位和 2 位

编码点 2,3 首先交错 0b010 的 2 位，0b11 得到 0b1110，x 维的第 3 位成为结果的第 5 位。

编码 4,2, 0b100, 0b11 变成 0b11010

为了找到 3x3 区域的 z 顺序，使用上述方法的上述逆向找到 4x4 区域的逆映射，同时生成映射跳过任何落在 3x3 区域之外的点。

映射看起来像

(0,0) -> (0,0)
(0,1) -> (1,0)
(0,2) -> (0,1)
(0,3) -> (1,1)
(1,0) -> (2,0)
(1,2) -> (2,1)
(2,0) -> (0,2)
(2,1) -> (1,2)
(3,0) -> (2,2)

1 回答 1