查找包含給定座標的區域

Question

上下文：我正在爲Spigot（Minecraft服務器插件）開發一個插件。

我想爲多個目的定義幾個區域。我將它們存儲在像這樣（YAML）的配置文件：

Regions 
    Region1: 
    P1: 
     X: 0 
     Y: 0 
     Z: 0 
    P2: 
     X: 1 
     Y: 1 
     Z: 1 
    Region2: 
    P1: 
     X: -1 
     Y: -1 
     Z: -1 
    P2: 
     X: 2 
     Y: 2 
     Z: 2 

正如你所看到的，我存儲的區域與2個對面座標。

我試圖想出一個算法，可以在數組中存儲所有包含給定座標的區域。

例如，(0,0,0) =>[Region1, Region2]和(2,2,2) =>[Region1]

我在做什麼現在的問題是：

1. 人口與各地區
2. 檢查如果X座標是一個數組在定義該區域的2個X座標之間
3. 如果不是，則從該數組中刪除該區域。如果是，則轉到2.然後檢查Z座標，然後檢查Y.

此解決方案對於少數幾個區域（不超過20個）似乎可行，但是因爲這將用於可觸發的事件每秒多次，我希望能夠通過更好的解決方案來實現這一點，該解決方案可以處理更多的區域並更快地完成。

我看着Data structures that can map a range of values to a key?，但我的地區可以重疊，所以我不能用這種方式。

你有什麼想法嗎？

我不想使用Worldedit/Worldguard API，但「通用」Java API很好。

Answer 1

我通過使用R-tree

R-樹是用於空間的訪問方法，即，用於索引多維信息諸如地理座標，矩形或多邊形的樹數據結構中找到的解決方案。

我測試2個實施方式：

• JSI
  • Documentation
  • Example
• 實施R-樹的由拉斯·威克斯（上this答案找到）
  • Source
  • Unit Tests

雖然JSI是非常簡單的實現，有一個完整的例子，它需要添加3個API與沒有錯誤/警告正常工作，併爲之努力2個維度（仍然有用，因爲Y座標對於我在我的Minecraft插件中的使用並不真正相關）。

所以我使用了第二個實現，因爲它可以處理多個維度，使用任何對象作爲條目，並且只使用一個類。

這裏是我的代碼（小測試搜索包含一個點的所有地區）：

private static final float[] ZEROES = { 0.0f, 0.0f, 0.0f }; 
private static final float[] POINT_FIVES = { 0.5f, 0.5f, 0.5f }; 
private static final float[] ONE_FIVES = { 1.5f, 1.5f, 1.5f }; 
private static final float[] ONES = { 1.0f, 1.0f, 1.0f }; 

public static void main(String[] args) { 
    RTree<Object> rt = new RTree<Object>(50, 2, 3); 
    rt.insert(ZEROES, ONES, "Region1"); 
    rt.insert(ONES, ONES, "Region2"); 

    System.out.println(rt.search(POINT_FIVES, ZEROES)); 

} 

輸出是：

[區域1]