何千もの長方形が交差しているかどうかを確認する

Question

現在、Bukkitプラグインを使用してカスタム領域を要求していますが、クレームを作成する前に領域が重複していないかどうかを確認するために矩形（および.intersect（））を使用しています。

私は確かに、これはかなりの時間がかかりますと（最終的には数万があるだろうそれらの）一つ一つの既存の請求をチェックする必要はありません方法を把握しようとしています。私はまた、プレーヤーがブレイクブロックやブロックを置くなどの作業を行うときに、クレーム所有者を確認する必要があります。

私の現在のシステム（カスタムクレームサイズは許せません。正方形のみ）では、クレームの近くのクレームを検出することができるので、最大で約10個のクレームをチェックする必要がありますこのシステムでのクレームの最大半径）が、新しいシステムでは理論上はクレームサイズが無限大になります。

すべての長方形に大量の時間がかかることを確認していますか？私がばかげているのですが、大きさが無制限であっても、近くの矩形をチェックする方法はありますか？

Answer 1

長方形のすべてのチェックを何千人もの第一は、大きなjavaに関する契約（またはプラグイン）ことつもりではありません。その簡単な数学はミリ秒単位で行う必要があります。あなたの所有者の問題に対処するために私はあなた自身の長方形と所有者クラスを作成することをお勧めします。だからあなたの四角形には所有者が定義されていて、プレイヤーが現在所有している領域の所有者であるかどうかを簡単に確認できます。

public class custom_Area extends Rectangle{ 

    private owner o; 

    public owner getOwner() { 
     return o; 
    } 

    public void setOwner(owner o) { 
     this.o = o; 
    }  
} 

EDIT：

は、私はちょうど100.000ランダムな長方形を作成し、そのうちの一つは、他の人と交わるかどうかをチェックすることによってそれをテストしました。

--custom矩形クラス

public class area extends Rectangle{ 
private owner o; 
public area(owner o, int i, int i1, int i2, int i3) { 
    super(i, i1, i2, i3); 
    this.o = o; 
} 
public owner getO() { 
    return o; 
} 
public void setO(owner o) { 
    this.o = o; 
} 

}

--custom所有者クラス

public class owner { 
String name; 

public owner(String name) { 
    this.name = name; 
} 
public String getName() { 
    return name; 
} 
public void setName(String name) { 
    this.name = name; 
} 

}

--Mainクラス

public class Rectanglesearch { 
     public static area a[] = new area[100000]; 
     public static owner o[] = new owner[10]; 
     public static int intersectCounter = 0; 
     public static int ownerCounter = 0; 

    public static void main(String[] args) { 
     for(int y = 0; y<10;y++){ 
     o[y] = new owner("y"); 
     } 
     for (int i = 0; i < 100000; i++) { 
      a[i] = new area(o[(int)(Math.random() * 10)],random(),random(),random(),random()); 
     } 
     checkArea(a[10]); 
     checkOwner(o[3]); 
     System.out.println("Area a[10] intersects with "+intersectCounter+" out of "+a.length); 
     System.out.println("Owner o[3] owns "+ownerCounter+" areas out of "+a.length); 
    } 
    public static int random(){ 
    return (int)(Math.random() * 100000) + 1; 
    } 
    public static void checkArea(area ab){ 
      for (area a1 : a) { 
       if (ab.intersects(a1)) { 
        intersectCounter +=1; 
       } 
      } 
    } 
    public static void checkOwner(owner ob){ 
      for (area a1 : a){ 
       if(a1.getOwner()==ob){ 
        ownerCounter +=1; 
       } 
      } 
    } 
} 

方法checkArea（面積AB）は男性の領域が所有されているか、あなたを返す私のOB

Answer 2

は、quadtreeとしての加速度構造であなたの四角形を格納考えてみましょエリアAB 方法checkOwner（所有者OB）と交差する方法男のエリア戻ります。既存のセットに対して新しい矩形をテストするには、道に沿って、各ノードでの長方形に対してテストしていますが、通過していないすべてのノードで長方形を無視して、それを含んでいるでしょうノードにツリーを下に移動したいです。これにより、個々に個別にテストすることなく、新しいものと交差する可能性のない矩形がすぐに削除されます。 のような他の加速構造も可能である。関連性のあるその他のリストについては、spatial indexesを参照してください。

---

新しい矩形を追加することはあまり頻繁ではないため、パフォーマンスはおそらく大きな問題ではありません。しかし、あなたのプラグインは特定の座標（ブロックなど）が要求された領域の1つに含まれているかどうかを確認する必要があると考えています。これは潜在的にすべてのフレームです。 。クアッドツリーやその他のアクセラレーション構造は、そのために価値があります。