How to check if two Rectangle Overlap in Java - Algorithm

Can you write a Java program to check if two rectangles are overlapping with each other or not? is one of the frequently asked coding questions on tech giants like Facebook, Amazon, Microsoft and others. This is also a kind of problem where it's easy to find opposite or negative conditions e.g. when rectangles are not overlapping and then inverting the result to prove that rectangles are colliding with each other. I first heard about this problem from one of my friend who was on Android game development space. He was asked to write an algorithm to find if given rectangles are intersecting or not. He was given the choice to implement the algorithm in any programming language e.g. Java, C, C++ or even pseudo code was fine, so don't worry about language here, it's more about algorithm and logic. He is a genius so he came successful from that interview, impressing the interviewer, talking about efficiency and accuracy of the algorithm as well.

Later when I catch-up with him, he told me about his interview experience and said that this question is quite popular on game programming domain and companies like Electronic arts and Sony. Why? because this is also used as collision detection algorithm, not very sophisticated but it is a quite popular collision detection algorithm for many arcade games like Super Mario Bros, Pac-Ma n, Donkey Kong and Breakout.

Since you can represent the characters and enemy as rectangle you can find out when an arrow hit the character or when he got one up by checking two rectangles are intersecting with each other. This looks very interesting problem to me and so I decided to take a look at this one. Btw, if you are interested in learning algorithms, I would suggest a brand new book, Grooking Algorithm by Aditya Bhargava. I was reading this book in the last couple of weekend and I have thoroughly enjoyed it.




How to check if two Rectangle Overlaps

The algorithm to check if two rectangles are overlapping or not is very straight forward but before that you need to know how you can represent a rectangle in Java programs? Well, a rectangle can be represented by two coordinates, top left, and bottom right. As part of the problem you will be given four coordinates L1, R1 and L2, R2, top left and bottom right coordinate of two rectangles and you need to write a function isOverlapping() which should return true if rectangles are overlapping or false if they are not.

Algorithm to check if rectangles are overlapping
Two rectangles A and B will not overlap or intersect with each other if one of the following four conditions is true.

1. Left edge of A is to the right of right edge of B. In this case first rectangle A is completely on right side of second rectangle B as shown in the following diagram




2. right edge of A is to the left of left edge of B. In this case first rectangle A is completely on the left side of second rectangle B, as shown below



3. Top edge of A is below bottom edge of B. In this case, first rectangle A is completely under second rectangle B as shown in the following diagram



4. Bottom edge of A is above top edge of B. In this case, first rectangle A is completely above second rectangle B as shown in the following diagram



If any of above four conditions is not true then two rectangles are overlapping with each other, as in following diagram first condition is violated, hence rectangle A intersects rectangle B. If you are interested in Game programming, I also suggest you take a look at Game programming patterns by Robert Nystrom, very interesting book to learn pattern with real world examples from games.

How to check if two Rectangle Overlap in Java - Algorithm



Java Program to check if two rectangles are intersecting

In this program, I have followed standard Java coding practices to solve this problem. I have encapsulated two co-ordinates in a Point class and have Rectangle has two Point instance variable and an instance method like equals() to check if another rectangle is overlapping with it or not. The logic to check if two rectangles are overlapping or not is coded in the isOverlapping() method which is as per the approach discuss in the solution section.

/*
 * Java Program to check if two rectangles is intersecting with each
 * other. This algorithm is also used as collision detection
 * algorithm in sprite-based arcade games e.g. Supre Mario Bros
 */

public class Main {

  public static void main(String[] args) {
  Point l1 = new Point(0, 10);
  Point r1 = new Point(10, 0);
  Point l2 = new Point(5, 5);
  Point r2 = new Point(15, 0);

  Rectangle first = new Rectangle(l1, r1);
  Rectangle second = new Rectangle(l2, r2);

  if (first.isOverLapping(second)) {
  System.out
  .println("Yes, two rectangles are intersecting with each other");
  } else {
  System.out
  .println("No, two rectangles are not overlapping with each other");
  }
  }

}

class Point {
  int x;
  int y;

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

class Rectangle {

  private final Point topLeft;
  private final Point bottomRight;

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

  /**
  * Java method to check if two rectangle are intersecting to each other.
  * 
  * @param other
  * @return true if two rectangle overlap with each other
  */
  public boolean isOverLapping(Rectangle other) {
  if (this.topLeft.x > other.bottomRight.x // R1 is right to R2
  || this.bottomRight.x < other.topLeft.x // R1 is left to R2
  || this.topLeft.y < other.bottomRight.y // R1 is above R2
  || this.bottomRight.y > other.topLeft.y) { // R1 is below R1
  return false;
  }
  return true;
  }

}

Output
Yes, two rectangles are intersecting with each other



That's all about how to check whether two rectangles are overlapping with each other or not. It's one of the interesting coding questions and trying to develop the algorithm to solve the problem is also a good choice. Try testing this algorithm with a different kind of rectangle to see if it works in all scenario or not. For further reading, you can read Introduction to Algorithm or Game Programming patterns book.



Othe coding problems in Java you may like
  • How to swap two numbers without using the third variable? (answer)
  • How to implement sieve of Eratosthenes algorithm in Java? (solution)
  • How to add two numbers without using plus operator in Java? (answer)
  • How to implement binary search tree in Java? (solution)
  • How to implement pre-order traversal of a binary tree in Java? (solution)
  • How to implement binary search algorithm in Java? (solution)
  • How to implement in-order traversal in Java? (solution)
  • How to print all leaf nodes of a binary tree in Java? (solution)
  • How to implement iterative quicksort in Java? (solution)
  • Write a program to implement bubble sort in Java? (solution)
  • How to implement insertion sort algorithm in Java? (answer)



3 comments :

Anonymous said...

Interesting question, thanks for sharing with us.

Anonymous said...

This is also known as "rectnagle intersection problem" e.g. write a program to check if two rectangle intersect with each other.

Sudarshan Sahu said...

A rectangle should be represented in class by coordinates of four points - top-left, top-right, bottom-left and bottom-right. Why so? Because not always the corresponding arms of two rectangles be parallel.

if((this.topLeft.y < other.bottomLeft.y && this.topRight.y < other.bottomRight.y)
|| (this.bottomLeft.y > other.topLeft.y && this.bottomRight.y > other.bottomRight.y)
|| (this.topLeft.x > other.topRight.x && this.bottomLeft.x > other.bottomRight.x)
|| (this.topRight.x < other.topLeft.x && this.bottomRight.x < other.bottomLeft.x))

Okay ??

Post a Comment