Проверете дали два правоъгълника се припокриват в Java

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, за да проверим дали се припокрива с друг даден правоъгълник - друг .

4. Решение

Двата дадени правоъгълника няма да се припокриват, ако някое от следните условия е вярно:

  1. Един от двата правоъгълника е над горния ръб на другия правоъгълник
  2. Един от двата правоъгълника е от лявата страна на левия ръб на другия правоъгълник

За всички останали случаи двата правоъгълника ще се припокриват един с друг. За да се убедим, винаги можем да извадим няколко примера.

5. Внедряване на Java

Сега, когато разбираме решението, нека приложим нашия метод isOverlapping () :

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

Нашата isOverlapping () метод в правоъгълник класа връща фалшива , ако един от правоъгълници е над или към лявата страна на друга, вярно друго.

За да разберем дали един правоъгълник е над другия, сравняваме техните y-координати . По същия начин сравняваме x-координатите, за да проверим дали един правоъгълник е вляво от другия.

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

В тази кратка статия научихме как да решим алгоритмичен проблем за намиране дали двата дадени правоъгълника се припокриват помежду си. Той служи като стратегия за откриване на сблъсък за два правоъгълни обекта.

Както обикновено, целият изходен код е достъпен в Github.