Intersection and difference of two rectangles

The problem of intersection of two rectangles is very easy to solve. But difference of two rectangles is something considered much less frequently.

To clarify, we will be looking only at rectangles that are parallel to the 2D axes.

Obviously, when one rectangle chomps away a part of another, typically it can no longer be represented as just one rectangle. The illustration shows these different cases. The solution described here represents the difference as a sum of multiple rectangles. It does not try to represent it in as few rectangles as possible, because there are multiple ways to do that and no objective way to pick one.

So if we have a Rectangle class that consists of 4 coordinates: x1, y1 (topleft corner), x2, y2 (bottomright corner), the intersection and difference functions would work like this (test cases are put in accordance to the illustration):

wzxhzdk:0

Intersection is simple. We look at the left edges of each rectangle and take whichever of them is more to the right — this will be the left edge of the new rectangle. Then the opposite happens for the right edges, and similar actions for top and bottom edges.

But there is also a possibility that the rectangles don't intersect. In case 4 the rightmost of the left edges is further to the right than the leftmost of the right edges. That (and the similar vertical case) will mean failure. So in the end we just need to check if the resulting rectangle has positive dimensions, and return it only in that case.

The difference, however, was a lot of fun to make.

As we can see from the illustration, the difference may consist of 0 to 8 rectangles!

The code below works by finding all the vertical (xs) and horizontal (ys) lines that go through our rectangle (all the white lines on the picture, which is the rectangle itself, and grey lines, which are the edges of the subtracted rectangle.

The coordinate sets are turned into sorted lists and taken pairwise: [a, b, c] becomes [(a, b), (b, c)].

The product of such horizontal and vertical segments gives us all the rectangles that we divided the original one into by these lines.

All that remains is to yield all of these rectangles except the intersection.

Now, for the code!

Methods in the class are ordered illogically so that the important parts are visible without scrolling.

wzxhzdk:1

(This was originally submitted on StackOverflow)