Überprüfen, ob sich Tausende von Rechtecken überschneiden

Question

Ich arbeite gerade an einem Bukkit-Plugin, um benutzerdefinierte Bereiche zu beanspruchen, und ich verwende Rechtecke (und .intersect()), um zu prüfen, ob sich Bereiche überschneiden, bevor ein Anspruch erstellt wird.

Ich versuche einen Weg zu finden, wo ich nicht jeden einzelnen Anspruch (von dem es irgendwann Zehntausende geben wird) überprüfen muss, da dies sicherlich einige Zeit dauern wird. Ich muss auch nach Besitzern von Ansprüchen suchen, wenn Spieler Dinge tun, wie Blöcke aufbrechen oder Blöcke platzieren.

In meinem derzeitigen System (das keine benutzerdefinierten Schadensgrößen zulässt, nur Quadrate) muss ich höchstens etwa 10 Ansprüche prüfen, da ich Ansprüche in der Nähe des Anspruchs erkennen kann (höchstens 64 Blöcke entfernt) der maximale Radius von Ansprüchen in diesem System), aber jetzt können die Anspruchgrößen in der Theorie mit dem neuen System unendlich groß sein.

Wird die Überprüfung aller Rechtecke sehr lange dauern? Bin ich dumm, gibt es eine Möglichkeit, um Rechtecke in der Nähe zu überprüfen, auch wenn die Größe unbegrenzt ist?

Answer 1

Zuerst die Überprüfung von Tausenden von Rechtecken wird nicht eine große Sache für Java sein (oder Ihr Plugin). Seine einfache Mathematik und sollte in Millisekunden erfolgen. Um mit Ihrem Besitzer umzugehen Problem Ich würde Ihnen empfehlen, mein eigenes Rechteck und Owner-Klasse zu erstellen. Ihr Rechteck kann also einen definierten Besitzer haben und Sie können einfach überprüfen, ob der Spieler der Besitzer des Bereichs ist, in dem er sich gerade befindet.

public class custom_Area extends Rectangle{ 

    private owner o; 

    public owner getOwner() { 
     return o; 
    } 

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

EDIT:

Getestet habe ich es nur von 100.000 zufälligen Rechtecken zu schaffen und zu überprüfen, ob einer von ihnen mit anderen schneidet.

--Custom Rechteck Klasse

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 Besitzer Klasse

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 Klasse

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; 
       } 
      } 
    } 
} 

Methode checkArea (Bereich ab) Sie gibt, wie man Bereiche mit einer Fläche ab schneidet Methode Sie check (Inhaber ob) zurückkehren, wie der Mensch Bereiche mein ob

Answer 2

Ihre Rechtecke in einer Beschleunigungsstruktur zu speichern, wie ein quadtree Betrachten Sie sind im Besitz . Um ein neues Rechteck gegen die vorhandene Menge zu testen, navigieren Sie in der Baumstruktur zu dem Knoten, der sie enthalten würde, testen Sie die Rechtecke in jedem Knoten auf dem Weg, ignorieren jedoch die Rechtecke in allen Knoten, die Sie nicht durchlaufen. Dadurch werden schnell viele Rechtecke eliminiert, die die neue nicht überschneiden können, ohne sie einzeln testen zu müssen.

Andere Beschleunigungsstrukturen sind auch als Alternativen möglich, z. B. binary space partitioning. Lesen Sie über spatial indexes für eine Liste von mehreren anderen, die relevant sein können.

Das Hinzufügen neuer Rechtecke zu dem Set passiert nicht sehr oft, daher ist die Leistung wahrscheinlich kein großes Problem.Aber ich würde mir vorstellen, dass Ihr Plugin auch prüfen muss, ob eine bestimmte Koordinate (wie ein Block) in einer der beanspruchten Regionen liegt und das viel häufiger vorkommen kann - möglicherweise in jedem Frame -, also muss es wirklich schnell sein . Ein Quadtree oder eine andere Beschleunigungsstruktur wird dafür wertvoll sein.