Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) 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 12981 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: 508
Projects: 3
Exp: 5 years

I'm the King!

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

Roquen

JGO Kernel

Medals: 517

 « 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

JGO Kernel

Medals: 517

 « 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

JGO Kernel

Medals: 517

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

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

 EgonOlsen (59 views) 2018-06-10 19:43:48 EgonOlsen (42 views) 2018-06-10 19:43:44 EgonOlsen (61 views) 2018-06-10 19:43:20 DesertCoockie (240 views) 2018-05-13 18:23:11 nelsongames (142 views) 2018-04-24 18:15:36 nelsongames (141 views) 2018-04-24 18:14:32 ivj94 (883 views) 2018-03-24 14:47:39 ivj94 (144 views) 2018-03-24 14:46:31 ivj94 (795 views) 2018-03-24 14:43:53 Solater (159 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 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