Алгоритм проверки столкновения двух движущихся окружностей

Нужен оптимальный алгоритм определения столкновения двух движущихся окружностей. Окружности задаются координатами центров и радиусами. Движение задается углом и длинной вектора. При этом считается что обе окружности переместятся из начальной точки в конечную за одно и то-же время, т.е. скорости их движения зависят от длинны вектора.
Алгоритм "в лоб" который я сейчас использую:
Определяю количество итераций пути из расчета N = MAX(size1/r1, size2/r2) * 2 Разбиваю движение каждой окружности на N частей В цикле от 0 до N вычисляю положение каждой окружности и проверяю пересечение.
Алгоритм хорош всем кроме одного - это производительность. Может кто-то сталкивался с подобной задачей? Наверняка есть математическое описание этой модели.

Ответ

Представим ваши углы и длины по другому, а именно в координаты начальных и конечных точек. Окружности будут двигаться так:
(x11; y11) -> (x12; y12) (x21; y21) -> (x22; y22)
Введем параметр t (время), который изменяется от 0 до 1. При t=0 окружности находятся в исходных точках, при t=1 - в конечных. Тогда координаты центров окружностей во время движения будут:
x1 = x11 + (x12 - x11) * t y1 = y11 + (y12 - y11) * t
x2 = x21 + (x22 - x21) * t y2 = y21 + (y22 - y21) * t
В момент соприкосновения расстояние между центрами окружностей равно сумме радиусов. Получаем:
(r1 + r2)^2 = (x1 - x2)^2 + (y1 - y2)^2
Если подставить координаты точек в уравнение соприкосновения, получим огромное квадратное уравнение относительно t. Его коэффициенты такие:
a = x11 * x11 + x12 * x12 + y11 * y11 + y12 * y12 + x21 * x21 + x22 * x22 + y21 * y21 + y22 * y22 + 2 * (- x11 * x12 - x21 * x22 - y11 * y12 - y21 * y22 - x11 * x21 - y11 * y21 + x11 * x22 + y11 * y22 + x12 * x21 + y12 * y21 - x12 * x22 - y12 * y22); b = 2 * ( - x11 * x11 - x21 * x21 - y11 * y11 - y21 * y21 + x11 * x12 + y11 * y12 + x21 * x22 + y21 * y22 - x11 * x22 - y11 * y22 - x12 * x21 - y12 * y21 + 2 * x11 * x21 + 2 * y11 * y21) c = x11 * x11 - 2 * x11 * x21 + x21 * x21 + y11 * y11 - 2 * y11 * y21 + y21 * y21 - (r1 + r2) * (r1 + r2);
Как и любое квадратное уравнение, оно может иметь 0 решений (окружности не пересекаются), бесконечность решений (окружности скользят по параллельных отрезках), 2 решения (окружности соприкасаются, пересекаются, и расходятся), 1 решение (окружности касаются только один раз).
Плюс к этому нужно проверить, входит ли t в промежуток 0..1
Пример:
(-5; -10) -> (3; 10) [r1 = 1] (-10; -1) -> (10; -10) [r2 = 1]
Решения:
t1 = 0.274411137729595 t2 = 0.377365512016598
Координаты окружностей в момент пересечения:
(-2.805; -4.512) (-4.512; -3.470)