9 c optimization performance computational-geometry data-structures
我在高性能集群中从事理论化学工作,通常涉及分子动力学模拟.我的工作涉及的问题之一涉及N维(通常N = 2-5)超球的静态场,测试粒子可能碰撞.我正在寻找优化(读取:大修)我用来表示球体领域的数据结构,这样我就可以进行快速碰撞检测.目前,我使用一个死的简单指针数组指向N元结构(中心的每个坐标加倍)和最近邻居列表.我听说过oct和quad-trees,但是没有找到关于它们如何工作的明确解释,如何有效地实现它,或者如何用一个快速碰撞检测.鉴于我的模拟大小,内存(几乎)没有对象,但周期是.
四叉树是一种二维树，其中每个级别的节点有 4 个子节点，每个子节点覆盖父节点面积的 1/4。
Oct 树是一种 3 维树，其中每个级别的节点有 8 个子节点，每个子节点包含父节点体积的 1/8。这是帮助您可视化它的图片： http: //en.wikipedia.org/wiki/Octree
如果您正在进行 N 维交叉测试，您可以将其推广到 N 树。
相交算法的工作原理是从树的顶部开始，递归地遍历与正在测试的对象相交的任何子节点，在某个时刻，您会到达包含实际对象的叶节点。