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

解决方案

回答

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

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

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

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

回答

听起来我们好像想要实现一个kd树，这将使我们可以更快地搜索N维空间。在Stony Brook算法存储库中，有更多信息和实现的链接。

回答

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

回答

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

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

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

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

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

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

可以在Klinger＆Dyer {4}中找到有关划分空间以创建四叉树(可以将其概括为n-tree)的描述。

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

{1}使用AAC的Quadtrees Journal的Connected Component Labeling，Hanan Samet，第28卷，第3期(1981年7月)

{2}在以八叉树为代表的图像中发现邻居，哈南·沙美特，计算机视觉，图形学和图像处理，第46卷，第3期(1989年6月)

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

{4}使用常规分解(Klinger，A。和Dyer，C.R。E，Comptr。)进行图片表示的实验。图形与图像处理5(1976)，68-105.

回答

只要我们可以按球的中心指定球，八角就可以起作用，它将球按层次划分为具有八个子级的立方区域。计算八叉树数据结构中的邻居将需要我们进行球面相交多维数据集计算(在某种程度上要比它们看起来容易)来计算八叉树中哪些立方区域在球体内。

找到最近的邻居意味着向后走一棵树，直到找到一个节点，其中有一个以上的填充子节点，并且包括所有周围的节点(这样可以确保查询得到所有方面)。

从内存来看，这是球体-立方体相交的(有点天真)基本算法：

一世。是立方体内的中心(得到同义的情况)

ii。中心半径r内的立方体的任意一个角(球体内的角)是否在

iii。对于立方体的每个表面(可以通过计算出中心位于表面的哪一侧来消除某些表面)(这是第一年的矢量算法)：

一种。到达球体中心的表面的法线

b。从球体中心到法线与曲面平面的交点的距离(弦的交点位于立方体曲面的平面上)

C。平面的交点位于立方体的侧面内(弦与立方体相交的一种情况)

iv。计算弦的大小(法线长度与球体半径之比的Cos ^ -1的Sin)

v。如果直线上最接近的点小于弦的距离，并且该点位于直线的两端之间，则弦与立方体的一条边线相交(弦在其中一条边的某处与立方体表面相交)。

稍微有些模糊的记忆，但这是我针对使用八位字节数据结构的球形区域的情况所做的(很多年前)。我们可能还希望像其他一些海报所建议的那样查看KD树，但是我们最初的问题听起来与我所做的非常相似。