Каков наилучший способ обнаружения столкновения?

Question

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

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

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

Answer 1

Metanet's excellent collision detection tutorial имеет хороший раздел о том, как совершать ударные столкновения с выровненными по оси ограничительными рамками (AABB) и произвольными «стенами».

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

Answer 2

Если вы хотите проверить только углы прямоугольника, вы можете выполнить «внутренний» тест для каждого из них. http://en.wikipedia.org/wiki/Point_in_polygon

И если вы также хотите, чтобы убедиться, что ни один заостренная часть полигона «не прокалывает» ваш прямоугольник можно сделать тест для каждого из 4-х линий в прямоугольнике против всех линий в многоугольнике, чтобы увидеть, если они пересекаются. http://en.wikipedia.org/wiki/Line-line_intersection