算法
July 8, 2019

Morton码

版权声明：本文为博主原创文章，转载请注明原文出处！

写作时间：2019-07-08 17:11:27

Morton码的计算

Morton码是对栅格格网进行编码的一种算法，在Google中搜索Morton，搜索结果第一位是Wikipedia的Z-order Curve，这是因为Morton码编码结果展现为一种Z形的填充曲线。下面简要说一下如何计算四进制和十进制的Morton码。

Morton码二进制

四进制Morton码计算

四进制编码对左上，右上，左下，右下的顺序对四个格网单元分布编码为0，1，2，3。

其计算方式为：二进制的行列号$r$、$l$（从第0行0列开始），四进制编码$M=2l+ r$；那么这里就是：第5行（101）第7列（111）：$M=2101+111=313$（313对应的十进制是55）

十进制Morton码计算

十进制的编码规则：首先，行列号转为二进制（从第0行0列开始）；然后行列号交叉排列；最后将二进制结果转为十进制。十进制Morton编码是按左上，右上，左下，右下的顺序从0开始对每个格网进行自然编码的。

对于第5行（101）第7列（111），交叉排列得到110111，然后转为十进制就是55。和四进制的编码结果是一样的。

下面给出十进制Morton码的C++实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

using std::cout;

int main() {
    uint32_t row = 5;
    uint32_t col = 7;
    uint64_t morton = 0;

    for (int i = 0; i < sizeof(row) * 8; i++) {
        morton |= (row & (uint64_t)1 << i) << i | (col & (uint64_t)1 << i) << (i + 1);
    }
    cout << morton << '\n';
    return 0;
}