检查两个矩形是否重叠

Question

这个问题已经问过很多次了，我也看到过很多话题，但我的查询非常具体。如何查看两个矩形是否重叠。在我的代码中发现错误的测试用例是：

l2 = new RectanglePoint(0, 7);
r2 = new RectanglePoint(6, 10);
l1 = new RectanglePoint(0, 7);
r1 = new RectanglePoint(6, 0);
Function call: isOverlap(new Rectangle(l1, r1), new Rectangle(l2, r2));

我的代码：

class RectanglePoint {
    int x;
    int y;

    public RectanglePoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Rectangle {
    RectanglePoint topLeft;
    RectanglePoint bottomRight;

    public Rectangle(RectanglePoint topLeft, RectanglePoint bottomRight) {
        this.topLeft = topLeft;
        this.bottomRight = bottomRight;
    }
}

public class RectangleOverlap {
    public boolean isOverlap(Rectangle rect1, Rectangle rect2) {
        return isOverlapHelper1(rect1.topLeft, rect1.bottomRight, rect2.topLeft,
                rect2.bottomRight);
    }


    private boolean isOverlapHelper1(RectanglePoint topLeftA,
            RectanglePoint bottomRightA, RectanglePoint topLeftB,
            RectanglePoint bottomRightB) {
        if (topLeftA.y < bottomRightB.y || topLeftB.y < bottomRightA.y) {
            return false;
        }
        if (topLeftA.x > bottomRightB.x || topLeftB.x > bottomRightA.x) {
            return false;
        }
        return true;
    }

The bug is in the condition: if (topLeftA.y < bottomRightB.y || topLeftB.y < bottomRightA.y)

请帮忙。我已经在这上面花了很多时间了。

Answer 1

您的条件 if (topLeftA.y < bottomRightB.y || topLeftB.y < bottomRightA.y) 和 (topLeftA.x > bottomRightB.x || topLeftB.x > bottomRightA.x) 假定属性 topLeft 确实是矩形的左上角顶点并且 bottomRight 确实是右下角矩形的顶点。但是，您的初始化代码 this.topLeft = topLeft; 和 this.bottomRight = bottomRight; 实际上并不能保证这一点。如果初始化为矩形使用了错误的顶点，您的代码不会更正该错误，以后的方法可能会出错。

这就是您的测试用例中发生的情况。您不清楚您的坐标是笛卡尔坐标（增加 y 值上升）还是图形坐标（增加 y 值下降）。但无论哪种情况，您的两个测试矩形中的一个都定义错误。您的第一个矩形从 (0, 7) 到 (6, 0)，这在笛卡尔坐标中是正确的，但在图形坐标中是错误的。您的第二个矩形从 (0, 7) 到 (6, 10)，这在图形坐标中是正确的，但在笛卡尔坐标中是错误的。无论您使用哪个坐标，其中一个矩形是错误的，因此您的重叠代码将失败。

鉴于您的名字，您应该在创建矩形时更正坐标，或者 return 错误坐标。为了校正笛卡尔坐标，令 topLeft 的 x 坐标为两个给定顶点的 x 坐标中的最小值，topLeft 的 y 坐标为两个给定顶点的 y 坐标中的最大值，x- bottomRight 的坐标是两个给定顶点的 x 坐标的最大值，bottomRight 的 y 坐标是两个给定顶点的 y 坐标的最小值。然后调用者可以使用矩形的任意两个相对顶点并仍然得到有效结果。

Answer 2

您假设输入 l1 和 l2 将始终是 topLeft 坐标，而 r1 和 r2 将始终是bottomRight 坐标。为了坚持这个假设，我建议你使用一些 condition/validation 来确保输入与你的假设一致，

在 isOverlap() 调用 isOverlapHelper1()

之前使用此代码

if ((rect1.topLeft.x > rect1.bottomRight.x) ||
(rect1.topLeft.y < rect1.bottomRight.y) ||
(rect2.topLeft.x > rect2.bottomRight.x) || 
(rect2.topLeft.y < rect2.bottomRight.y))
  throw new IllegalArgumentException("Wrong co-ordinates");

以上条件的简化：

TopLeft 的 X 坐标应小于 BottomRight 的 X 坐标
左上角的Y坐标应大于右下角的Y坐标

或者你可以在构造函数中检查这个 Rectangle()

为了更简单和独立于语言的解释，请查看 my answer on a similar thread

检查两个矩形是否重叠

Check if two rectangles overlap

java

math

rectangles

data-structures