Время выполнения для алгоритма обнаружения столкновений

Question

Я придумал алгоритм для прогнозирования столкновения между двумя частицами. Учитывая прямоугольную среду (ширину w, высота h), и две частицы с известными исходными положениями и скоростями, он может определить

• ли не две частиц будут когда сталкиваются
• Если поэтому время, в которое последуют две частицы, будет сталкиваться

в конечном числе шагов, так сказать O(1). В дополнение, он может сделать это для n частиц в O(n^2). Есть ли что-то новое в этом подходе?

Я предполагаю, что частицы движутся линейно и с постоянной скоростью и занимают точки (так что столкновение было бы, когда две частицы занимают одну и ту же точку).

Благодарим за помощь.

Answer 1

Это очень легко сделать для n частиц в O (n^2), просто путем сравнения всех пар частиц и экстраполяции каждого сегмента, чтобы увидеть, где они сталкиваются.

Существуют более эффективные алгоритмы, основанные на идее индексирования ваших объектов в памяти с использованием чего-то вроде quadtree; Wikipedia article on collision detection имеет хороший обзор другого возможного подхода.

Answer 2

Это прямое решение, предполагающее растрированную установку и что столкновения (межчастичные или частичные стенки) не изменяют направление и скорость частиц. Основная идея - «нарисовать» траектории частиц в растре размера 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 неудобно большие.