关于性能：C语言中的空间数据结构

Spatial Data Structures in C

我在高性能簇上从事理论化学工作，通常涉及分子动力学模拟。我的工作解决的问题之一涉及N维(通常为N = 2-5)超??球的静态场，测试粒子可能会与之碰撞。我正在寻求优化(阅读：大修)我用来表示球体场的数据结构，以便进行快速碰撞检测。目前，我使用了一个简单的指向N元成员结构的指针简单数组(中心的每个坐标都加倍)和一个最近邻居列表。我听说过八叉树和四叉树，但是没有找到关于它们如何工作，如何有效地实现它们或如何对其中一个进行快速冲突检测的清晰解释。鉴于我的仿真大小，内存(几乎)不是对象，而周期是。

如何最好地解决此问题取决于您尚未描述的几个因素：
-是否会将相同的超球面布置用于许多粒子碰撞计算？
-超球体的大小均匀吗？
-粒子的运动是什么(例如直线/曲线)，该运动受球体影响吗？
-您认为粒子的体积为零吗？

我假设粒子不具有简单的直线运动，因为这将是找到一条线和一个点之间最接近点的相对较快的计算，这很可能与找到哪个点之间的速度大致相同。框线与之相交(确定要在n树中检查的位置)。

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

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

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

高效的实现可能很简单，例如存储从每个超多维数据集到其子超多维数据集的8个指针的列表，并在超多维数据集是叶子的情况下以特殊方式对其进行标记(例如，使所有指针为NULL)。

在克林格(Klinger)中找到有关划分空间以创建四叉树(您可以将其推广为n-tree)的描述。

由于您的字段是静态的(我假设您的意思是超球不动)，所以我知道的最快的解决方案是Kdtree。
您可以自己制作，也可以使用别人的，就像这样：
http://libkdtree.alioth.debian.org/

听起来您想实现一个kd-tree，它可以让您更快地搜索N维空间。在Stony Brook算法存储库中，有更多信息和实现的链接。

四叉树是二维树，其中每个节点上有4个子节点，每个子节点覆盖父节点面积的1/4。

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

如果您要进行N维交集测试，则可以将其推广为N树。

交集算法的工作方式是从树的顶部开始，然后递归地遍历与要测试的对象相交的任何子节点，有时您会到达包含实际对象的叶节点。