Проверьте, не пересекаются ли два прямоугольника

Question

Эти вопросы заданы несколько раз, и я видел много потоков, но мой запрос очень специфичен. Как увидеть, перекрываются ли два прямоугольника. Тест, который обнаруживает ошибку в моем коде:

l2 = новый RectanglePoint (0, 7);
r2 = новый RectanglePoint (6, 10);
l1 = новый RectanglePoint (0, 7);
r1 = новый RectanglePoint (6, 0);
Вызов функции: isOverlap (новый прямоугольник (l1, r1), новый прямоугольник (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; 
    } 

Это ошибка в условии: если (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), что верно в графических координатах, но неверно в декартовых координатах. В зависимости от того, какие координаты вы используете, один из этих прямоугольников ошибочен, поэтому ваш код перекрытия выходит из строя.

Учитывая ваши имена, вы должны исправить координаты при создании прямоугольника или вернуть ошибку для плохих координат. Чтобы исправить декартовы координаты, пусть x-координата topLeft является минимумом x-координат двух заданных вершин, y-координата topLeft - это максимум y-координат двух заданных вершин, x- координата bottomRight - это максимум x-координат двух заданных вершин, а y-координата bottomRight - это минимум y-координат двух заданных вершин. Затем вызывающий может использовать любые две противоположные вершины прямоугольника и все равно получить действительный результат.

Answer 2

Вы полагаете, что входы l1 и l2 собираются быть всегда topLeft координаты и r1 и r2 собираются быть всегда bottomRight координаты. Чтобы придерживаться этого предположения, я рекомендую вам использовать некоторые kindda условие/проверку, чтобы убедиться, что входы согласуются с предположением,

Используйте этот код, прежде чем внутри 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"); 

Упрощение выше условия:

1. Х координата TopLeft должно быть меньше, чем у BottomRight
2. Y координата TOPL тритон должен быть больше, чем у BottomRight

Или вы можете проверить это в конструкторе Rectangle()

Для простого и языка независимого объяснения, оформление заказа my answer on a similar thread