Demo

In this post, I discuss the rectangle intersector used for the following demo, which typically exceeds 4 gigaintersections per second:

This is the fastest result I'm aware of, possibly because I can't find any benchmarks of this kind, or much discussion of rectangle intersection in general.

Here is the article I was looking for.

Discussion

Suppose you have two rectangles and want to know if they intersect. Perhaps those rectangles are repsented as CGRects, or equivalently, they consist of horizontal and vertical lines. This axis-aligned case is very simple:

You simply check each point of one rectangle to see if it's inside the minimum/maximum points of the other. In fact, CGRect has a nice intersects(_:) API for this.

But how to deal with the case that the rectangles are rotated?

Stack Overflow

Stack Overflow gives two answers. The first is based on the hyperplane separation theorem. It's a fine algorithm, but it's generic across any polygon, so if your problem involves rectangles specifically there are faster techniques.

The second method is an approximation that gives wrong results in some cases.

Alternatives

I will now explain some methods I used in a recent project. I doubt they are, strictly speaking, new. But they seem to be new to Google.

Approximations

First, let's examine what the problem is with the axis-aligned approach. Suppose we pretended our rectangle were axis-aligned, and did a simple min < point < max comparison like CGRect does.

As you can see, this will find points not inside our rectangle, but inside its axis-aligned bounding box.

This is often an efficent first-pass for intersection, since it is extremely cheap to calculate and quickly eliminate rectangles that are far away. However, let's assume that we've either done this and need something better, or we can't use that fast path for some reason.

Alternatively, we can rotate the whole system so our rectangle is axis-aligned:

In this configuration, checking whether points are inside is straightforward. You might imagine you can simply check the 4 points of the other rectangle to see if they are inside, however this is not the case:

In case you're like me and thinking "maybe adding the center point will fix that", it won't:

This counterexample involves rectangles with one side more than twice the dimension of the other. If your data is sufficiently squareish this may not be a real situation. In fact, you can continue to add test points that are evenly spaced in the long dimension until

w > l / (k+1)

in which case your approximation will be exact. Here is a diagram of the test points for k=2:

In many cases, some small k is sufficient. However for elongated rectangles k can become large. This approach may be appropriate for a fast path, or even for the only path on squareish data.

But at some point we have to stop coming up with new fast paths and actually solve the problem. And we may need a different approach that has better worst-case performance.

Stepping back a moment

Most approaches assume we have the rectangle points. However, not all 4 points form rectangles:

In fact, most points you would try would not be rectangular and therefore not valid inputs to a rectangle-intersection algorithm. In the language of information theory, would say the points-representation lacks entropy. Or mathematically, we might say this representation doesn't naturally describe rectangles.

Alternatively, we could define a rectangle by its center, angle of rotation, and size. Now, any combination of values will produce a valid rectangle:

Working in this notation turns out to be key. Of course, we can derive the point representation by:

1. Generating 4 points that are +/- half each dimension
2. Rotating the points about the angle
3. Translating by the center

A general algorithm

Suppose for a moment we have a rectangle with angle 0 and center 0,0. Then the lines that extend from the edges have a simple definition, that is

Why do we care about the lines in the edges? Well, because of the hyperplane separation theorem, two rectangles don't intersect if and only if there is some line that separates them:

And in the case of polygons, one of the polyon edges will be that line.

Convince yourself that in this diagram, only the edge indicated separates the rectangles. As a consequence, there may only be a single separating edge, and it may not be on the first rectangle we choose.

This insight yields the following algorithm:

1. Transform the whole system so one rectangle is at 0,0 with angle 0
2. Now we can easily calculate "candidate lines" from the identities shown in the diagram.

3. Let's try the line indicated. We know that the axis-aligned points will all be in the top half (y >= -w/2). Therefore, if this line separates the rectangles, the other rectangle will be in the bottom half (y < -w/2). In this example, only 2 of its 4 points are in the bottom half, so this is not a separating line.

4. Alternatively, consider this line. We know the axis-aligned rect will be on the left half (x <= l/2). Therefore, a separating line would have the other rect on the right (x > l/2). Indeed, all points on the rect meet that criteria, so this is a separating line.

5. If there's a separating line, the rectangles do not intersect.
6. If there wasn't a separating line, repeat this process with the other rect at 0,0 with angle 0
7. If it didn't have any separating lines either, the rectangles do not intersect.

Performance remarks

This is substantially faster than the better-known polygon method in several respects.

First, when we "transform the system" we only need to transform a single rectangle. The axis-aligned rectangle is only used for lines, which we calculate directly from the identities. Therefore we don't even need to bother about that rectangle's points.

Second, when we transform the other rectangle, we can transform its center/angle representation directly, and derive the corner points from that. This is better than deriving the points first, and then transforming all of them serially.

Third, the bulk of this algorithm is simple comparisons against 4 points, and the occasional sin/cos for the rotation. There is an efficient vectorized implementation for practically every platform, including GPUs for example.

Implementation

You can see an implementation of this in blitcurve, a project which I will hopefully write more about soon™️.

In the meantime, blitcurve has both CPU and GPU implementations of various geometry algorithms like this one.

Special thanks to my friend Blue for his invaluable assistance with this algorithm.