我需要一个引擎，由一个充满了轴对齐包围盒（AABBs）的世界。将执行连续循环，执行以下操作：
for box_a in world
box_a = do_something(box_a)
for box_b in world
if (box_a!=box_b and collides(box_a, box_b))
collide(box_a, box_b)
collide(box_b, box_a)
问题是，很明显，这是O（n^2）我已经设法使这个循环更快地将空间分成块，所以这变成了：
for box_a in world
box_a = do_something(box_a)
for chunk in box_a.neighbor_chunks
for box_b in chunk
if (box_a!=box_b and collides(box_a, box_b))
collide(box_a, box_b)
collide(box_b, box_a)
这要快得多，但有点粗糙考虑到有这么一个快速的算法，不需要太多的努力，我敢打赌，有一个数据结构，我不知道，这概括了我在这里所做的，为这个算法提供更好的可伸缩性。
所以，我的问题是：这个问题的名称是什么？实现它的最佳算法和数据结构是什么？
最佳答案
这确实是计算机科学的一个普遍问题：空间分割。
它用于光线跟踪、路径跟踪、光栅渲染、物理、IA、游戏，在HPC、数据库、矩阵数学、任何科学（分子、制药等）中都非常可靠，我敢打赌还有成千上万的其他东西。
没有1 best结构，我有一个朋友，他精通一种算法，将激光扫描仪（数十亿数据）中的一个云点镶嵌起来，在他的例子中，最好的数据结构是将一组统一的三维网格与一些八叉树混合起来。
对于其他人来说kd树是最好的，对于其他人来说，bvh树是最好的。
我喜欢网格系统，但如果空间太宽，它不能工作，因为所有的细胞都必须存在。
有一天，我甚至用散列映射实现了一个稀疏的网格系统，它工作了，我没有费心去分析或调查性能，所以我不知道这是不是一个很好的方法，但我知道这是唯一的方法。
要做到这一点，您需要创建一个键类，它基本上是一个3D位置向量散列器，首先在坐标上应用整数除法来定义一个网格单元的大小然后你愚蠢地将所有坐标散列成一个散列，并提供一个散列值方法或友元方法一个相等运算符，然后它可以在哈希映射中使用。
您可以使用google::sparse_map或类似的语句。我个人使用boost::unordered，这对我来说已经足够了。
那么需要考虑的是aabb是否存在于多个细胞中。你可以在aabb覆盖的每个单元格中存储一个引用，在每个算法中都需要注意：“单元格引用和aabb之间没有1-1的关系。”仅此而已。
祝你好运