Вот простое решение, предполагающее растеризованную настройку и то, что столкновения (между частицами или частицами со стенками) не изменяют направление и скорость частиц. Основная идея состоит в том, чтобы «раскрасить» траектории частиц в растр размером w x h.
allocate a raster of size w*h, each pixel being able to keep a list of (time,particle_id) tuples
for each particle pa
for each pixel pi on the direction of pa
store the tuple (time_of_pa_at_pi, pa_id) in the list of pi
for each pixel pi in the raster
check for collisions inside the list of pi by ordering the tuples by time
Наихудший сценарий довольно сложно описать, но верхняя граница производительности — O(n*max(w,h)) + O(wh) + max(w,h)*O(n*logn). Наихудший сценарий (сценарии), вероятно, имеет место, когда все частицы (или большая их часть) движутся в одном направлении. Это крайне маловероятно, если предположить равномерное случайное распределение всех входных параметров. Предполагая, что в среднем сценарии производительность должна быть намного лучше.
Кроме того (но это, вероятно, важная часть этого ответа), вы можете получить ускорение, если сначала выделите меньший растр (например, размером w/c x h/c) и запустите проверку вероятного столкновения таким же образом, как указано выше. Пиксели в этом растре больше, поэтому шаг вероятного столкновения занимает меньше времени. В конце этого шага вы получаете представление о том, что может произойти в каждом макроскопическом пикселе, а затем продолжаете свое исследование локально (рекурсивным способом или с использованием какой-либо другой техники). c выше может быть константой или некоторой функцией w, h и n (например, c=sqrt(max(w,h))).
Конечно, все вышеперечисленное бесполезно, если w и/или h неудобно велики.
person
cobarzan
schedule
21.02.2016
