モートン発注点からのクアッドツリー構築

Question

私はモートンソートされた[(x1,y1),(x2,y2), ..., (xn,yn)]点のコレクションを持っています。これらの点からポインタベースの圧縮クアッドツリーを構築したいと考えています。 EppsteinらとAluruを読むと、これは比較的単純な作業でなければならないという印象を受けています。

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

Answer 1

encodeメソッドに特に注意してください。それはいくつかのbithacks =）を持っています。

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 
    } 


}