Алгоритм определения того, будут ли сталкиваться 2 объекта на 2D плоскости

Question

Я пытаюсь определить, столкнется ли Object1 с Object2, учитывая следующую информацию:

1) Ограничивающие прямоугольники объектов (использует обнаружение столкновений с ограниченным кругом)

2) Объекты 'скорости

3) Текущее местоположение объекта (координаты x, y)

4) Направления объектов (вверх, вниз, влево или вправо)

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

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

Answer 1

Сначала найдите интервал времени, в течение которого блоки будут перекрываться по оси X. Во-вторых, найдите интервал времени, в течение которого блоки будут перекрываться по оси Y. Наконец, проверьте, перекрываются ли два временных интервала. Если это так, то самый ранний момент времени, который находится в обоих интервалах, - это момент, когда они столкнутся.

Answer 2

То, что вы ищете, называется «Тест разделения осей для перемещения выпуклых объектов».

Вот ссылка на книги Google, которая объясняет детали:

http://books.google.de/books?id=WGpL6Sk9qNAC&pg=PA219&lpg=PA219&dq=separating+axis+test+movement&source=bl&ots=Pl5MmM1bfQ&sig=_1VXYm5WFaV9AFj0ws63SAPtjck&hl=de&ei=coVVTML3BtGVOI26oJ8O&sa=X&oi=book_result&ct=result&resnum=3&ved=0CCIQ6AEwAg#v=onepage&q=separating%20axis%20test%20movement&f=false

(извините за большую ссылку - это была не моя идея)

Answer 3

Ваш лучший подход - выработать:

1. Линейный диапазон времени (возможно, никогда), в котором координаты x будут перекрываться
2. Линейный временной диапазон (возможно, никогда), в котором координаты y будут перекрываться

А затем проверьте, пересекаются ли два временных диапазона. Это как дополнительный бонус даст вам время столкновения.

В целом это будет простая операция с постоянным временем.