CODEWITHSUNDEEP
javaalgorithmcollision-detection
user1150769
user1150769

Reputation: 395

Algorithm to determine how much and in what direction two rectangles are overlapping?

Does anyone know of an algorithm that can be used to determine how much and in what direction two rectangles are overlapping? I have spent hours trying to figure this out so I can implement it into a basic tile game written in slick2d + java.

Upvotes: 0

Views: 382

Answers (3)

ElKamina
ElKamina

Reputation: 7807

Let us represent each rectangle as R=(x1,x2,y1,y2) (i.e. (x1,y1), (x1,y2), (x2,y1), (x2,y2) are vertices of that rectangle, and x1

Now, we have two rectangles R1 and R2 and we want to know if they overlap and if yes, what direction.

For each vertex of R1 check if it is inside rectangle R2 which you can represent as 4 bits. The mapping is very direct:

0000 -> None (or R2 is inside R1)
0001 -> R2 is bottom right of R1
0010 -> R2 is top right of R1
0100 -> R2 is bottom left of R1
1000 -> R2 is top left of R1
0011 -> R2 is right of R1
0101 -> R2 is bottom of R1
1100 -> R2 is left of R1
1010 -> R2 is left of R1
1111 -> R1 is inside R2

Other combinations are impossible.

Upvotes: 1

jellyfication
jellyfication

Reputation: 1605

First make a center point between rectangles ( center of second rectangle - center of first one). Check distance form every point of each rectangle to center point. Pick 2 closest points, check if one of them is inside other rectangle, if yes, the rectangle created by these two point gives us the overlapping area.

Upvotes: 0

Sheriff
Sheriff

Reputation: 495

Poll the coordinates for the corners, and if Square1 has any corner between Square2's nearest and farthest vertices, they are in collision by the difference in coordinates?

Example:

square1.setVertex1(0,0);
square1.setVertex2(2,0);
square1.setVertex3(2,2);
square1.setVertex4(0,2);

square2.setVertex1(1,1);
square2.setVertex2(4,1);
square2.setVertex3(4,4);
square2.setVertex4(1,4);

Vertex[] verticesSq1=Square1.getVertices();
for (Vertex vert: verticesSq1) {
    if(vert.getXVal>square2.getLowestXVal() &&
       vert.getXVal<square2.getHighestXVal() 

       &&
       vert.getYval>square2.getLowestYval() &&
       vert.getYVal<square2.getHighestYVal() {

            System.out.write("Vertex "+vert.ID+" is overlapping Square 2 by " +
            vert.getXval()-square2.getLowestXVal +","+
            vert.getYval()-square2.getLowestYVal);
    }
}

Upvotes: 1

Related Questions