Теорема о разделяющей оси и Python

Question

Вот что я сейчас делаю:

Создание 4 осей, которые перпендикулярны 4 ребрам из 2 прямоугольников. Так как они являются прямоугольниками, мне не нужно генерировать ось (нормаль) для каждого ребра.

Затем я перебираю свои 4 оси.

Итак, для каждой оси: я получаю проекцию каждого угла прямоугольника на ось. Есть 2 списка (массива), содержащие эти проекции. По одному на каждый прямоугольник. Затем я получаю скалярное произведение каждой проекции и оси. Это возвращает скалярное значение, которое можно использовать для определения минимума и максимума.

Теперь 2 списка содержат скаляры, а не векторы. Я сортирую списки, чтобы легко выбрать минимальное и максимальное значения. Если минимальное значение для поля B >= максимальное для поля A ИЛИ максимальное значение для поля B <= минимальное значение для поля A, то столкновения на этой оси не происходит и столкновения между объектами нет.

В этот момент функция завершается и цикл прерывается.

Если эти условия никогда не выполняются для всех осей, то мы имеем столкновение

Я надеюсь, что это был правильный способ сделать это.

Сам код Python можно найти здесь http://pastebin.com/vNFP3mAb

Также: http://www.gamedev.net/page/reference/index.html/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604

Проблема, которую я имел, состоит в том, что код выше не работает. Он всегда обнаруживает столкновение даже там, где его нет. То, что я напечатал, это именно то, что делает код. Если я пропускаю какие-либо шаги или просто не понимаю, как работает SAT, пожалуйста, дайте мне знать.

Answer 1

Я вижу две вещи неправильно. Во-первых, проекция должна быть просто точечным произведением вершины с осью. То, что вы делаете, слишком сложно. Во-вторых, способ, которым вы получаете свою ось, неверен. Ты пишешь:

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] не перекрываются, потому что минимум последнего больше, чем максимум первого. Второе сравнение - для случаев, когда входные наборы меняются местами.

Answer 2

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

Есть несколько простых способов "оптимизировать" в смысле обеспечения шансов для более ранних выходов. Практическая ценность этого зависит от распределения прямоугольников, которые проверяются, но оба легко включаются в существующую структуру.

(1) Проверка ограничивающего круга

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

(2) вершина одного прямоугольника внутри другого

Проекция вершины одного прямоугольника на оси, параллельные краям другого прямоугольника, предоставляет достаточно информации, чтобы определить, находится ли эта вершина внутри другого прямоугольника. Эта проверка особенно проста, когда последний прямоугольник был переведен и не повернут в начало координат (ребра параллельны обычным осям). Если случается, что вершина одного прямоугольника находится внутри другого, то прямоугольники, очевидно, пересекаются. Конечно, это достаточное условие для пересечения, а не необходимое. Но это допускает ранний выход с заключением пересечения (и, конечно, без нахождения оси разделения, потому что ни один не будет существовать).