CODEWITHSUNDEEP
javabukkitrectangles
CT16
CT16

Reputation: 21

Checking if thousands of rectangles intersect

I'm currently working on a Bukkit plugin to claim custom areas, and I'm using rectangles (and .intersect()) to check if regions overlap before creating a claim.

I'm trying to figure a way where I don't need to check every single existing claim (of which there eventually will be tens of thousands) as surely this will take quite some time. I'll also need to check for claim owners when players do things such as break blocks or place blocks.

In my current system (which doesn't allow custom claim sizes, only squares) I only need to check at most about 10 claims because I can detect claims within the vicinity of the claim (at most 64 blocks away which is the max radius of claims in this system) but now the claim sizes can be infinitely large in theory with the new system.

Is checking all the rectangles going to take a massive amount of time? Am I being dumb, is there a way to check for rectangles within the vicinity even while the size is unlimited?

Upvotes: 2

Views: 136

Answers (2)

Wyzard
Wyzard

Reputation: 34573

Consider storing your rectangles in an acceleration structure such as a quadtree. To test a new rectangle against the existing set, you'd navigate down the tree to the node that would contain it, testing against the rectangles in each node along the way, but ignoring the rectangles in all the nodes you don't traverse. This quickly eliminates lots of rectangles that can't possibly intersect the new one, without having to test each one individually.

Other acceleration structures are also possible as alternatives, such as binary space partitioning. Read about spatial indexes for a list of several others that may be relevant.

Adding new rectangles to the set doesn't happen very often, so performance probably isn't a big concern. But I'd imagine that your plugin also needs to check whether a specific coordinate (such as a block) is within one of the claimed regions, and that may happen much more often — potentially every frame — so it really does need to be fast. A quadtree or other acceleration structure will be valuable for that.

Upvotes: 1

Till Hemmerich
Till Hemmerich

Reputation: 168

First of all checking thousands of rectangles is not gonna be a big deal for java(or your Plugin). Its simple math and should be done in millisecs. To deal with your owner Problem i would recommend you to create my own rectangle and owner class. So your rectangle can have a defined owner and you can simply check if the player is the owner of the area he is in right now. 

public class custom_Area extends Rectangle{

    private owner o;

    public owner getOwner() {
        return o;
    }

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

EDIT:

I just tested it by creating 100.000 random rectangles and checking if one of them intersects with others.

--Custom rectangle class

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 owner class

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 class

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

method checkArea(area ab) returns you how man areas intersects with area ab method checkOwner(owner ob) return you how man areas are owned my ob

Upvotes: 1

Related Questions