Java中用于存储和搜索二维空间坐标的良好数据结构是什么？

Question

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

是否存在任何数据结构可以有效地支持此类搜索？如果是，我在哪里可以找到相关文档，以查找可用的java实现或必要时自己实现该算法？

我还想指出，我找到了一些似乎只支持批量加载的树形结构，但我必须能够实时添加和删除该结构中的值。

- Sethcran

---

请参考此答案。 - trashgod

有多少个矩形？矩形是否经常变化？添加/删除矩形是否有性能要求？ - meriton

@meriton - 矩形不会被改变，只会被添加和删除，因为这是在服务器上运行，所以它需要处理至少每秒几次的插入操作，而不会影响服务器的性能，尽管平均而言，它可能只会被调用一分钟一次。 - Sethcran

@trashgod - 我需要能够高效地搜索空间，而不仅仅是确定形状是否被包含，因为这已经是微不足道的了，但穷举搜索数千个或更多的形状以查看是否包含其中任何一个并不高效。 - Sethcran

你能具体说明一下是多少吗？比如10000？100000？1000000？ - meriton

@meriton - 我预计在给定时间内，空间中可能会有1-10k个区域。 - Sethcran

Answer 1

在空间中确定碰撞的一种好的数据结构是四叉树数据结构。 四叉树根据给定区域内的元素数量递归地划分空间。 因此，如果坐标位于区域内，则可以在对数时间内进行搜索。

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

- Yet Another Geek

---

迄今为止呈现出来的最佳解决方案。 - Sethcran

这样的答案让我想起了为什么我喜欢这个网站——我每天都在学习新东西！ - Hovercraft Full Of Eels

但问题不在于一个点是否在特定区域内，而是哪些区域新包含或不再包含该点。我不明白四叉树如何帮助解决这个问题？ - meriton

这个破损的链接 there 应该指向 Algorithms, 4th Ed 。还可以参考OpenMap API。 - trashgod

在GitHub上有一个MIT许可的QuadTree实现（https://github.com/varunpant/Quadtree）。 - chrisjleu

Answer 2

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

要解决二维问题，可以使用区间树快速查找至少在一个维度上包含点的矩形，并对每个矩形检查第二个维度（这可能已经足够快），或者使用维基百科文章简要概述的多维泛化（尽管我必须承认我第一次阅读时没有理解那个泛化）。

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

- meriton

Answer 3

要实现坐标，您可以在实现所需功能的类中使用Point2D：

http://download.oracle.com/javase/6/docs/api/java/awt/geom/Point2D.html

- james_bond