查找包含给定坐标的区域

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]