Area of Intersection of Two Rotated Rectangles

algorithm graphics geometry intersection
Nate Thorn picture Nate Thorn · Jul 26, 2012 · Viewed 13.5k times · Source

I have two 2D rectangles, defined as an origin (x,y) a size (height, width) and an angle of rotation (0-360°). I can guarantee that both rectangles are the same size.

I need to calculate the approximate area of intersection of these two rectangles. Rectangle intersection

The calculation does not need to be exact, although it can be. I will be comparing the result with other areas of intersection to determine the largest area of intersection in a set of rectangles, so it only needs to be accurate relative to other computations of the same algorithm.

I thought about using the area of the bounding box of the intersected region, but I'm having trouble getting the vertices of the intersected region because of all of the different possible cases: So many possible intersection shapes

I'm writing this program in Objective-C in the Cocoa framework, for what it's worth, so if anyone knows any shortcuts using NSBezierPath or something you're welcome to suggest that too.

Answer

Joseph O'Rourke picture Joseph O'Rourke · Jul 26, 2012

To supplement the other answers, your problem is an instance of line clipping, a topic heavily studied in computer graphics, and for which there are many algorithms available. If you rotate your coordinate system so that one rectangle has a horizontal edge, then the problem is exactly line clipping from there on.

You could start at the Wikipedia article on the topic, and investigate from there.

Related questions

Algorithm to detect intersection of two rectangles?

I'm looking for an algorithm to detect if two rectangles intersect (one at an arbitrary angle, the other with only vertical/horizontal lines). Testing if a corner of one is in the other ALMOST works. It fails if the rectangles …

Read More
fast algorithm for drawing filled circles?

I am using Bresenham's circle algorithm for fast circle drawing. However, I also want to (at the request of the user) draw a filled circle. Is there a fast and efficient way of doing this? Something along the same lines …

Read More
Find if a point is inside a convex hull for a set of points without computing the hull itself

What is the simplest way to test if a point P is inside a convex hull formed by a set of points X? I'd like an algorithm that works in a high-dimensional space (say, up to 40 dimensions) that doesn't explicitly …

Read More