java - 一种有效索引数千个移动点的数据结构？

Question

情况:

我可能有数以万计的移动 (2D) 点。它们仅在一定半径范围内相互影响。它们可以从一个地方移动到另一个地方(本质上不是传送，只是在屏幕上飞来飞去)。

由于我必须在每次更新时检查更新，因此高效地执行此操作非常重要。

我天真的解决方案是简单地创建一个网格类型结构，网格间距围绕效果半径某处，并且随着点从一个单元格移动到另一个单元格，更新它们所在的单元格。所以当我需要进行效果检查时，我只必须检查一个点的单元格和几个相邻的单元格。

我熟悉四叉树，但我担心它比我需要做的要贵一点，但如果这确实是正确的路线，我愿意接受建议。

此外，对于附加信息，这是使用 Java 编写的。

谢谢

Answer 1

我过去和我的下一个项目都会遇到类似的情况。
我选择了简单的网格变体，因为它更简单，实现起来也更快。 数万处于四叉树或 k-d 树可能有意义的边界。 (尤其是当许多单元格为空时)

您应该尝试测试网格方法是否足够。可能是。