android - 用于矩形相交计算的 Minkowski 和

Question

我一直在研究确定 2 个矩形相交位置的最佳方法，并且一直在研究使用 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)

否则会发生碰撞。

如果你的矩形不是轴对齐的，那么你可以使用有效的separating axes algorithm

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

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

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

有一些方法，比如我们可以用Liang-Barsky line clipping algorithm .请注意，我们不必检查所有交点，因为我们只需要第一次碰撞 - 如果 vx >=0，则检查与左边缘的交点并忘记右边缘等等......