android - 矩形交点计算的 Minkowski 和

Question

我一直在研究确定 2 个矩形相交位置的最佳方法，并一直在研究使用 Minkowski 和。

如果有人能解释如何使用 Minkowski 和来确定 2 个矩形何时何地（即哪个边）碰撞，我将不胜感激。

我已经阅读了很多关于此的内容，但我不确定如何正确实现这一点。

谢谢

代码是：

float w = 0.5 * (A.width() + B.width());
float h = 0.5 * (A.height() + B.height());
float dx = A.centerX() - B.centerX();
float dy = A.centerY() - B.centerY();

if (abs(dx) <= w && abs(dy) <= h)
{
/* collision! */
float wy = w * dy;
float hx = h * dx;

if (wy > hx)
    if (wy > -hx)
        /* collision at the top */
    else
        /* on the left */
else
    if (wy > -hx)
        /* on the right */
    else
        /* at the bottom */
}

Answer 1

如果您的矩形是轴对齐的，那么有一个简单的方法：

矩形 A 和 B不相交，如果

(A.Left > B.Right) or 
(A.Right < B.Left) or 
(A.Top < B.Bottom) or 
(A.Bottom > B.Top)

否则会发生碰撞。

如果您的矩形不是轴对齐的，那么您可以使用有效的分离轴算法

编辑：使用 Minkowski 和的动态碰撞：

让我们有移动矩形 A 和站立矩形 B。让我们 A 的速度向量是 (vx, vy)。我们想找到第一次碰撞的时刻并确定哪些边缘相互接触。

首先，将A矩形缩小到中心相同的点，将B.Width对称地扩大A.Width，将B.Height扩大A.Height（Minkowski求和）。现在我们必须找到直线（射线）与矩形的交点。

有一些方法，例如，我们可以使用Liang-Barsky 线裁剪算法。请注意，我们不必检查所有交叉点，因为我们只需要第一次碰撞 - 如果 vx >=0，检查与左边缘的交叉点并忘记右边缘等等......

Answer 2

我迟到了 7 年，但我想我会分享一些“几何外行”的直觉，我在这几个小时里摸不着头脑。

附件是涉及该算法的问题的一些注释，我通过这些注释帮助我理解值之间的关系。（希望为我的回复附上注释不会太违反 Stack Overflow 的政策）