我目前正在为一款游戏编写一个插件，其中一个功能包括设置由 2 个二维坐标定义的区域（矩形的左上和右下区域）。然后，这些区域将被存储，并且将具有与每个区域相关联的各种其他数据。当玩家在世界上移动时，我需要仅根据玩家的坐标确定他何时进入这些区域之一，并且这样做的方法必须高效，因为这最终会每秒被调用数百次。
是否有任何数据结构可以有效地支持这种搜索，如果是的话，我在哪里可以找到有关它的文档，以找到要使用的java实现，或者如果需要的话，自己实现它？
我还想指出，我发现一些树结构似乎只支持批量加载，但我必须能够实时添加和删除该结构中的值。
用于确定部分空间中的碰撞的良好数据结构是四叉树 http://en.wikipedia.org/wiki/Quadtree数据结构。四叉树根据给定区域中元素的数量递归地划分空间。因此，它可以在对数时间内搜索坐标是否在某个区域内。
编辑：我找到了一个实现here http://algs4.cs.princeton.edu/92search/QuadTree.java.html但没有给出许可证信息。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
