Sunday, September 24, 2023

How to Check if two Rectangles Overlap in Java? Collision Detection Solution and Example

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 like 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 friends who were in the 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 languages 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 the 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 in the game programming domain and companies like Electronic Arts and Sony. Why? because this is also used as a 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 the 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 like a very interesting problem for me and so I decided to take a look at this one.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithms as possible to take advantage of all the knowledge available. You can also join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.







How to check if two Rectangle Overlaps in Java?

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.

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 weekends and I have thoroughly enjoyed it.

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. The left edge of A is to the right of the right edge of B. In this case, the first rectangle A is completely on the right side of second rectangle B as shown in the following diagram

collision detection problem Java solution



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



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

code to test for rectangle overlapping in Java


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

How to Check if two Rectangles Overlap in Java


If any of the above four conditions are not true then two rectangles are overlapping with each other, as in the following diagram the 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, a very interesting book to learn patterns 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 coordinates in a Point class and have Rectangle has two Point instance variables 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 colliding or not is coded in the isOverlapping() method which is as per the approach discussed 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 to solve in interviews and trying to develop the algorithm to solve the problem is also a good choice. If you struggle to solve this kind of question then you should join a comprehensive data structure and problem-solving course and practice some problems on Data Structure and Algorithms which I have shared below.


Other coding problems in Java you may like
  • How to swap two numbers without using the third variable? (answer)
  • How to implement the sieve of the Eratosthenes algorithm in Java? (solution)
  • How to add two numbers without using the plus operator in Java? (answer)
  • How to implement a binary search tree in Java? (solution)
  • How to implement pre-order traversal of a binary tree in Java? (solution)
  • How to implement a 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 an insertion sort algorithm in Java? (answer)

P. S. - You can also try testing this algorithm with a different kind of rectangle to see if it works in all scenarios or not. For further reading, you can read Introduction to Algorithm or Game Programming patterns book.

And lastly one question for you? Which one is your favorite Java Programming exercise? Palindrome, Prime number, Fibonacci, Factorial or this one? 

5 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.

Unknown 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 ??

Anonymous said...

Not okay. The case when the other rectangle is rotated is more complicated. Your extended test, for example, will say the rectangles (-1,3.5)(1,3.5)(1,5.5)(-1,5.5) and (1,0)(5,4)(4,5)(0,1) overlap while in fact they don't.

Sacred Hollow Lefts said...

What if the rectangles share a border, but don't actually overlap? If the max X side of one rectangle is the min X side of the other rectangle your overlapping method will return true. Rectangles only overlap if their overlapping area is > 0, and your method will return true when the overlapping area is 0.

Post a Comment