[Math] the simplest way to convert two overlapping rectangles into a set of non-overlapping rectangles

geometry

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?

Best Answer

This problem is well-studied in computer graphics, because, at its core, it is a special case of clipping. Two traditional solutions are the Weiler–Atherton clipping algorithm, and the Sutherland–Hodgman clipping algorithm. Both are more general than you need. But using the search term "rectangle clipping" will lead you to specific code, e.g., this C++ code. Finally, this question might be better asked at StackExchange. For example: "How to subtract a rectangle from another?."

Related Question