Minkowski sum for rectangle intersection calculation

我一直在寻找最好的方法来确定2矩形相交的位置，并且一直在考虑使用Minkowski和。Minkowski sum for rectangle intersection calculation

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

我已阅读了很多关于此，但我不知道如何正确实现这一点。

由于

的代码是：

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 */ 
}

来源

2013-04-24 Zippy

如果您的矩形轴对齐，则有简单的方法：

矩形A和B 不相交，如果

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

否则会发生碰撞。使用Minkowski和动态碰撞：

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

编辑

让我们我们已经移动矩形A和站在矩形B.让我们的速度A的矢量是（vx，vy）。我们希望找到第一次碰撞的时刻，并确定彼此之间有什么边缘。

首先，将一个矩形缩小到具有相同中心的点，对称地将A.Width展开B.Width，并使用A.Height展开B.Height（使Minkowski sum）。现在我们必须找到线（射线）与矩形的交点。

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

来源

2013-04-25 06:16:01 MBo

Hi @MBo - I'm使用轴对齐的简单边界矩形/正方形。没有旋转（或者至少没有需要CD的旋转）。你的方法存在的问题是，它不能告诉我哪条边发生碰撞，并且如果两条边相交，哪条边首先相交，我需要这些信息来对碰撞进行反应/重新定位移动的精灵。你有什么想法，我会这样做，因为我一直在寻找2天坚实，我迄今为止尝试过的一切都失败了。帮助将不胜感激。谢谢 – Zippy 2013-04-25 12:45:07

请您详细说明一下@Mbo，我不太明白你的意思....谢谢！ – Zippy 2013-04-25 23:16:32

@Zippy图片添加 – MBo 2013-04-26 03:57:07

Minkowski sum for rectangle intersection calculation

回答

相关问题