我目前正在为游戏编写一个插件，其中一个功能包括能够设置由 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