java - 查找包含给定坐标的区域

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) = > [区域 1]

我现在正在做的是:

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-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

我测试了 2 个实现:

• JSI
  • Documentation
  • Example
• Russ Weeks 的 R-Tree 实现(在 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));

}

输出是:

[Region1]