Повернутый прямоугольник Столкновение

Question

Какой самый эффективный способ выяснить, сталкивается ли один выровненный по оси прямоугольник с одним повернутым прямоугольником? Каждый класс имеет вектор положения и вектор размера, а повернутый класс имеет значение угла.

Answer 1

Вы хотите использовать теорему о разделяющей оси (SAT). Обычно он используется в 3d, но довольно хорошо падает до 2d. Поскольку у вас есть особый случай, единственная ось, которую вы должны рассмотреть, - это 4 основные оси ваших прямоугольников:

[ 1,0 ]
[ 0,1 ]
[ sin(theta), cos(theta) ]
[ -cos(theta), sin(theta) ]

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

Вот недавний SO вопрос по той же проблеме: Теорема о разделяющей оси и Python

А вот статья в википедии

http://en.wikipedia.org/wiki/Separating_axis_theorem

Answer 2

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

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

Затем вы могли бы использовать этот «подтвержденный» удар, чтобы выполнить анализ с более сложной моделью;тот, который учитывает углы, скорости, геометрию и упругость столкновения (или все, что вас интересует).

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