检查数千个矩形是否相交

我目前正在使用Bukkit插件来声明自定义区域，并且我正在使用矩形（和.intersect（））在创建索赔之前检查区域是否重叠。检查数千个矩形是否相交

我试图找到一种方法，我不需要检查每一个现有的索赔（其中最终会有成千上万的），因为这肯定需要相当长的一段时间。我还需要在玩家做某些事情时检查索赔所有者，例如休息时间块或地点块。

在我目前的系统（不允许自定义索赔大小，只有正方形）我只需要检查最多约10个索赔，因为我可以检测索赔附近的索赔（最多64块，这是在这个系统中索赔的最大半径），但现在索赔规模在理论上可以是无限大的新系统。

检查所有要花费大量时间的矩形吗？我是愚蠢的，有没有办法检查附近的矩形，即使尺寸是无限的？

2016-10-04 CT16

首先检查数以千计的矩形对java（或者你的插件）不会有什么大不了的。它简单的数学，应该以毫秒来完成。要处理你的主人问题，我会建议你创建我自己的矩形和所有者类。所以你的矩形可以有一个定义的所有者，你可以简单地检查玩家是否是他现在所在区域的所有者。

public class custom_Area extends Rectangle{ 

    private owner o; 

    public owner getOwner() { 
     return o; 
    } 

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

编辑：

我只是通过创建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; 
}

}

- 主类

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）返回你的男人地区如何与相交区域AB 方法checkOwner（所有者OB）返回你的男人地区是如何拥有我的OB

来源

2016-10-04 11:55:50

考虑存储在加速结构中的矩形，如quadtree 。要根据现有集合测试新的矩形，可以沿着树形结构向下导航到包含它的节点，沿着每个节点测试矩形，但忽略所有不经过的节点中的矩形。这很快就消除了许多不可能与新的矩形相交的矩形，而无需单独测试每个矩形。

其他加速结构也可以作为替代方案，如binary space partitioning。请阅读spatial indexes以了解其他可能相关的其他列表。

向集合添加新的矩形并不经常发生，因此性能可能不是一个大问题。但我可以想象你的插件还需要检查一个特定的坐标（如一个块）是否在一个声称的区域内，而且这可能发生得更多 - 可能是每一帧 - 所以它确实需要快速。四叉树或其他加速结构对此很有价值。

来源

2016-10-04 12:34:19 Wyzard

检查数千个矩形是否相交

回答

相关问题