Alex Rivera | Logout

Area of Intersection of Two Rotated Rectangles

Asked 2012-07-26T13:09:33.070
27

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.

algorithm graphics geometry intersection
Edit
Report

1 Answer

4

In any case, computing the exact intersection polygon of two convex polygons is an easy task, since any convex polygon can be seen as an intersection of half-planes. "Sequential cutting" does the job.

Choose one rectangle (any) as the cutting rectangle. Iterate through the sides of the cutting rectangle, one by one. Cut the second rectangle by the line that contains the current side of the cutting rectangle and discard everything that lies in the "outer" half-plane.

Once you finish iterating through all cutting sides, what remains of the other rectangle is the result.

answered 2012-07-26T14:52:01.667

Your Answer