Algorithm to store particle position on a grid (Chaining mesh)

Question

I have a particle distribution, i.e. a set of 3D array x,y and z that give the positions of N particles. I divide my domain into cells and I would like to program an algorithm which gives me how many particles I have in a cell. I am looking for something that doesn't use too much memory. If the distribution of particles were mono-dimensional a smart idea is to sort the particles with decreasing x. In this way we only need to save, for every cell, the particle with smaller x within the cell. For example I know that the 7th particle is the particle with the smaller x that belong to cell i. Therefore, in cell i, we have to find particles 0 to 7.

My question is: how can I extend this to 3D? Or, how can I build a chaining mesh?

Answer 1

This is not a trivial problem. You might want to look at R-trees and indeed Spatial databases in general.

Answer 2

I think your problem can be solved much easier.

Make a 3D-array of 'cells'. Loop through your particles and increment value of a cell current particle belongs to.

Sample code:

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]++ 

UPD: works only if all cells have the same correspondent sizes (i.e. x1 = x2 = xn, y1 = y2 = yn...).