我如何访问使用 Z 顺序以 O(1) 时间复杂度存储在数组中的数据?我需要通过坐标快速访问每个元素。有没有比使用 while 移位位更快的方法来访问这些数据?
一种方法是使用查找表(我有静态数据大小)
EDIT:
我现在的一个想法是使用 y*SIZE+x 按顺序存储叶子
EDIT 2.:
我正在 std::bitset 中的四叉树中讲述位。我正在尝试检查某些数据是否可用。大小为 128*128 的矩阵。所以我可以跳过暴力矩阵搜索空数据。
您可以使用以下代码计算 z 顺序曲线值:
uint32_t calcZOrder(uint16_t xPos, uint16_t yPos)
{
static const uint32_t MASKS[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const uint32_t SHIFTS[] = {1, 2, 4, 8};
uint32_t x = xPos; // Interleave lower 16 bits of x and y, so the bits of x
uint32_t y = yPos; // are in the even positions and bits from y in the odd;
x = (x | (x << SHIFTS[3])) & MASKS[3];
x = (x | (x << SHIFTS[2])) & MASKS[2];
x = (x | (x << SHIFTS[1])) & MASKS[1];
x = (x | (x << SHIFTS[0])) & MASKS[0];
y = (y | (y << SHIFTS[3])) & MASKS[3];
y = (y | (y << SHIFTS[2])) & MASKS[2];
y = (y | (y << SHIFTS[1])) & MASKS[1];
y = (y | (y << SHIFTS[0])) & MASKS[0];
const uint32_t result = x | (y << 1);
return result;
}
它是从这里拍摄的位摆弄黑客
从 128x128 数组(或任何其他大小)中,您可以轻松计算任何位置的 z 顺序曲线值。例如:
xPos = 2, yPos = 3 -> z order curve value = 7
示例代码的最大数组大小为 65536*65536。为了方便起见,只需使用 2 的幂,在这种情况下,最大浪费的空间约为。 3/4
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)