Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (576) Games in Android Showcase (154) games submitted by our members Games in WIP (626) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Fastest way to determine if two rotated rectangles intersect?  (Read 6394 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: 374
Projects: 3
Exp: 5 years

I'm the King!

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

Google "separating axis theorem".

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.
 Games published by our own members! Check 'em out!
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.

 Games published by our own members! Check 'em out!
ddyer
 « Reply #10 - Posted 2012-09-01 20:47:04 »

There is no single, fastest way until you nail down what else you know about the rectangles.   For example, if the rectangles are likely to be far apart, then the fastest way might be to check mins and maxes of the coordinates, and then do more detailed checks only if they might still intersect.  If they're not likely to be far apart, then the quick test would be a quick waste of time.
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 ClaasJG (38 views) 2015-04-30 20:33:25 Riven (23 views) 2015-04-30 13:25:12 ClaasJG (42 views) 2015-04-27 13:36:51 BurntPizza (49 views) 2015-04-23 03:42:11 theagentd (51 views) 2015-04-22 16:23:07 Riven (61 views) 2015-04-16 10:48:47 Duke0200 (74 views) 2015-04-16 01:59:01 Fairy Tailz (56 views) 2015-04-14 20:13:12 Riven (62 views) 2015-04-12 21:36:37 bus hotdog (87 views) 2015-04-10 02:39:32
 theagentd 25x BurntPizza 19x Spasi 16x kingroka123 11x wessles 11x alwex 11x Hanksha 8x ra4king 7x chrislo27 7x Ecumene 7x Olo 7x kevglass 7x princec 6x Riven 6x trollwarrior1 5x EgonOlsen 5x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org