檢查數千個矩形是否相交

我目前正在使用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

檢查數千個矩形是否相交

回答

相關問題