Fastest way to determine if two rotated rectangles intersect?

Performance Tuning
#1

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?

#2

Google “separating axis theorem”. :slight_smile:

#3

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.

#4

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

#5

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:

#6

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.

#7

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
  continue;

 //Here use a smarter test if requiered
 ...

}
#8

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.

#9

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

#10

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.

#11

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.