Алгоритм сохранения положения частиц на сетке (Chain mesh)

Question

У меня есть распределение частиц, то есть набор трехмерных массивов x, y и z, которые задают положения N частиц.Я делю свой домен на ячейки и хочу запрограммировать алгоритм, который дает мне количество частиц в ячейке.Я ищу то, что не использует слишком много памяти.Если распределение частиц было одномерным, разумно было бы отсортировать частицы по убыванию x.Таким образом, нам нужно только сохранить для каждой ячейки частицу с меньшим x внутри ячейки.Например, я знаю, что седьмая частица - это частица с меньшим размером x, принадлежащая ячейке i.Поэтому в ячейке i мы должны найти частицы от 0 до 7.

Мой вопрос: как я могу распространить это на 3D?Или, как я могу построить цепочку?

Answer 1

Это не тривиальная проблема. Возможно, вы захотите взглянуть на R-деревья и даже Пространственные базы данных в целом.

Answer 2

Я думаю, что ваша проблема может быть решена намного проще.

Создайте 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]++ 

UPD : работает, только если все ячейки имеют одинаковый корреспондентразмеры (то есть x1 = x2 = xn, y1 = y2 = yn ...).