Non axis-aligned rectangle intersection

Question

I'm trying to find an algorithm that will compute the intersection between 2 rectangles, which are not necessarily axis-aligned, and return the resulting intersection.

This question describes finding whether an intersection exists. I'd like to have the resulting shape of the intersection, if it exists.

My application of the algorithm will use one axis-aligned rectangle and one that is not necessarily axis-aligned, but a general algorithm would be preferable.

Thanks!

Answer 1

Here's a polygon-polygon intersection algorithm with sources in C and Java, that returns the area of intersection.

Answer 2

One algorithm for finding the intersection of any two convex polygons involves first finding the convex hull around all the vertices. The convex hull follows the outline of whichever polygon is outermost; the shape you're seeking follows the outline of whichever polygon is innermost, so follow whichever one the convex hull isn't following. Here is a prettier picture of the same algorithm.

This extremely brief wiki page mentions two other algorithms. One has you breaking the polygons into trapezoids. The other is a very clever way of walking around both polygons counterclockwise in lock step. I think I like this one best, but as the wiki says, it's rather hard to describe.