从morton有序点构建四叉树

Question

我有一个点[(x1,y1),(x2,y2), ..., (xn,yn)]的集合，它们是Morton排序的。我希望从这些点构造一个基于指针的压缩四叉树。读了Eppstein等人和Aluru，我的印象是这应该是一个相对简单的任务。

不幸的是，两篇文章中的解释都缺少伪代码，并且有些难以处理。因此，我想知道是否有人可以提供高级伪代码来描述构建树所需的具体操作。

Answer 1

要特别注意编码方法。它有一些双峰=)。

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
    }

}