Алгоритмы обнаружения столкновений между выпуклыми многоугольниками произвольного размера
Я работаю над клоном астероидов. Все 2D и написано на C ++.
Для астероидов я генерирую случайные N-сторонние многоугольники. Я гарантировал, что они выпуклые. Затем я поворачиваю их, увеличиваю их скорость и заставляю их летать в космосе. Все работает и очень красиво.
Для столкновения я использую алгоритм, который я думал о себе. Вероятно, это плохая идея, и если толчок придет к толчку, я, вероятно, откажусь от всего этого и найду учебник в Интернете.
Я написал и реализовал все, и обнаружение столкновений работает хорошо … большую часть времени. Он случайным образом потерпит неудачу, когда на экране явно будет столкновение, и иногда будет указывать на столкновение, когда ничто не касается. Либо я где-то провалил свою реализацию, либо мой алгоритм ужасен. Из-за размера / масштаба моей реализации (более чем из нескольких исходных файлов) я не хотел беспокоить вас этим, а просто хотел, чтобы кто-то проверил, что мой алгоритм действительно работает. В этот момент я могу пойти на большую ошибку охоты.
Алгоритм:
Для каждого астероида у меня есть функция, которая выводит, где должна быть каждая вершина при рисовании астероида. Для каждой пары смежных вершин я генерирую формулу для линии, на которой они сидят, y=mx+b формат. Затем я начинаю с вершины одного из моих кораблей, проверяя эту точку, чтобы увидеть, находится ли она внутри астероида. Я начинаю с подключения координаты X точки и сравниваю результат с фактическим значением Y. Это говорит мне, находится ли точка выше или ниже линии. Затем я делаю то же самое с Центром Астероида, чтобы определить, какая половина линии считается «Внутри» астероида. Затем я повторяю для каждой пары вершин. Если я когда-нибудь найду линию, для которой моя точка не находится на той же стороне, что и центр астероида, я знаю, что столкновения нет, и обнаружение выхода для этой точки. Поскольку на моем корабле 3 очка, мне нужно проверить следующее. Если все 3 точки уходят рано, то нет никаких столкновений ни для одной из точек на корабле, и мы закончили. Если какая-либо точка ограничена со всех сторон линиями, образованными астероидом, то она находится внутри астероида, и устанавливается флаг столкновения.
Две проблемы, которые я обнаружил с помощью этого алгоритма:
- он не работает на вогнутых многоугольниках, и
- У него проблемы с краем, когда уклон не определен.
Я удостоверился, что все многоугольники являются выпуклыми, и написал код для решения проблемы неопределенного уклона NAN если мы разделим на 0так что проверить это довольно легко).
Так должно ли это работать?
Решение
Я сделал что-то похожее на вычисление пересечений полигонов, а именно нахождение вершины внутри данного многоугольника.
Ваш алгоритм здравый, и действительно не работает для вогнутых полисов. Выбранное вами линейное представление также проблематично на склонах, приближающихся к бесконечности. Я решил использовать пару векторов для моего, один для направления линии и один для контрольной точки на линии. Из них я могу легко вывести параметризованное уравнение линии и использовать его различными способами для нахождения пересечений с другими фигурами.
P = S + t * D
Любая точка P линии может быть охарактеризована ее координатой t на линии, учитывая вышеуказанное соотношение, где S — опорная точка, а D — вектор направления.
Это представление позволяет легко определить, какие части плоскости являются положительными и отрицательными (т. Е. Выше и ниже линии), благодаря ориентации направления. Теперь любую область плоскости можно определить как пересечение отрицательных или положительных подпланов нескольких линий. Таким образом, ваш алгоритм «точка в многоугольнике» может быть немного изменен, чтобы использовать это представление с добавленным ограничением для всех направлений, указывающих по часовой стрелке, и проверкой точки, находящейся в отрицательной подплоскости всех линий (поэтому вам не нужно центр многоугольника больше).
Формула для вычисления стороны точки по линии, которую я использовал, следующая:
(xs - xp) * yd - (ys - yp) * xd
Проблема наклона возникает здесь, когда точка P близка к S.
Это представление может быть вычислено с использованием вершин ребер, но для того, чтобы иметь правильные подплоскости, вы должны хранить вершины в многоугольнике в последовательных порядках.
Для вогнутых многоугольников проблема немного сложнее: вкратце, вы должны проверить, что точка находится между двумя последовательными выпуклыми ребрами. Этого можно достичь, проверив координаты точки на краю при проецировании на нее и убедившись, что она стоит между 0 а также length(edge) (при условии, что направление нормализовано). Обратите внимание, что это сводится к тому, чтобы проверить, принадлежит ли точка треугольнику внутри многоугольника.
Другие решения
Стандартным решением этой проблемы является использование теоремы о разделительной оси (SAT). Учитывая два выпуклых многоугольника, A и B, алгоритм в основном выглядит так:
for each normal N of the edges of A and B
intervalA = [min, max] of projecting A on N
intervalB = [min, max] of projecting B on N
if intervalA doesn't overlap intervalB
return did not collide
return collided