#python #math #physics #pygame
#python #математика #физика #pygame
Вопрос:
Это то, чем я сейчас занимаюсь:
Создание 4 осей, которые перпендикулярны 4 краям 2 прямоугольников. Поскольку они представляют собой прямоугольники, мне не нужно генерировать ось (нормаль) для каждого ребра.
Затем я перебираю свои 4 оси.
Итак, для каждой оси: я получаю проекцию каждого угла прямоугольника на ось. Существует 2 списка (массива), содержащих эти проекции. По одному для каждого прямоугольника. Затем я получаю скалярное произведение каждой проекции на ось. Это возвращает скалярное значение, которое может быть использовано для определения минимального и максимального значений.
Теперь два списка содержат скаляры, а не векторы. Я сортирую списки, чтобы я мог легко выбирать минимальные и максимальные значения. Если min блока B > = max блока A Или max блока B <= min блока A, то на этой оси нет столкновения и нет столкновения между объектами.
На этом этапе функция завершается и цикл прерывается.
Если эти условия никогда не выполняются для всех осей, то мы имеем столкновение
Я надеюсь, что это был правильный способ сделать это.
Сам код Python можно найти здесь http://pastebin.com/vNFP3mAb
Проблема, с которой я столкнулся, заключается в том, что приведенный выше код не работает. Он всегда обнаруживает столкновение, даже если столкновения нет. То, что я напечатал, — это именно то, что делает код. Если я пропускаю какие-либо шаги или просто не понимаю, как работает SAT, пожалуйста, дайте мне знать.
Комментарии:
1. В чем вопрос?
2. Для более общих выпуклых многоугольников мы бы рассмотрели потенциальные оси разделения, которые параллельны краям обоих многоугольников, но поскольку вы конкретно имеете дело с прямоугольниками, в этом случае эквивалентно запрашивать оси, перпендикулярные (или нормальные) к краям.
3. Проблема, с которой я столкнулся, заключается в том, что приведенный выше код не работает. Он всегда обнаруживает столкновение, даже если столкновения нет. Извините, что не так понятно. Я отредактирую то, что я написал, чтобы это было более понятно.
4. @hardmath. Разделяющая линия будет параллельна краям. Разделяющая ось — это вектор направления, на который вы проецируете точку для тестирования, и она перпендикулярна краям полигонов. В 3d разделяющая ось перпендикулярна граням (т. Е. это нормаль к грани) или является перекрестным произведением ребер каждого объекта — опять же перпендикулярно ребрам.
5. @phkahler: Вы правы, разделяющая «гиперплоскость» соответствует нормальному направлению, и последняя «ось» имеет смысл как цель проекции. Уравнение «гиперплоскости» можно понимать как наложение на вектор направления вектора неизвестных, дающего некоторую константу, «нормальную форму» уравнения, если оно должным образом нормализовано.
Ответ №1:
В общем случае необходимо выполнить шаги, описанные в вопросе, чтобы определить, «сталкиваются» ли прямоугольники (пересекаются), отмечая при выполнении операции, что мы можем прерваться (с выводом о непересекании), как только будет найдена разделяющая ось.
Существует пара простых способов «оптимизации» в смысле предоставления шансов на более ранний выход. Практическая ценность этих методов зависит от распределения проверяемых прямоугольников, но оба они легко интегрируются в существующую структуру.
(1) Проверка ограничивающей окружности
Один из быстрых способов доказать непересечение — показать, что ограничивающие окружности двух прямоугольников не пересекаются. Ограничивающий круг прямоугольника разделяет его центр, середину любой диагонали, и имеет диаметр, равный длине любой диагонали. Если расстояние между двумя центрами превышает сумму радиусов двух окружностей, то окружности не пересекаются. Таким образом, прямоугольники также не могут пересекаться. Если целью было найти разделяющую ось, мы этого еще не достигли. Однако, если мы хотим только знать, «сталкиваются» ли прямоугольники, это позволяет выполнить ранний выход.
(2) Вершина одного прямоугольника внутри другого
Проекция вершины одного прямоугольника на оси, параллельные краям другого прямоугольника, предоставляет достаточно информации, чтобы определить, когда эта вершина находится внутри другого прямоугольника. Эта проверка особенно проста, когда последний прямоугольник был переведен и развернут к началу координат (с ребрами, параллельными обычным осям). Если случается, что вершина одного прямоугольника находится внутри другого, прямоугольники, очевидно, пересекаются. Конечно, это достаточное условие для пересечения, а не необходимое. Но это допускает ранний выход с завершением пересечения (и, конечно, без нахождения разделяющей оси, потому что ни одна из них не будет существовать).
Ответ №2:
Я вижу две неправильные вещи. Во-первых, проекция должна быть просто скалярным произведением вершины с осью. То, что вы делаете, слишком сложно. Во-вторых, способ получения вашей оси неверен. Вы пишете:
Axis1 = [ -(A_TR[0] - A_TL[0]),
A_TR[1] - A_TL[1] ]
Где это должно гласить:
Axis1 = [ -(A_TR[1] - A_TL[1]),
A_TR[0] - A_TL[0] ]
Разница в том, что координаты действительно дают вам вектор, но для получения перпендикуляра вам нужно поменять местами значения x и y и отрицать одно из них.
Надеюсь, это поможет.
РЕДАКТИРОВАТЬ Обнаружена еще одна ошибка
В этом коде:
if not ( B_Scalars[0] <= A_Scalars[3] or B_Scalars[3] >= A_Scalars[0] ):
#no overlap so no collision
return 0
Это должно гласить:
if not ( B_Scalars[3] <= A_Scalars[0] or A_Scalars[3] <= B_Scalars[0] ):
Сортировка дает вам список, значение которого увеличивается. Таким образом, [1,2,3,4] и [10,11,12,13] не перекрываются, потому что минимум более позднего больше максимума первого. Второе сравнение предназначено для случаев, когда входные наборы меняются местами.
Комментарии:
1. Спасибо за ответ, Пхалер. Как только у меня есть углы, спроецированные на ось, нужно найти 2 угла (на прямоугольник), которые являются самыми дальними в любом направлении? Это можно сделать, измерив длину между двумя координатами. Думаю, теперь я понимаю, как это работает. Я опубликую свое решение, когда оно заработает.
2. Что касается вещей «слишком сложных», мне не нравится способ представления прямоугольника. Нет ничего явного, представляющего угол поворота прямоугольника. Вместо этого представление выглядит как представление общего четырехугольника, то есть четырех точек, которые просто помечены «верхний левый», «верхний правый» и т.д. Результирующие восемь координат слишком общие, поэтому вам приходится полагаться на код, который их заполняет, чтобы получить их согласованными. Более строгое представление (центр, ширина, высота, угол поворота) могло бы обеспечить определение повернутого прямоугольника.
3. @hardmath: да, я согласен, что это общий четырехугольник, но его реализация SAT также вычисляет ось для всех 4 сторон, поэтому она должна работать до тех пор, пока они выпуклые.
4. @ Bruk Habtu: Вы все еще хотите искать минимальные и максимальные значения, как вы делаете. Не беспокойтесь о том, что точечные произведения подписаны или что ни одна конкретная вершина не равна нулю — все это относительно.
5. @phkahler Я последовал вашему совету. Но код по-прежнему обнаруживает объекты как сталкивающиеся, даже когда они находятся далеко друг от друга. Как только у меня были проекции всех углов, я проверил, какие из них были минимальными и максимальными, проверив длину между каждой точкой. Я уверен, что это что-то маленькое, чего мне не хватает. pastebin.com/7yGWF5AG