Program to check if two rectangle overlap or itntersect

Input - 2 Rectangles with x and y coordinates.
Output - boolean value which states if they overlap or not 

This is a one of the classic problems in graphics programming and game development. So, let's see how we can solve it.

Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. As you move down the screen, the y value increases. And, as you move right the x value increases.

Algorithm :

• Two rectangles can overlap if one rectangle has 0,1,2,4 corners inside the other rectangle. The check of above mentioned condition could result is many different combinations. Remember overlapping rectangle cannot have 3 corners inside.
  
• Other way we can say that two rectangle overlap if the region of one rectangle lies inside the other.

• The best way to find is to identify whether an overlapping area is present or not which can be known if the below mentioned all conditions are true.
  
  If we check that( B = Black rectangle, R - Red Rectangle)
  
  
• The left edge of B is to the left of right edge of R.
• The top edge of B is above the R bottom edge.
• The right edge of B is to the right of left edge of R.
• The bottom edge of B is below the R upper edge.

Then we can say that rectangles are overlapping.

Off-course, we discussed the algorithm on matching rectangles, let's now focus on where the rectangles will not intersect.

Consider the following figure:

From those pictures, we can infer that two rectangles are not intersecting each other if they have one of the four conditions:

1. Right edge of blue is closer to the left of the screen than the left edge of red 
2. Bottom edge of blue is further from the bottom of the screen than the top edge of red 
3. Top edge of blue is closer to the bottom of the screen than the bottom edge of red 
4. Left edge of blue is further from the left of the screen than the right edge of red

Consider an example: There are two rectangles as shown in diagram – Black Rectangle (B) and Red rectangle(R).

Conditions to be checked
The left edge of B is to the left of right edge of R. The selected area will be :

The top edge of B is above the R bottom edge. So the selected area will be:

The right edge of B is to the right of left edge of R. The selected area will be:

The bottom edge of B is below the R upper edge. The selected area will be:

Hence all conditions are true we can say that rectangles are overlapping.


Therefore we can see that all the conditions are valid and hence rectangle is overlapping.
 
c++ implementation

#include<iostream>
using namespace std;

struct Point
{
  float x;
  float y;
};

struct Rect
{
  Point topLeft;
  Point bottomRight;
};

bool checkOverlap(Rect rect1, Rect rect2)
{
  if (rect1.topLeft.x >= rect2.bottomRight.x 
      || rect1.bottomRight.x <= rect2.topLeft.x 
      || rect1.topLeft.y <= rect2.bottomRight.y 
      || rect1.bottomRight.y >= rect2.topLeft.y)
    return false;
    
  return true;
}

Java implementation
Here is the java implementation for the code if you want to visualize as well. The logic is only present in checkOverlap() method, rest is used to display the GUI and check.

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;



public class RectangleOverlap extends JPanel{

 int r1x1,r1x2,r2x1,r2x2 ;
 int r1y1,r1y2,r2y1,r2y2 ;
 int r1width,r2width ;
 int r1height,r2height ;

 static JButton btn = new JButton("Check");
 public RectangleOverlap(int r1x1,int r1y1,int r1x2,int r1y2,
   int r2x1,int r2y1,int r2x2,int r2y2){

  this.r1x1=r1x1;
  this.r1x2=r1x2;
  this.r1y1=r1y1;
  this.r1y2=r1y2;
  
  this.r2x1=r2x1;
  this.r2x2=r2x2;
  this.r2y1=r2y1;
  this.r2y2=r2y2;

  r1width = Math.abs(r1x1-r1x2);
  r2width = Math.abs(r2x1-r2x2);
  r1height = Math.abs(r1y1-r1y2);
  r2height = Math.abs(r2y1-r2y2);

  addActionListener();
 }



 private void addActionListener() {
  btn.addActionListener(new ActionListener(){

   public void actionPerformed(ActionEvent e) {
    checkOverlap();
   }
  });
 }

 private void checkOverlap() {
  // condition to check whether the rectangles are overlapping or not.s
  boolean isOVerlap= ((r1x2 >= r2x1) &&
    (r1y2 >= r2y1) &&
    (r1x1 <= r2x2) &&
    (r1y1 <= r2y2));

  if(isOVerlap ){
   JOptionPane.showMessageDialog(null, "OVerlap");
  }else{
   JOptionPane.showMessageDialog(null, "No OVerlap");
  }

 }



 @Override

 protected void paintComponent(Graphics g) {
  g.drawRect(r1x1,r1y1 , r1width, r1height);
  g.setColor(new Color(123,232,122));
  g.drawRect(r2x1, r2y1, r2width,r2height);

 }



 public static void main(String args[]){
  JFrame frame = new JFrame();
  frame.setSize(500,500);

  // input to check overlap condition.

  // the order followed as : enter coordinate for 1st rectangle as
  // lower limit and upper limit to rectangles          

  frame.getContentPane().add(new RectangleOverlap(20,30,120,130,10,50,160,120),
    BorderLayout.CENTER);
  frame.getContentPane().add(btn,BorderLayout.SOUTH);
  frame.addWindowListener(new WindowAdapter(){
   @Override

   public void windowClosing(WindowEvent e) {
    System.exit(0);
   }

  });

  frame.setVisible(true);

 }

}

Sources:
http://codesam.blogspot.com/2011/02/check-if-two-rectangles-intersect.html
http://tech-read.com/2009/02/06/program-to-check-rectangle-overlapping/