algorithm - 从莫顿订购点开始的四叉树施工

我有一个点的集合[(x1,y1),(x2,y2), ..., (xn,yn)]是莫顿排序的。我想从这些点构造一个基于指针的压缩四叉树。阅读Eppstein等人和Aluru，我的印象是这应该是一个相对简单的任务。
不幸的是，这两篇文章中的解释都缺少伪代码，而且有些棘手。因此，我想知道是否有人可以提供高级伪代码来描述构造树所需的具体操作。

最佳答案

请特别注意编码方法。它有一些bitchacks=）。

import java.util.*;
class MortonQuadTree<E> {

    List<E> data = new ArrayList<E>();

    public E insert(int x, int y, E e) {
        int pos = encode(x,y);
        ensureCapacity(pos);
        return data.set(pos,e);
    }

    public E query(int x, int y) {
        int pos = encode(x,y);
        return data.get(pos);
    }

    private void ensureCapacity(int size) {
        while(data.size() < size + 1) data.add(null);
    }

    // technically the values here aren't final... don't overwrite them :)
    static final int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
    static final int S[] = {1, 2, 4, 8};

    /**
     * Interleave lower 16 bits of x and y, so the bits of x
     * are in the even positions and bits from y in the odd;
     * x and y must initially be less than 65536.
     * Adapated from http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
     */
    private static int encode(int x, int y) {
        x = (x | (x << S[3])) & B[3];
        x = (x | (x << S[2])) & B[2];
        x = (x | (x << S[1])) & B[1];
        x = (x | (x << S[0])) & B[0];

        y = (y | (y << S[3])) & B[3];
        y = (y | (y << S[2])) & B[2];
        y = (y | (y << S[1])) & B[1];
        y = (y | (y << S[0])) & B[0];

        return x | (y << 1);
    }

    public static void main(String[] args) {

        MortonQuadTree<String> tree = new MortonQuadTree<String>();
        tree.insert(1,4,"Hello");
        tree.insert(6,8,"World");
        System.out.println(tree.query(1,4)); // should be hello
        System.out.println(tree.query(6,8)); // should be world
        System.out.println(tree.query(9,6)); // should be null
        System.out.println(tree.query(900,600)); // should be index error
    }


}