我目前正在为游戏编写一个插件，其中一个功能包括设置由2个二维坐标（矩形的左上角和右下角区域）定义的区域的能力。然后存储这些区域，并且将具有与每个区域相关联的各种其他数据。当玩家在世界各地移动时，我需要确定他何时只从玩家的坐标进入这些区域中的一个，并且这样做的方法必须是有效的，因为这最终会被称为每秒数百次。
是否有任何数据结构可以有效地支持这种搜索，如果是这样，我在哪里可以找到它的文档，找到要使用的java实现，或者如果需要，自己实现它？
我还想注意，我发现了一些似乎只支持批量加载的树结构，但我必须能够实时添加和删除此结构中的值。
确定空间部分碰撞的良好数据结构是 四叉树 数据结构。四叉树根据给定区域中的元素数量递归地划分空格。因此，如果坐标在对数时间内位于区域内，则可以进行搜索。
编辑：我找到了一个实现 这里 但没有给出许可证信息。
在一维情况下，合适的数据结构是 区间树。
要解决二维强制转换，您可以使用区间树快速查找包含至少一个维度中的点的矩形，并检查每个矩形的第二个维度（可能已经足够快），或者使用维基百科文章简要概述了许多方面的概括（尽管我必须承认我不理解第一次阅读的概括）。
假设玩家移动缓慢（即区域进入或离开事件的数量与区域数量相比较小），以下方法可能更有效：保留x坐标的搜索树，其中矩形开始或结束，以及a y坐标的类似树。如果玩家进入或离开某个区域，他必须越过边界点的x或y坐标。也就是说，您将在x搜索树上对范围[old_x，new_x]执行范围查询，并检查每个矩形。对y方向执行相同操作（不报告重复项）。
要实现坐标，您可以在实现您正在寻找的功能的类中使用Point2D：
http://download.oracle.com/javase/6/docs/api/java/awt/geom/Point2D.html