Теорема о разделяющей оси и Python - PullRequest
Новая
       74

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

4 голосов
/ 16 мая 2011

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

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

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

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

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

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

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

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

Сам код 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, пожалуйста, дайте мне знать.

Ответы [ 2 ]

5 голосов
/ 16 мая 2011

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

Существует несколько простых способов «оптимизации» в смысле обеспечения шансов для более ранних выходов.Их практическая ценность зависит от распределения прямоугольников, которые проверяются, но оба легко включаются в существующую структуру.

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

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

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

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

3 голосов
/ 16 мая 2011

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

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

...