指定された座標を含む領域を見つける

Question

コンテキスト：私はSpigot（Minecraftサーバープラグイン）用のプラグインを開発中です。

複数の領域を複数の目的で定義したいと考えています。あなたが見ることができるように

Regions 
    Region1: 
    P1: 
     X: 0 
     Y: 0 
     Z: 0 
    P2: 
     X: 1 
     Y: 1 
     Z: 1 
    Region2: 
    P1: 
     X: -1 
     Y: -1 
     Z: -1 
    P2: 
     X: 2 
     Y: 2 
     Z: 2 

、私は2点の反対の座標で領域を格納している：私はこのような設定ファイル（YAML）に格納します。

私は、与えられた座標を含むすべての領域を配列に格納することができるアルゴリズムを試してみようとしています。例えば

、私が今やっている何を(0,0,0) =>[Region1, Region2]と(2,2,2) =>[Region1]

は次のとおりです。

1. 人口X座標かどうかのチェックすべての領域を持つ配列
2. があります領域を定義する2つのX座標の間
3. そうでない場合、配列から領域を削除します。 trueの場合、2に移動し、Z座標を確認し、その後、Y.

このソリューションは、いくつかの領域（20を超えない）のために実行可能なようだが、これがトリガされるイベントで使用されますので、 1秒に何回も、より多くの地域に対応し、より迅速に対応できる優れたソリューションでこれを実現したいと考えています。

私はData structures that can map a range of values to a key?を見ましたが、私の地域は重複する可能性がありますので、この方法では使用できません。

ご存知ですか？

Worldedit/Worldguard APIは使用しませんが、「汎用」Java APIは問題ありません。

Answer 1

IはR-tree

R木を使用して解決策を見つけたが、そのような地理座標、長方形または多角形のように多次元情報にインデックスを付けるための空間アクセス方法、即ち、に使用されるツリーデータ構造です。

I 2つの実装試験：（this回答に見出さ）ラスの週間Rツリーの

• JSI
  • Documentation
  • Example
• 実装を
  • Source
  • Unit Tests

JSIは、実装が本当に簡単でしたが、完全な例と、それはエラーなし/警告が正しく動作する3つのAPIを追加するために必要な、とのために働いていました2次元のみ（Y座標は私のMinecraftプラグインでの私の使用にはあまり関係しないので、今でも役に立ちます）。

複数のディメンションを処理し、オブジェクトをエントリとして使用し、1つのクラスのみを使用できるため、2番目の実装を使用しました。

ここに私のコード（ポイントを含むすべての領域を探索するための小テスト）は次のとおり

private static final float[] ZEROES = { 0.0f, 0.0f, 0.0f }; 
private static final float[] POINT_FIVES = { 0.5f, 0.5f, 0.5f }; 
private static final float[] ONE_FIVES = { 1.5f, 1.5f, 1.5f }; 
private static final float[] ONES = { 1.0f, 1.0f, 1.0f }; 

public static void main(String[] args) { 
    RTree<Object> rt = new RTree<Object>(50, 2, 3); 
    rt.insert(ZEROES, ONES, "Region1"); 
    rt.insert(ONES, ONES, "Region2"); 

    System.out.println(rt.search(POINT_FIVES, ZEROES)); 

} 

出力である：

[領域1]