Найдите лучшее пересечение двух движущихся объектов

Ответ 1

Без ограничения общности, пусть O2 находится в точке (0,0).

Пусть s и v местоположение и скорость векторов O1, v2 скорость O2, t - время перехвата. Тогда имеем:

|s + v * t| = t * v2

По определению расстояния:

(sx + vx * t) ^ 2 + (sy + vy * t) ^ 2 = (t * v2) ^ 2

Умножение этого параметра и условия переупорядочения дают:

  sx^ 2 + 2 * sx * vx * t + vx^2 * t^2
+ sy^ 2 + 2 * sy * vy * t + vy^2 * t^2
-                           v2^2 * t^2
= 0

то есть.

  sx^2 + sy^2 + (2 * sx * vx + 2 * sy * vy) * t + (vx^2 + vy^2 - v2^2) * t^2 = 0
  \---   ---/   \------------   ----------/       \--------   ------/
      \ /                    \ /                           \ /
       c                      b                             a

Как вы можете видеть, это квадратичное уравнение по t. Мы можем просто применить квадратичную формулу чтобы найти два возможных значения для t (если уравнение не имеет решения, потому что перехват невозможен). Вероятно, вы захотите использовать самый ранний будущий перехват, т.е. Меньший t, который равен > 0.

Как только вы вычислили t, найдя точку перехвата, и из-за этого направление перехвата должно быть легким.

Подводя итог, эта проблема может быть решена в постоянное время, итерация не требуется.

Ответ 2

Вы, кажется, слишком задумываетесь о проблеме, это просто простая геометрия.

Оставив в стороне проблему определения ближайшей точки, разрешите для ситуации, когда желаемая точка находится на полпути между PA и PB.

Мы должны принять период времени для всего цикла, назовем это T.

PI = (PB - PA) / 2;  // simplified
TI = T / 2;          // simplified

[разложите все формулы для координат x и y отдельно].

Существуют относительно простые формулы для определения ближайшего пересечения точки (ПК) с линией (PA → PB), хотя, как это определено, сложно, когда эта линия не бесконечно длинна.

Тогда вам нужно:

V1 = (PB - PA) / T;  // O1 velocity
V2 = (PI - PC) / T;  // O2 velocity

Эти последние две строки не зависят от более ранних предположений - если вы знаете точку перехвата, тогда скорость - это просто пройденное расстояние, деленное на время.

Следовательно, если вы не наложите некоторые дополнительные ограничения на V2, всегда есть решение и оно вычисляется в нескольких тривиальных математических операциях.

Ответ 3

Обновление: более поздний ответ @Meriton лучше моего. Я рекомендую попробовать его первый.

Как вы понимаете, у нас есть три одновременных уравнения в трех неизвестных vx2, vy2 и t - соответственно скорости x и y в 02 и время. Уравнения, к сожалению, не все линейны:

x1o + vx1*t == x2o + vx2*t
y1o + vy1*t == y2o + vy2*t
vx2*vx2 + vy2*vy2 == vy*vy

(Здесь x1o, y1o, x2o и y2o - координаты начальных положений.)

Если есть способ линеаризации проблемы, я ее не вижу. Тем не менее вы можете решить итеративно и быстро, тем же методом Newton-Raphson GPS использует, чтобы выработать свою позицию со спутниковых сигналов. Конечно, чтобы заполнить детали и реализовать это потребует некоторой работы!

Обновление: я думаю, что @Alnitak, возможно, линеаризует вашу проблему довольно аккуратно. Возможно, комбинация его подхода и моего успеха будет процветать. (Я все еще думаю, что вы захотите использовать итерацию Ньютона-Рафсона для слияния на @Altinak T.)

Ответ 4

Поскольку скорости фиксированы, это должно быть разрешено с использованием идеи параллельной навигации. Подумайте об этом так. В момент времени 0 существует линия между O1 и O2 (LOS или линия визирования). Если O2 следует оптимальному пути пересечения, то в момент времени 1 линия между O1 и O2 будет параллельна времени 0 LOS. Поскольку у вас есть скорость O2, вы можете рассчитать расстояние, которое оно будет перемещаться между временем 0 и временем 1, и из этого можно рассчитать, где это пересекает время 1 LOS. Подумайте о том, чтобы нарисовать круг вокруг исходного положения O2 с радиусом, равным расстоянию, которое он будет перемещать в этот промежуток времени. Пересечение этого круга со вторым LOS будет содержать решение. Если пересечения нет, решения нет. В начале этой онлайн-книги есть диаграмма и формулы, которые показывают концепцию:

http://www.crcnetbase.com/doi/abs/10.1201/9781420062281.ch2

Эта проблема имеет приложения реального мира, где вы также можете найти это решение. Например, подводные лодки могут использовать это для построения и поддержания курса перехвата со своей целью, сохраняя при этом LOS с постоянной мишенью по мере приближения к цели.

Edit:

Эта диаграмма показывает, о чем я говорю. Это можно решить с помощью тригонометрии, за исключением особого случая, когда цель O1 движется непосредственно к ракете O2 (или ее удалению тривиально) и/или удаляется.

На приведенной выше диаграмме мы можем взять некоторое произвольное небольшое количество времени. В течение этого времени t1, O1 будет пройденным расстоянием b, а O2 будет пройденным расстоянием f. Линия между O1 и O2 в момент времени t0 параллельна линии между O1 и O2 в момент времени t1. Поскольку нам даны начальные положения O1 и O2, мы знаем расстояние d, и поскольку нам дано направление O1, мы можем просто вычислить угол A.

So given A, b, f, and d, using the law of Cosines,
a = sqrroot(c^2 + b^2 - (2cb * cos(A)))
and
B = arccos((a^2 + c^2 - b^2)/2ac)
Using the law of Sines
E = arcsin((a * sin(B))/f)  or the ambiguous value of 180 - that value
and with that
BC = 180 - E   (because C = 180 - B - E so C+B = 180 - E

с BC мы имеем решение, и любые другие аспекты треугольника начальных местоположений O1 и O2 и точки пересечения могут быть вычислены аналогичным образом. Прошло много лет с тех пор, как я использовал свой триггер в средней школе, поэтому может быть упрощение этого, которое я пропустил, но, надеюсь, объясняет подход к решению, который я изначально описал.