Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (603) Games in Android Showcase (171) games submitted by our members Games in WIP (652) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Fastest way to determine if two rotated rectangles intersect?  (Read 6786 times) 0 Members and 1 Guest are viewing this topic.
CodeBunny

Senior Devvie

Medals: 4
Projects: 3

 « Posted 2012-04-12 17:59:40 »

So, I have two rectangles, A and B.

Each rectangle has:
A midpoint, labeled x and y.
A rotation, labeled r.
A width and a height, labeled w and h.

What is the fastest possible way in code to determine if these two rectangles intersect or not?
ra4king

JGO Kernel

Medals: 389
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #1 - Posted 2012-04-12 18:02:31 »

Roquen
 « Reply #2 - Posted 2012-04-12 20:08:35 »

SAT in this case will not be the fastest.  Using SAT, however, is reasonable.  Note that the axis will be the direction between the centers.
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #3 - Posted 2012-04-12 20:58:44 »

This is a plenty solved problem. Have a look here:

http://gamedev.stackexchange.com/questions/7890/2d-object-aligned-bounding-box-intersection-test

See my work:
OTC Software
CodeBunny

Senior Devvie

Medals: 4
Projects: 3

 « Reply #4 - Posted 2012-04-12 21:03:29 »

Hmm. The SAT seems to heavyweight for what I'm thinking.

I'm trying to find a good 2D graphics clipping algorithm. The view region can be moved and rotated, as can the entities that would appear in it.

The method I currently use is "lossy" - I have my viewing region, and I check if each entity's location is within its bounding radius away from the view. That way I don't have to do any complex math to determine if it should be rendered or not. However, I want to look at other, more specific methods, to see what else is possible.

Here are some examples:

As you can see, object A will be rendered:

However, object B will not:
Roquen
 « Reply #5 - Posted 2012-04-13 08:05:46 »

Note that the axis will be the direction between the centers.
Note: Bad me.  This is incorrect, it will be one of the faces intersecting this segment.

Inside the view area is a slightly different question as it depends on how the world is represented and you probably don't care about exact results.
DzzD
 « Reply #6 - Posted 2012-04-13 09:21:16 »

If you are looking for fastness rather than precision I would advice to make a first pass using bounding radius of both view and objects (basically distance between center of view and center of object) and remove all object that are too far and than use another method smarter for all remaining viewable objects

basically :

 1  2  3  4  5  6  7  8  9  10  11  12  13 `for each objects{double dx=objectX-viewX;double dx=objectY-viewY;double distMinSqrt = (viewRadius+objectRadius)²; //<== for even faster test, this value could be precomputed and stored for each object if there size doesnt changeif(dx*dx+dy*dy>distMinSqrt ) //Object wont be viewable  continue; //Here use a smarter test if requiered ...}`

Roquen
 « Reply #7 - Posted 2012-04-13 11:07:42 »

DzzD's suggestion is reasonable. I'd augment it by saying abstract way setting of object's position and the query.  In that manner you can move to a more advanced technique if and only if you need to...otherwise move on to something else.

FWI: An example would be to change to storing in a uniform grid, then the first pass becomes equivalent to rasterizing a rect, where each cell is treated like a pixel.  There are a couple of tweakable factors here: size of cells and/or rejection of false positives along the edges.
CodeBunny

Senior Devvie

Medals: 4
Projects: 3

 « Reply #8 - Posted 2012-04-14 12:02:03 »

Sweet, thanks, I'll be able to work with this.
tarlek

Junior Devvie

Medals: 2
Projects: 1

 « Reply #9 - Posted 2012-09-01 17:24:17 »

You can project the corners of the two rotated rectangles into 2 polygons, and perform these tests:

1. Does any line from poly1 intersect with any line from poly2?
2. Is any vertex from poly1 inside poly2, or vice-versa?

If either is true, then there is an overlap. This is not expensive to calculate and is accurate.