Обнаружение столкновения 2D полигонов

Question

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

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

Спасибо

Answer 1

Посмотрите теорему о разделяющей оси.Здесь есть учебник .

Он быстрый, элегантный, надежный, не слишком сложный и имеет много ресурсов.

Answer 2

Выезд http://www.metanetsoftware.com/technique/tutorialA.html

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

1) Ограничительная коробка: хороша для прямоугольных форм и быстрой загрузки. Все, что вам нужно знать, это (x, y) положение объекта, а также его ширина и высота.

2) Теорема о разделении осей (SAT): Способна обрабатывать более сложные формы и довольно интуитивна.

3) SAT с регионами Вороного (VR): использует информацию о том, к какой вершине любого заданного многоугольника ближе всего, чтобы уменьшить общее количество вычислений.

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

Answer 3

Пример:

Прямоугольник A

Левый, верхний угол (x, y). Ширина, высота.

Прямоугольник B

Левый, верхний угол (x1, y1).

Состояние

(x> = x1) и (x <= x1 + width) => столкновение для оси x. Для оси y это то же самое, но с y и y1 и высотой.

Answer 4

Есть несколько методов, простой - просто проверить, есть ли перекрытия в X или Y границах.Это, однако, работает только с прямоугольниками, выровненными по оси.

Есть проверка границ, это угол одного объекта с границами координат другого.

Оттуда обнаружение столкновений становится более продвинутым.Проверка наличия линии, которую можно провести между ними в любом направлении и т. Д.