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

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

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

If we check that

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

Below is the source code attached. The logic is only present in checkOverlap() method, rest is used to display the GUI and check.

**package** com;

**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**);

}

}

Haseeb

said:Thankyou so much 🙂

Nico Krebs

said:Hey Harshit,

this article show the simplest possible way to do that task for axis-parallel rectangles.

But, do you also know one or two things about how to calculate the upper left and lower right corner coordinates of the resulting intersection rectangle (“final area” in your post)?

I have fount some methods to do this but these methods were applicable for all possible rectangles including arbitrary rotations of the rectangles (in 2D) as well.

But my problem is also very specialized for axis-parallel rectangles. this should mean a simplification of the algorithms i saw.

the result of that intersection method either should be:

1. a point (corner over corner overlap)

2. a line (border over border overlap)

3. a rectangle

or 4. no intesection -> null

this could all be covered by one rectAngle class

1. x1/2 and y1/2 are equal

2. both points have the same x- or y-coordinates

3. all points are disjunct

4. all points each of boxA and boxB e.G. can be separated by a vertical or horizontal line

I’m guessing, someone else already solved this problem but i cant find anything on the web. Probably because i don’t know what special term i have to look for.

go on with your great work!

nico

Nico Krebs

said:Hello again!

i just found the answer to my question on http://www.allegro.cc/forums/thread/588775

the solution is simple – and now obvious.

// rect[n].

// n = rectangle number – 0 for first rectangle, 1 for second rectangle or 2 for overlap

// Left = left edge

// Right = right edge

// Top = top edge

// Bottom = bottom edge

//

rect[2].Left = max(rect[0].Left, rect[1].Left)

rect[2].Right = min(rect[0].Right, rect[1].Right)

rect[2].Top = max(rect[0].Top, rect[1].Top)

rect[2].Bottom = min(rect[0].Bottom, rect[1].Bottom)

as adrian would say:

You’ll thank me later 😉

nicow

Anonymous

said:Another way you could solve this is to find a new rectangle that encloses both of the original original rectangles. If both side lengths of the new rectangle are less than the sum of the corresponding side lengths of the original rectangles, then the original rectangles must overlap because at least one point of each rectangle must lie in the other.