什么是在Java中存储和搜索2d空间坐标的良好数据结构

java spatial-query

2022-09-04 03:37:57

我目前正在为一款游戏编写插件，其中一个功能包括设置由2个二维坐标（矩形的左上角和右下角区域）定义的区域的能力。然后存储这些区域，并将具有与每个区域关联的各种其他数据。当玩家在世界上移动时，我需要仅从玩家的坐标中确定他何时进入其中一个区域，并且这样做的方法必须是有效的，因为这最终会被每秒调用数百次。

是否有任何数据结构可以有效地支持这种搜索，如果是这样，我在哪里可以找到有关它的文档，以找到要使用的java实现，或者如果需要，自己实现它？

我还想注意，我发现了一些似乎只支持大容量加载的树结构，但我必须能够实时地从此结构中添加和删除值。

答案 1

用于确定部分空间中碰撞的良好数据结构是四树数据结构。四元树根据给定区域中的元素数递归划分空间。因此，如果坐标在对数时间内位于某个区域内，它可以进行搜索。

编辑：我在这里找到了一个实现，但没有给出许可证信息。

答案 2

在一维情况下，合适的数据结构是区间树。

要解决二维转换，您可以使用区间树快速找到至少一个维度中包含点的矩形，并检查每个矩形的第二个维度（可能已经足够快了），或者使用维基百科文章简要概述的许多维度的推广（尽管我必须承认我在第一次阅读时不理解这种概括）。

假设玩家移动缓慢（即，与区域数量相比，进入或离开事件的区域数量很少），以下方法可能更有效：保留矩形开始或结束的x坐标的搜索树，以及y坐标的类似树。如果玩家进入或离开某个区域，他必须已越过边界点的 x 或 y 坐标。也就是说，您将在 x 搜索树上对范围 [old_x，new_x] 执行范围查询，并检查每个矩形。对 y 方向执行相同的操作（不报告重复项）。