«1. Обзор

В этом кратком уроке мы научимся решать алгоритмическую задачу проверки того, перекрываются ли два заданных прямоугольника.

Мы начнем с определения проблемы, а затем постепенно найдем решение.

Наконец, мы реализуем это на Java.

2. Постановка задачи

Предположим, у нас есть два заданных прямоугольника – r1 и r2. Нам нужно проверить, есть ли хотя бы одна общая точка между r1 и r2. Если да, то это просто означает, что эти два прямоугольника перекрываются.

Давайте рассмотрим несколько примеров:

Если обратить внимание на самый последний случай, прямоугольники r1 и r2 не имеют пересекающихся границ. Тем не менее, они представляют собой перекрывающиеся прямоугольники, поскольку каждая точка в r1 также является точкой в ​​r2.

3. Начальная настройка

Чтобы решить эту проблему, мы должны сначала определить прямоугольник программно. Прямоугольник может быть легко представлен его левыми нижними и правыми верхними координатами: 

public class Rectangle {
    private Point bottomLeft;
    private Point topRight;

    //constructor, getters and setters

    boolean isOverlapping(Rectangle other) {
        ...
    }
}

где Point — это класс, представляющий точку (x,y) в пространстве: 

public class Point {
    private int x;
    private int y;

    //constructor, getters and setters
}

Позже мы определим isOverlapping(Rectangle other) в нашем классе Rectangle, чтобы проверить, не пересекается ли он с другим заданным прямоугольником — other.

4. Решение

Два заданных прямоугольника не будут перекрываться, если выполняется одно из следующих условий:

  1. One of the two rectangles is above the top edge of the other rectangle
  2. One of the two rectangles is on the left side of the left edge of the other rectangle

Во всех остальных случаях два прямоугольника будут перекрываться друг с другом. Чтобы убедиться в этом, всегда можно привести несколько примеров.

5. Реализация Java

Теперь, когда мы поняли решение, давайте реализуем наш метод isOverlapping(): 

public boolean isOverlapping(Rectangle other) {
    if (this.topRight.getY() < other.bottomLeft.getY() 
      || this.bottomLeft.getY() > other.topRight.getY()) {
        return false;
    }
    if (this.topRight.getX() < other.bottomLeft.getX() 
      || this.bottomLeft.getX() > other.topRight.getX()) {
        return false;
    }
    return true;
}

Наш метод isOverlapping() в классе Rectangle возвращает false, если один из прямоугольников находится выше или ниже. слева от другого, верно иначе.

Чтобы узнать, находится ли один прямоугольник над другим, мы сравниваем их y-координаты. Точно так же мы сравниваем координаты x, чтобы проверить, находится ли один прямоугольник левее другого.

6. Заключение

В этой короткой статье мы узнали, как решить алгоритмическую задачу определения того, перекрываются ли два заданных прямоугольника друг с другом. Он служит стратегией обнаружения столкновений для двух прямоугольных объектов.

Как обычно, весь исходный код доступен на Github.