Hi !
Featured games (87)
games approved by the League of Dukes
Games in Showcase (671)
Games in Android Showcase (194)
games submitted by our members
Games in WIP (727)
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 7873 times)
0 Members and 1 Guest are viewing this topic.
Offline 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?
Offline ra4king

JGO Kernel

Medals: 422
Projects: 3
Exp: 5 years

I'm the King!

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

Google "separating axis theorem". Smiley

Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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:

See my work:
OTC Software
Offline 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:
Offline 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.
Offline 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 :

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 change

if(dx*dx+dy*dy>distMinSqrt ) //Object wont be viewable

 //Here use a smarter test if requiered


Offline 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.
Offline 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.
Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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.

IanParcs (44 views)
2016-04-18 14:18:53

KaiHH (43 views)
2016-04-18 08:35:41

KaiHH (74 views)
2016-04-15 12:43:58

theagentd (75 views)
2016-04-14 02:16:17

theagentd (89 views)
2016-04-14 02:15:43

IanParcs (103 views)
2016-04-12 03:51:16

IanParcs (46 views)
2016-04-12 03:50:03

IanParcs (42 views)
2016-04-12 03:49:54

IanParcs (37 views)
2016-04-12 03:49:52

IanParcs (47 views)
2016-04-12 03:49:52
Website offering 3D Models specifically for games for free
by vusman
2016-04-29 12:56:17

List of Learning Resources
by SilverTiger
2016-02-05 09:39:47

List of Learning Resources
by SilverTiger
2016-02-05 09:38:38

List of Learning Resources
by SilverTiger
2016-02-05 09:35:50

Rendering resources
by Roquen
2015-11-13 14:37:59

Rendering resources
by Roquen
2015-11-13 14:36:58

Math: Resources
by Roquen
2015-10-22 07:46:10

Networking Resources
by Roquen
2015-10-16 07:12:30 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‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!