# What is the simplest way to convert two overlapping rectangles into a set of non-overlapping rectangles?

Two rectangles can overlap in lots of different ways. One can be entirely inside the other (2 variations depending on which is inside which). They can overlap at a single corner (4 variations there depending on which corner pair is involved), they can overlap with one rectangle passing through one side but not the other (8 variations, 1 for each side of each rectangle), etc.

Take the following two rectangles:

+--------+
|        |
|  +--+  |
|  |  |  |
+--|--|--+
|  |
+--+


They would become the following 5 rectangles:

+--------+
|        |
+--+--+--+
|  |  |  |
+--+--+--+
|  |
+--+


Or possibly just the following 2 rectangles:

+--------+
|        |
|        |
|        |
+--+--+--+
|  |
+--+


I want to write code which would take two arbitrary rectangles (each one has x,y coordinates of one corner plus a width and height) and chop them up so that we end up with a set of non-overlapping rectangles.

The problem is that there are SO MANY possible variations! Would it really be necessary to write code with 20 or more special cases where I first check if the upper left corner overlaps the other rectangle and then check the upper right corner, etc., and eventually check if two corners overlap and so on and so on?

Can anyone think of a simpler way to do this other than to enumerate all possible overlaps and then laboriously check every point and combinations of points to see how they overlap?

-