在网格上存储粒子位置的算法(链式网格)

Question

我有一个粒子分布，即一组3D数组x，y和z，它们给出了N个粒子的位置。我将我的域划分为细胞，我想编写一个算法，它可以告诉我一个细胞中有多少粒子。我在找不占用太多内存的东西。如果粒子的分布是一维的，一个聪明的想法是对x递减的粒子进行排序。这样，我们只需要为每个细胞保存该细胞内具有较小x的粒子。例如，我知道第7个粒子是属于细胞i的x较小的粒子。因此，在单元格i中，我们必须找到粒子0到7。

我的问题是:我如何将其扩展到3D？或者，我如何构建一个链式网格？

Answer 1

这不是一个微不足道的问题。您可能希望了解一下R-trees，甚至是一般的Spatial databases。

Answer 2

我认为你的问题可以解决得容易得多。

创建一个“cell”的3D数组。循环遍历粒子和当前粒子所属单元格的增量值。

示例代码：

cells = int[X][Y][Z]
for p in particles:
   cx = cast_to_int((p.x / maxX) * X)
   cy = cast_to_int((p.y / maxY) * Y)
   cz = cast_to_int((p.z / maxZ) * Z)
   cells[cx][cy][cz]++ 

更新:仅当所有单元格具有相同的对应大小(即x1 = x2 = xn，y1 = y2 = yn...)时才有效。