Разбиение пространства на «блоки», обоснование разбиения, описание алгоритма

Введем прямоугольную пространственную сетку с шагом . Разобьем пространство на кубические «блоки»:

, – и введем нумерацию блоков: .

Будем рассматривать кластер из сферических частиц с центрами и радиусами ( ).

Утверждение. Тогда для баллистической траектории сферической частицы радиуса , проходящей через точку , с направлением ( ):

,

точка «прилипания» сферической частицы будет принадлежать одному из блоков , для которых выполнено . Обозначим множество таких блоков с номером за

Опираясь на это утверждение, можно предложить следующий алгоритм определения точки «прилипания» i-ой сферической частиц:

1. Для каждого блока определить множество частиц , где .

2. Для каждого и для каждого определить точку «прилипания» к j-ой сфере, как если бы других частиц не было. Полученное множество возможных точек «прилипания» обозначим за .

3. Вычислить реальную точку «прилипания» по формуле .

При увеличении параметра , отношение среднего количества сфер, лежащих одновременно в нескольких блоках, к среднему (среднего по блокам) количеству сфер, полностью содержащихся в блоке, сокращается. В то время, как количество блоков, принадлежащих , сокращается при уменьшении параметра .

Хотя такой алгоритм и приводит к тому, что точка «прилипания» к одной и той же сфере может быть рассчитана несколько раз, при правильном подборе параметров алгоритм дает существенное сокращение объемов вычислений.

□