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

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

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


algorithm mesh particles
person Brian    schedule 02.03.2012    source источник
comment
Частицы имеют одинаковую массу, но разное положение. Они ограничены трехмерным объемом, скажем, кубом со стороной 1.   -  person Brian    schedule 02.03.2012

Ответы (2)


arrow_upward
1
arrow_downward

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

person Weeble    schedule 02.03.2012

arrow_upward
0
arrow_downward

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

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

person Roman    schedule 02.03.2012
comment
Это было бы полезно для вычисления плотности в каждой ячейке, но это не то, что мне нужно. Мне нужно знать в каждой ячейке идентификаторы частиц, принадлежащих этой ячейке. Глупым способом было бы сохранять эти идентификаторы в массиве, но это потребовало бы много памяти. Вот почему я придумал эту идею цепочки мешей. Если бы частицы были отсортированы по-умному, то в каждой ячейке нужно было бы хранить лишь несколько фрагментов информации, а не все идентификаторы частиц. - person Brian; 02.03.2012