Вы пытаетесь столкнуть движущийся выпуклый многоугольник (ваш "ромб") с другим движущимся выпуклым многоугольником, верно?Примерно так:
Ваш первый шаг должен состоять в том, чтобы преобразовать задачу в эквивалентный, в котором один из полигонов является стационарным:
Затем вы можете преобразовать движущийся многоугольник в «шахту», которая покрывает область, охватываемую движущимся многоугольником.Это легко сделать: если исходный многоугольник имеет n сторон, то вал имеет n + 2 стороны, причем дополнительные две стороны имеют ту же длину и направление, что и вектор движения,Вы найдете, куда вставить эти новые стороны, отсортировав вершины по их компоненту, ортогональному вектору движения, и вставив новые стороны в максимумах.
Теперь у вас естьсвел проблему к статическому многоугольнику против статического многоугольника.Взглянув на удобную таблицу алгоритмов столкновений , предоставленную realtimerendering.com, и, следуя ссылкам, мы увидим, что нам нужно использовать тест с разделительной осью , например, как описанов разделе 3 этой статьи Дэвида Эберли.
В двух измерениях два выпуклых многоугольника не пересекаются, если мы можем найти разделяющую ось , такую линию, чтоодин многоугольник падает с одной стороны линии, а другой многоугольник с другой:
Если нам дано направление, мы можем легко обнаружить, существует ли разделяющая оськоторый движется в этом направлении, проецируя два многоугольника на линию, проходящую перпендикулярно этому направлению, и проверяя, не являются ли проекции непересекающимися:
Как мы узнаем, какиеВ каком направлении будет двигаться разделительная ось?Хорошо, если существует любая разделяющая ось, то есть такая, которая проходит параллельно одной из сторон одного из выпуклых многоугольников (см. Eberly , стр. 3).Так что есть только небольшой набор направлений для проверки, и если вы проверили их все, не найдя разделяющей оси, то два многоугольника пересекаются (и, следовательно, исходные движущиеся объекты сталкиваются).
Есть многоУточнения и оптимизации, которые вы можете внести, конечно же, не ограничиваясь перечисленными:
- Перед выполнением полного теста на перемещение многоугольника / многоугольника сделайте более простой тест, такой как кружок / окружность, чтобы вы могли быстро отклонять простые случаи.
- Используйте какую-то схему пространственного разделения, например, квадродерево, чтобы проверять только те объекты, которые расположены достаточно близко, чтобы они могли столкнуться.
- "Кэширование свидетелей" - если линия разделяет два объекта одновременно t , вполне вероятно, что он продолжит их разделять во время t + δ, поэтому он может заплатить, чтобы запомнить найденную вами разделяющую ось и попробовать ее в первый раз в следующий раз (см. Rabbitz, " Быстрое обнаружение столкновения движущихся выпуклых многогранников"в Graphics Gems IV ).
Но не беспокойтесьСлишком много для оптимизации: сначала сделайте все правильно, если будете уверены, что сможете ускорить его позже.