我正在执行一些涉及数百万个原子的系统的 MD 模拟。
我编写了一些代码来生成一个文件,该文件只是 XYZ 原子坐标的列表。现在我需要在原子之间生成键。如果两个原子彼此之间的距离在一定距离内,则被视为键。
XYZ 文件示例:
1 0 0
2 0 0
7 0 0
10 0 0
9 0 0
所以我有五个原子。如果我的距离阈值是 2 个单位,那么我的债券列表将是:
1 2
3 5
4 5
(其中数字对应于 XYZ 文件中坐标的索引)。
生成此列表的简单方法就是:
for i = 1:numAtoms
for j = i+1:numAtoms
if distance(atom[i], atom[j]) < 2
bonds.push [i, j]
然而,这很快就达到了算法限制,并且即使在针对数百万个原子高度优化的 C 语言中也很慢,至少对于我将执行此过程的频率来说是这样。
我对空间分区数据结构的唯一经验是当我编写光子映射器时使用 kd 树,所以我真的不知道这个问题的最佳解决方案是什么。我确信可能有一些最适合此目的的东西。
我还应该提到,我的模拟盒是周期性的,这意味着 (0.5, 0, 0) 处的原子将与 (boxWidth - 0.5, 0, 0) 处的原子键合,距离阈值例如为 2。