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

#коллизии

Нужен оптимальный алгоритм определения столкновения двух движущихся окружностей. 
Окружности задаются координатами центров и радиусами. Движение задается углом и длинной
вектора. При этом считается что обе окружности переместятся из начальной точки в конечную
за одно и то-же время, т.е. скорости их движения зависят от длинны вектора. 

Алгоритм "в лоб" который я сейчас использую:


Определяю количество итераций пути из расчета N = MAX(size1/r1, size2/r2) * 2
Разбиваю движение каждой окружности на N частей
В цикле от 0 до N вычисляю положение каждой окружности и проверяю пересечение.


Алгоритм хорош всем кроме одного - это производительность.
Может кто-то сталкивался с подобной задачей? Наверняка есть математическое описание
этой модели.
    

Ответы

Ответ 1

Представим ваши углы и длины по другому, а именно в координаты начальных и конечных
точек. Окружности будут двигаться так:

(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)


Ответ 2

Упрощённая запись формул:

Заданы два тела


A (Xa;Ya; скорость Va[x,y], радиус ra) 
B (Xb;Yb; скорость Vb[x,y], радиус rb):


Тогда:

dVx = Vax - Vbx
dVy = Vay - Vby

dx = Xa - Xb
dy = Ya - Yb

R = ra + rb

# Коэффициенты уравнения:

a = dVx^2 + dVy^2
b = 2*(dx*dVx + dy*dVy)
c = dx^2 + dy^2 - R^2


ЗЫ: выводил на коленке, так что за абсолютную достоверность не ручаюсь.

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

Нужен оптимальный алгоритм определения столкновения двух движущихся окружностей. Окружности задаются координатами центров и радиусами. Движение задается углом и длинной вектора. При этом считается что обе окружности переместятся из начальной точки в конечную за одно и то-же время, т.е. скорости их движения зависят от длинны вектора.
Алгоритм "в лоб" который я сейчас использую:
Определяю количество итераций пути из расчета 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)