Massive Algorithms: Hilbert Curve

Hilbert Curve - Airbnb

Hilbert Curve
Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步

int hilbertCurve(int x, int y, int iter) {
    if (iter == 0) return 1;
    int areaCnt = (1 << (iter * 2 - 2)); // 每一块区域边长的边界值
    int borderLen = (1 << (iter - 1)); // 区域移动的长度

    if (x >= borderLen && y >= borderLen) //右上角区域 = 前一阶往右上角移动borderLen
        return areaCnt * 2 + hilbertCurve(x - borderLen, y - borderLen, iter - 1);
    else if (x < borderLen && y >= borderLen) //左上角区域 = 前一阶往上移动borderLen
        return areaCnt + hilbertCurve(x, y - borderLen, iter - 1);
    else if (x < borderLen && y < borderLen) //右下角区域 = 前一阶按照y=x对称
        return hilbertCurve(y, x, iter - 1);
    else //右下角区域 = 前一阶按照y=-x对称，然后右移2*borderLen - 1，上移borderLen - 1
    // 设原来坐标(a,b) => (-b, -a) => (2*borderLen - 1 - b, borderLen - 1 - a) = (x, y)
    // => a = borderLen - 1 - y, b = 2*borderLen - 1 - x
        return areaCnt * 3 + hilbertCurve(borderLen - 1 - y, 2 * borderLen - 1 - x, iter - 1);
}

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/hilbert_curve/HilbertCurve.java

        public int hilbertCurve(int x, int y, int iter) {
            if (iter == 0) return 1;
            int len = 1 << (iter - 1);
            int num = 1 << (2 * (iter - 1));

            if (x >= len && y >= len) {
                // 3 Shape is identical with previous iteration
                return 2 * num + hilbertCurve(x - len, y - len, iter - 1);
            } else if (x < len && y >= len) {
                // 2 Shape is identical with previous iteration
                return num + hilbertCurve(x, y - len, iter - 1);
            } else if (x < len && y < len) {
                // 1 Clock-wise rotate 90
                return hilbertCurve(y, x, iter - 1);
            } else {
                // 4 Anti-Clockwise rotate 90
                return 3 * num + hilbertCurve(len - y - 1, 2 * len - x - 1, iter - 1);
            }
        }
    }

https://github.com/gabhi/leetcode-1/blob/master/b/HilbertCurve.java
public static int[][] generateHC(int n) {
int width = (int) Math.pow(2, n);
int[][] res = new int[width][width];
res[0][0] = 1;
res[0][1] = 2;
res[1][0] = 0;
res[1][1] = 3;
if(n <= 1) return res;

int w = 2;
for(int i = 2; i <= n; i++) {
w *= 2; //4

// top left
copy(res, w, 0, 0, w / 4, w / 4); // [0, 0] -> [1, 1]
// top right
copy(res, 2 * w, 0, w / 2, w / 2 - 1, w - 1); // [0, 2] -> [1, 3]
}
return res;
}

public static void copy(int[][] res, int offset, int x1, int y1, int x2, int y2) {
System.out.println("index: " + x1 + " " + x2 + " " + y1 + " " + y2);
for(int x = x1; x <= x2; x++) {
for(int y = y1; y <= y2; y++) {
// System.out.println(x + " " + y);
res[x][y] = res[x][y] + offset;
}
}
}

public static void main(String[] args) {
int n = 2;
int[][] result = generateHC(n);
for(int[] row : result) {
for(int elem : row) {
System.out.print(elem + " ");
}
System.out.println();
}
}

http://www.cnblogs.com/xuyuan77/archive/2008/10/13/1310269.html

德国数学家David Hilbert发现了一种曲线，首先把一个正方形等分成四个小正方形，依次从西南角的正方形中心出发往北到西北正方形中心，再往东到东北角的正方形中心，再往南到东南角正方形中心，这是一次迭代，如果对四个小正方形继续上述过程，往下划分，反复进行，最终就得到一条可以填满整个正方形的曲线，这就是Hibert曲线，其大致过程如下图所示