我在高性能簇上从事理论化学工作，通常涉及分子动力学模拟。我的工作解决的问题之一涉及N维(通常为N = 2-5)超球的静态场，测试粒子可能会与之碰撞。我正在寻求优化(阅读:大修)我用来表示球体领域的数据结构，以便进行快速碰撞检测。当前，我使用了一个简单的指向N成员结构的指针简单数组(中心的每个坐标都加倍)和一个最近邻居列表。我听说过八叉树和四叉树，但是还没有找到关于它们如何工作，如何有效实现一个树或如何对一个树进行快速碰撞检测的清晰解释。考虑到我的模拟大小，内存(几乎)不是对象，而循环是对象。
最佳答案
如何最好地解决此问题取决于您尚未描述的几个因素:
-是否会将相同的超球面布置用于许多粒子碰撞计算？
-超球体的大小均匀吗？
-粒子的运动是什么(例如直线/曲线)，该运动受球体影响吗？
-您认为粒子的体积为零吗？
我假设粒子没有简单的直线运动，因为这将是找到一条线和一个点之间最接近的点的相对较快的计算，这很可能与找到该行中的哪个框的速度大致相同。与相交(确定要在n树中检查的位置)。
如果您的超球体位置在许多粒子碰撞中是固定的，那么计算voronoi decomposition/Dirichlet tessellation将为您提供一种快速的方式，以便稍后准确地找到空间中任何给定点哪个球体最接近您的粒子。
但是，要回答有关octrees/quadtrees/2 ^ n-trees的原始问题，在n维中，您将从一个( super )多维数据集开始，该多维数据集包含您感兴趣的空间区域。这将 segmentation 为2 ^ n个超多维数据集如果您认为内容过于复杂。递归地继续进行，直到叶节点中只有简单元素(例如一个超球质心)为止。
现在已经构建了n树，您可以通过获取粒子的路径并将其与外部超立方体相交来将其用于碰撞检测。相交位置将告诉您接下来要访问树的下一个层次中的哪个超立方体，并确定与该层上所有2 ^ n个超立方体的相交位置，然后向下直至到达叶节点。到达叶子后，您可以检查粒子路径与该叶子上存储的超球之间的相互作用。如果发生碰撞，则说明已经完成，否则，您必须从当前的超立方体叶子中找到粒子路径的导出点，并确定将其移至下一个 super 立方体。继续直到找到碰撞或完全离开整个边界超立方体。
退出超立方体时有效地找到相邻的超立方体是此方法最具挑战性的部分之一。对于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} Connected Component Labeling, Hanan Samet, Using Quadtrees Journal of the ACM Volume 28 , Issue 3 (July 1981)
{2} Neighbor finding in images represented by octrees, Hanan Samet, Computer Vision, Graphics, and Image Processing Volume 46 , Issue 3 (June 1989)
{3} Convex hull generation, connected component labelling, and minimum distancecalculation for set-theoretically defined models, Dan Pidcock, 2000
{4}使用常规分解，A。Klinger和C.R. E，Dyer，Comptr进行图片表示的实验。图形与图像处理5(1976)，68-105。