确定两个矩形是否相互重叠？

Question

我正在尝试编写一个 C++ 程序，该程序接受用户的以下输入来构造矩形（2 到 5 之间）：高度、宽度、x-pos、y-pos。所有这些矩形都将平行于 x 和 y 轴存在，也就是说，它们的所有边都将具有 0 或无穷大的斜率。

我试图实现 这个 问题中提到的内容，但我运气不佳。

我当前的实现执行以下操作：

 // Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;

但是我不太确定（a）我是否已经正确实现了我链接到的算法，或者我是否确实做了如何解释这个？

有什么建议么？

原文由 Rob Burke 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )

或者，使用笛卡尔坐标

（X1是左坐标，X2是右坐标， 从左到右增加，Y1是上坐标，Y2是下坐标， 从下到上增加——如果这不是你的坐标系[例如，大多数计算机有Y方向反转]， 交换下面的比较）…

 if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)

假设你有 Rect A 和 Rect B。证明是矛盾的。四个条件中的任何一个都保证 不存在重叠：

• 条件 1。如果 A 的左边缘在 B 的右边缘的右侧，则 - 则 A 完全在 B 的右侧
• 条件 2。如果 A 的右边缘在 B 的左边缘的左侧， - 那么 A 完全在 B 的左侧
• 条件 3。如果 A 的上边缘低于 B 的下边缘，则 - 则 A 完全低于 B
• 条件 4。如果 A 的底边高于 B 的顶边， - 那么 A 完全高于 B

所以非重叠的条件是

非重叠 => Cond1 或 Cond2 或 Cond3 或 Cond4

因此，重叠的充分条件是相反的。

重叠 => 非（Cond1 或 Cond2 或 Cond3 或 Cond4）

德摩根定律说

Not (A or B or C or D) 与 Not A And Not B And Not C And Not D 相同

所以使用德摩根，我们有

非 Cond1 且非 Cond2 且非 Cond3 且非 Cond4

这相当于：

• A 的左边缘到 B 的右边缘的左侧，[ RectA.Left < RectB.Right ]，和
• A 的右边缘到 B 的左边缘的右侧，[ RectA.Right > RectB.Left ]，和
• A 的顶部高于 B 的底部，[ RectA.Top > RectB.Bottom ]，和
• A 的底部低于 B 的顶部 [ RectA.Bottom < RectB.Top ]

注 1 ：很明显，同样的原理可以扩展到任意数量的维度。

注意 2 ：计算仅一个像素的重叠也应该是相当明显的，将边界上的 < 和/或 > 更改为 <= 或一个 >= 。

注意 3 ：当使用笛卡尔坐标 (X, Y) 时，此答案基于标准代数笛卡尔坐标（x 从左到右增加，Y 从下到上增加）。显然，如果计算机系统可能以不同方式处理屏幕坐标（例如，从上到下增加 Y，或从右到左增加 X），则需要相应地调整语法/

原文由 Charles Bretana 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

如果两个矩形重叠，这是使用 C++ 检查的一种非常快速的方法：

 return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
    && std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

它的工作原理是计算相交矩形的左右边界，然后比较它们：如果右边界等于或小于左边界，则表示交点为空，因此矩形不重叠；否则，它会再次尝试使用顶部和底部边框。

与传统的 4 次比较替代方法相比，这种方法有什么优势？这是关于现代处理器的设计方式。他们有一种叫做分支预测的东西，当比较的结果总是相同的时候效果很好，但否则会有巨大的性能损失。但是，在没有分支指令的情况下，CPU 的性能相当不错。通过计算交叉点的边界而不是对每个轴进行两次单独的检查，我们节省了两个分支，每对一个。

如果第一次比较很可能是错误的，那么四种比较方法可能会优于这种方法。不过，这种情况非常少见，因为这意味着第二个矩形通常位于第一个矩形的左侧，而不是右侧或重叠。大多数情况下，您需要检查第一个矩形两侧的矩形，这通常会抵消分支预测的优势。

这种方法可以进一步改进，具体取决于矩形的预期分布：

• 如果您希望选中的矩形主要位于彼此的左侧或右侧，则上述方法效果最佳。例如，当您使用矩形交集来检查游戏的碰撞时，可能就是这种情况，其中游戏对象主要水平分布（例如，类似于 SuperMarioBros 的游戏）。
• 如果您希望检查的矩形主要位于彼此的顶部或底部，例如在冰塔类型的游戏中，那么先检查顶部/底部和最后检查左/右可能会更快：

 return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom)
    && std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);

• 但是，如果相交的概率接近于不相交的概率，最好有一个完全无分支的替代方案：

 return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
     & std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

（注意将 && 更改为单个 & ）

原文由 Pedro Gimeno 发布，翻译遵循 CC BY-SA 4.0 许可协议