algorithm - 处理边界框内移动点接触和包含的数据结构？

Question

我在空间中有许多点随时间移动。它们在充满 AABB 边界框的空间中移动(包括嵌套边界框，BB 比点少)我想知道是否有一种数据结构可以帮助组织点进入边界框检测。

目前我想到了一个基于盒子中心的kd-tree来对点移动执行ANN，盒子相交/嵌套层次结构(谁在谁里面/在谁旁边)用于盒子检测。

但是对于这么多点来说这很慢所以我想知道是否有一些专门的算法/数据结构来处理这种情况？有办法同时查询多个点吗？

Answer 1

我建议使用某种四叉树。基本的四叉树在快速删除/插入方面已经相当不错了，但是还有一些特殊的变体，它们更好:

• Quadtree proposed by Samet et al使用重叠区域，允许移动对象在需要重新插入不同节点之前在同一节点中停留更长时间。
• PH-Tree作为技术上的“位级特里”。它基本上看起来像一个四叉树，但深度有限(64 位值是 64)，永远 没有重新插入/重新平衡，并且保证每次插入或删除最多修改两个节点。同时，节点大小受维数限制，因此对于 3D 点每个节点最多 8 个点，或者在存储点和矩形(框)时最多 64 个条目。对您的情况很重要:非常好的更新性能(优于 R 树或 KD 树)和非常好的窗口查询性能。当您查找与 AABB 重叠的点时，窗口查询将代表您的 AABB。此外，您还可以将 AABB 存储在树中，然后任何窗口查询都会返回所有点和与其重叠的其他 AABB(如果这对您有用的话)。

不幸的是，我不知道 Samet 四叉树的任何免费实现。对于 PH-Tree，您可以在上面给出的链接上找到 Java 版本和 C++ 版本 here .也可以看看我的index collection用于各种多维索引的 Java 实现。