Пересечение двух движущихся отрезков (или движущегося отрезка и точки)

Question

Я пытаюсь создать физический движок 2D с непрерывным обнаружением столкновений Объекты хранятся в виде списка невращающихся отрезков. Поэтому я могу обнаруживать столкновения, находя время столкновения между каждой парой отрезков линии между любыми двумя объектами.

Я хочу найти точное время для пересечения двух движущихся отрезков, которые движутся в постоянном направлении, и это оказывается трудным.

Я понял, что могу еще больше упростить задачу, найдя время столкновения между каждой точкой на отрезке и другим отрезком (и наоборот). Вполне возможно, что это неэффективно в вычислительном отношении, поэтому общее решение для двух отрезков будет идеальным ответом. Я также могу игнорировать случай, когда линии параллельны (я хочу трактовать линию / точку с одинаковым положением и скоростью как «без столкновения»).

Если ответ «невозможно», чтобы точно нашел это время пересечения, я бы принял его как решение. Буду признателен за любую помощь по этому вопросу.

РЕДАКТИРОВАТЬ : Согласно статье Википедии о отрезке , для отрезка с конечными точками A = (a_x, a_y) и C = (c_x, c_y) общее уравнение для отрезка выглядит следующим образом :

Для отрезка прямой - точка пересечения, заменяющего

• p_x + p_v * t для a_x (только левая сторона, правая сторона просто p_x)
• p_y + p_v * t для a_y (только слева, справа только p_y)
• q_x + q_v * t для c_x (только левая сторона, правая сторона просто q_x)
• q_y + q_v * t для c_y (только левая сторона, правая сторона просто q_y)
• r_x + r_v * t для x
• r_y + r_v * t для y

для отрезка линии pq [(p_x, p_y), (q_x, q_y)], точка r (r_x, r_y), движущаяся со скоростью p_v == q_v! = r_v, разрешима для t? Вот полное уравнение:

Answer 1

Уравнение, приведенное выше, неверно в том смысле, что оно использует одинаковую скорость для обоих компонентов x и y.

Поскольку скорость постоянна, я могу упростить уравнение так, чтобы точка двигалась относительно отрезка. Количество переменных, используемых для скорости, значительно уменьшается, используя v = r_v - qp_v для скорости точки r и 0 для скорости каждого отрезка. Тогда уравнение с включенными переменными становится:

Благодаря WolframAlpha уравнение затем решается для t:

Что интересно, если вы проанализируете это, оно будет симметричным для 3D. Перекрестное произведение для [x1, y1, 0] и [x2, y2, 0] равно [0, 0, x1*y2 - y1*x2]. Это уравнение затем переводит в:

Answer 2

Для пересечения отрезок линия - точка я могу найти интервал, в котором происходит столкновение (хотя этот интервал больше, чем фактическое время для столкновения):

Для данного отрезка [p, q], движущегося со скоростью v, и для точки r со скоростью w, direction(w) != direction(v), определите три линии L1 = [p, p+v], L2 = [q, q+v], L3 = [r, r+w]. Пусть t1, t_p и t2, t_q будут временами пересечения между L1 и L3 и между L2 и L3 соответственно. Если интервал [t1, t2] не является взаимоисключающим с [t_p, t_q], то существует пересечение в пересечении этих двух интервалов (например, пересечение между [-1, 10] и [2, 20] равно [2, 10]). Если эти интервалы являются взаимоисключающими, то столкновения нет.

Кроме того, если направления v и w одинаковы, но не имеют одинаковую длину, то вы можете найти точное время столкновения. Пусть s будет точкой r при проецировании на линию [p, q]. Если эта точка находится в отрезке [p, q], в момент времени t1 происходит столкновение, которое можно рассчитать путем деления расстояния между точкой r и точкой s на относительную скорость между точкой r и отрезок [p, q].

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