莫顿码Morton code的c语言实现

84 阅读 0 评论 56 点赞

我是靠谱客的博主安详棒棒糖，这篇文章主要介绍莫顿码Morton code的c语言实现，现在分享给大家，希望可以做个参考。

十进制 Morton码可以使用栅格单元的行列号计算

###原理部分
遵循C语言规范，矩阵的第一行为“0”行、第一列为“0”列，先将十进制的行列号转换成二进制数，进行“位”运算操作，即行号和列号的二进制数两两交叉，得到以二进制数表示的MD码，再将其转换为十进制数。
例如图中第二行和第三列对应的栅格单元，其二进制的行列号分别为:I＝0010，J＝0011；得到的MD码为:MD＝（0001101）2＝（13）10；用类似的方法，也可以由MD码反求栅格单元的行列号。
morton码顺序表
基本过程

###基本算法

复制代码

1
2
3
4
5
6
7
8
9
10
11
// 输入 x 和 y, 交叉后为 xyxyxy。
unsigned short x;
// x在奇数位
unsigned short y;
// y在偶数位
unsigned int md = 0; // 存储生成的Md码
for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // 核心交叉算法，基本思想为移位和位运算..
{
md |= (x & 1U << i) << (i + 1) | (y & 1U << i) << i;
}

###完整代码
#####代码一：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<limits.h>	//定义CHAR_BIT
int main(void)
{
unsigned short i,j;	//行号、列号
unsigned short n;	//栅格大小
unsigned int md[n][n];	//每个码位的值
printf("请输入栅格的行列数（0<=n<=65535)：");
if(scanf("%hd",&n) == 0)
return 0;
for(i = 0;i < n;i++)	//行循环
{
for(j = 0;j < n;j++)	//列循环
{
md[i][j] = 0;
for(int x = 0;x < sizeof(unsigned short) * CHAR_BIT;x++)	//行列号计算
md[i][j] |= (i & 1U << x) << (x + 1) | (j & 1U << x) << x;
printf("%5u ",md[i][j]);	//打印输出
}
printf("n");
}
return 1;
}

#####代码二：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h>
#include<limits.h>
void to_binary1(unsigned short n);
void to_binary2(unsigned int n);
int main(void)
{
unsigned short x,y;
unsigned int md;
printf("请输入行号和列号（q to quit)：");
while(scanf("%hd %hd",&x,&y) != 0)
{
printf("行号I=(%hd)10=(",x);
to_binary1(x);
printf(")2n");
printf("列号J=(%hd)10=(",y);
to_binary1(y);
printf(")2n");
md = 0;
for(int i = 0;i < sizeof(x) * CHAR_BIT;i++)
md |= (x & 1U << i) << (i + 1) | (y & 1U << i) << i;
printf("莫顿码MD=(%u)10=(",md);
to_binary2(md);
printf(")2n");
printf("n请输入行号和列号（q to quit)：");
}
printf("Done.n");
return 0;
}
void to_binary1(unsigned short n)
{
int r;
r = n % 2;
if (n >= 2)
to_binary1(n / 2);
putchar(r == 0 ? '0' : '1');
return;
}
void to_binary2(unsigned int n)
{
int r;
r = n % 2;
if (n >= 2)
to_binary2(n / 2);
putchar(r == 0 ? '0' : '1');
return;
}