Hilbert曲线简介及生成算法

Hilbert曲线

Hilbert曲线是一种空间填充曲线，类似的填充曲线还包括Z曲线。Hilbert曲线依据自身空间填充曲线的特性，可以线性地贯穿二维或者更高维度每个离散单元，并且仅仅穿过一次，并对每个离散单元进行线性排序和编码，该编码作为该单元的唯一标识。由于Hilbert 编码没有出现大步幅的跳转，所以Hilbert空间排列的聚集性能较好，即Hilbert曲线上相邻的点，在原始空间上一定相邻。

Hilbert曲线如下图所示：

Hilbert曲线生成的关键是如何计算每一个离散单元所对应的编码以及根据编码获得离散单元所处的位置。代码如下：

package study;

class Point {
    public int x;   // X坐标
    public int y;   // X坐标

    public Point() {
    }

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Hilbert {

    private void rot(int n, Point pt, int rx, int ry) {
        if (ry == 0) {
            if (rx == 1) {
                pt.x = n - 1 - pt.x;
                pt.y = n - 1 - pt.y;
            }

            //Swap x and y
            int temp = pt.x;
            pt.x = pt.y;
            pt.y = temp;
        }
    }

    //Hilbert代码到XY坐标
    public void d2xy(int n, int d, Point pt) {
        int rx, ry, s, t = d;
        pt.x = pt.y = 0;
        for (s = 1; s < n; s *= 2) {
            rx = 1 & (t / 2);
            ry = 1 & (t ^ rx);
            rot(s, pt, rx, ry);
            pt.x += s * rx;
            pt.y += s * ry;
            t /= 4;
        }
    }

    //XY坐标到Hilbert代码转换
    public int xy2d(int n, Point pt) {
        int rx, ry, s, d = 0;
        for (s = n / 2; s > 0; s /= 2) {
            rx = ((pt.x & s) > 0) ? 1 : 0;
            ry = ((pt.y & s) > 0) ? 1 : 0;
            d += s * s * ((3 * rx) ^ ry);
            rot(s, pt, rx, ry);
        }
        return d;
    }

    public static void main(String[] args) {
        Hilbert hilbert = new Hilbert();
        int n = 8;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf("%2d ", hilbert.xy2d(n, new Point(j, i)));
            }
            System.out.println();
        }
    }
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

输出

 0  3  4  5 58 59 60 63 
 1  2  7  6 57 56 61 62 
14 13  8  9 54 55 50 49 
15 12 11 10 53 52 51 48 
16 17 30 31 32 33 46 47 
19 18 29 28 35 34 45 44 
20 23 24 27 36 39 40 43 
21 22 25 26 37 38 41 42 
1
2
3
4
5
6
7
8

上面的代码需要注意的是，变量n是网格在X方向或者Y方向上单元的个数，n必须是2的次方。（Hilbert曲线是一种能填充满一个平面正方形的分形曲线（空间填充曲线））

https://blog.csdn.net/firecoder/article/details/7178928