2

[(x1,y1),(x2,y2), ..., (xn,yn)]モートンでソートされたポイントのコレクションがあります。これらのポイントからポインターベースの圧縮された四分木を構築したいと考えています。Eppstein et al と Aluru を読むと、これは比較的単純な作業であるという印象を受けます。

残念ながら、両方の記事の説明には疑似コードがなく、やや扱いにくいものになっています。したがって、ツリーを構築するために必要な具体的な操作を説明する高レベルの擬似コードを誰かが提供できるかどうか疑問に思っています。

4

1 に答える 1

2

エンコード方法に特に注意してください。いくつかのビットハックがあります =)。

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
    }


}
于 2011-10-19T21:11:09.380 に答える