c - C 中的空间数据结构

Question

我确实在高性能集群上从事理论化学工作，通常涉及分子动力学模拟。我的工作解决的问题之一涉及 N 维（通常 N = 2-5）超​​球体的静态场，测试粒子可能会与之发生碰撞。我正在寻找优化（阅读：大修）用于表示球体领域的数据结构，以便我可以进行快速碰撞检测。目前，我使用一个简单的指针数组，指向一个 N 成员结构（中心的每个坐标双精度）和一个最近邻列表。我听说过八叉树和四叉树，但还没有清楚地解释它们是如何工作的，如何有效地实现它们，或者如何使用它们进行快速碰撞检测。考虑到我模拟的大小，内存（几乎）不是对象，但循环是。

Answer 1

如何最好地解决您的问题取决于您未描述的几个因素： - 相同的超球面排列是否会用于许多粒子碰撞计算？- 超球体的大小是否一致？- 粒子的运动是什么（例如直线/曲线），运动是否受到球体的影响？- 你认为粒子的体积为零吗？

我假设粒子没有简单的直线运动，因为这将是找到一条线和一个点之间最近点的相对快速的计算，这可能与找到线中哪个框的速度大致相同相交（以确定要检查的 n-tree 中的哪个位置）。

如果您的超球体位置对于大量粒子碰撞是固定的，那么计算voronoi 分解/Dirichlet 细分将为您提供一种快速的方法，以便您稍后准确地找到对于空间中的任何给定点哪个球体最接近您的粒子。

然而，要回答关于八叉树/四叉树/2^n-trees 的原始问题，在 n 维中，您从包含您感兴趣的空间区域的（超）立方体开始。这将被细分为 2^n 超立方体如果您认为内容过于复杂。这会递归地继续，直到叶节点中只有简单的元素（例如一个超球体质心）。现在已经构建了 n-tree，您可以通过获取粒子的路径并将其与外部超立方体相交来使用它进行碰撞检测。交点位置将告诉您接下来要访问树的下一层中的哪个超立方体，并且您确定与该级别的所有 2^n 个超立方体的交点位置，向下直到到达叶节点。到达叶子后，您可以检查粒子路径与存储在该叶子上的超球体之间的相互作用。如果你有碰撞你已经完成了，否则你必须从当前超立方体叶子中找到粒子路径的出口点，并确定它接下来移动到哪个超立方体。继续直到发现碰撞或完全离开整个边界超立方体。

在退出超立方体时有效地找到相邻的超立方体是这种方法中最具挑战性的部分之一。对于 2^n 树，可以采用 Samet 的方法 {1, 2}。对于 kd-trees（二叉树），{3} 第 4.3.3 节建议了一种方法。

有效的实现可以很简单，例如存储从每个超立方体到其子超立方体的 8 个指针的列表，如果超立方体是叶，则以特殊方式标记它（例如，使所有指针为 NULL）。

可以在 Klinger & Dyer {4} 中找到划分空间以创建四叉树（您可以将其推广到 n-tree）的描述

正如其他人提到的那样，kd-trees 可能比 2^n-trees 更适合，因为扩展到任意数量的维度更直接，但是它们会产生更深的树。调整分割位置以将超球体的几何形状与 kd-tree 匹配也更容易。上面对 2^n 树中的碰撞检测的描述同样适用于 kd-tree。

{1} Connected Component Labeling, Hanan Samet, Using Quadtrees Journal of ACM 第 28 卷，第 3 期（1981 年 7 月）

{2}在 octrees 表示的图像中寻找邻居，Hanan Samet，计算机视觉、图形和图像处理第 46 卷，第 3 期（1989 年 6 月）

{3}集理论定义模型的凸包生成、连接组件标记和最小距离计算，Dan Pidcock，2000

{4} 使用正则分解的图片表示实验，Klinger, A., and Dyer, CR E, Comptr。图形和图像处理 5 (1976), 68-105。

Answer 2

听起来您想要实现一个kd-tree，它可以让您更快地搜索 N 维空间。在Stony Brook Algorithm Repository有更多信息和实现链接。

Answer 3

由于您的领域是静态的（我假设您的意思是超球体不移动），所以我所知道的最快的解决方案是 Kdtree。
你可以自己做，也可以用别人的，比如这个： http: //libkdtree.alioth.debian.org/

Answer 4

四叉树是一棵二维树，其中每一层有一个节点有 4 个子节点，每个子节点占父节点面积的 1/4。

Oct 树是一棵 3 维树，其中每一层有一个节点有 8 个子节点，每个子节点包含父节点体积的 1/8。这是帮助您将其可视化的图片：http ://en.wikipedia.org/wiki/Octree

如果您正在进行 N 维交叉测试，您可以将其推广到 N 树。

相交算法的工作原理是从树的顶部开始并递归地遍历与正在测试的对象相交的任何子节点，在某些时候您会到达包含实际对象的叶节点。

Answer 5

只要您可以通过球体的中心指定球体，八叉树就可以工作 - 它将点分层分类为具有八个孩子的立方区域。计算八叉树数据结构中的邻居将需要您进行球体相交立方体计算（在某种程度上比他们看起来更容易）来计算出八叉树中的哪些立方体区域在球体内。

找到最近的邻居意味着沿着树往回走，直到你得到一个节点，其中包含多个填充的子节点和所有周围的节点（这确保了查询得到所有方面）。

从记忆中，这是球体 - 立方体相交的（有点天真）基本算法：

一世。是立方体内的中心（这得到了同名的情况）

ii. 立方体的任何角是否在中心半径 r 内（球内的角）

iii. 对于立方体的每个表面（您可以通过计算中心位于表面的哪一侧来消除一些表面）计算（这都是第一年的向量算术）：

一个。指向球体中心的曲面法线

湾。从球体中心到法线与曲面平面交点的距离（弦与立方体曲面相交）

C。平面的交点位于立方体的边内（弦与立方体相交的一个条件）

iv. 计算弦的大小（Sin of Cos^-1 of ratio of normal length to sphere of sphere）

v. 如果线上最近的点小于弦的距离并且该点位于线的两端之间，则弦与立方体的其中一条边相交（弦与立方体表面沿其中一条边相交）。

记得有点模糊，但这是我为使用八角形数据结构（多年前）涉及球形区域的情况所做的事情。您可能还希望按照其他一些海报的建议查看 KD-trees，但您最初的问题听起来与我所做的非常相似。